查找樹是否是單聲道（所有元素都是唯一的）的函數？

Question

我試圖將Total函數和isMono函數添加到此代碼中。已經總共

需要函數ismono的幫助，它返回一棵樹是否是單聲道的（所有元素都是唯一的，也就是說沒有元素會多次出現）。請

#ifndef T_H 

#define T_H 

#include <iostream> 
#include <iomanip> 
using namespace std; 

struct tnode { 
    int info ; 
    int count; 
    tnode * right, *left; 
}; 

tnode * insert(int target,tnode * t); 
tnode * makenode(int x); 
tnode * tsearch(int x,tnode * t); 
void inorder(tnode * t); 
int height(tnode * t); 
int count(tnode * t) ; 
int total(tnode * t) ; 

#endif 

int main() { 
int n,c; 
tnode * t = NULL, *x; 
    while (cin >> n) {t=insert(n,t);cout << n <<' ';} 
    cout << endl; 
    inorder(t); 
    cout << endl; 
    c = count(t); 
    cout << "count: "<< c <<endl; 
    cout << endl; 
    c = height(t); 
    cout << "height: "<< c <<endl; 
    cout << endl; 
    c=200; 
    while (c-->0) if (x = tsearch(c,t)) cout << c << " is on the tree."<<endl; 
return 0; 
} 

#include "t.h" 

int count(tnode * t) { 
    if (t == NULL) return 0; 
    return 1 + count(t->left) + count (t->right); 
} 

#include "t.h" 

int height(tnode * t) { 
    if (t == NULL) return -1; 
    return 1 + max(height(t->left) , height (t->right)); 
} 

#include "t.h" 

//write out t in order 
void inorder(tnode * t) { 
    if (t == NULL) return; 
    inorder (t->left);//write out lst in order 
    cout <<setw(5) << t->info <<setw(5) << t->count<< endl; 
    inorder (t->right);//write out rst in order 
} 

#include "t.h" 

tnode * insert(int x, tnode * t) { 
tnode * tmp = tsearch(x,t); 
if (tmp != NULL) { 
    tmp->count++; 
    return t; 
} 
if (t == NULL) return makenode(x); 
if (x < t->info) { 
    t->left = insert(x,t->left); 
    return t; 
} 
t->right = insert(x,t->right); 
return t; 
} 

#include "t.h" 

tnode * makenode(int x) { 
tnode * t = new tnode; 
    t->info =x; 
    t->count =1; 
    t->right = t->left = NULL; 
return t; 
} 

Answer 1

如果您使用C++，你可以簡單地使用std::set或者std::unordered_set存儲在你的樹對象的名單。然後，使用一個樹遍歷（序，序，後序等），並在遍歷每個對象，請執行以下操作：

1. 你檢查它是否已經在set。如果是，那麼return false;。
2. 您將該元素添加到set。

然後，當你完成遍歷時，你知道沒有任何重複，所以簡單地return true;。

Answer 2

只是遍歷樹！

//Gets the value of the node at the leftmost node 
int left_most_value(tnode * t) { 
    if (t == NULL) return (0); //Something went wrong 
    if (t->left == NULL) return(t->info); 
    else return(left_most_value(t)); 
} 

//Gets the value of the node at the rightmost node  
int right_most_value(tnode * t) { 
    if (t == NULL) return (0); //Something went wrong 
    if (t->right == NULL) return(t->info); 
    else return(right_most_value(t)); 
} 

//Returns true (1) if node does NOT have duplicate 
int node_is_mono(tnode * t) { 
    //Ignore leaf nodes 
    if (t->left == NULL && t->right == NULL) return 1; 

    //Check the left side 
    if (t->left != NULL && right_most_value(t->left) == t->info) return(0); 

    //Check the right side 
    if (t->right != NULL && left_most_value(t->right) == t->info) return(0); 

    //This node is mono 
    return(1); 
} 

int tree_is_mono(tnode * t) { 
    if (t == NULL) return(1); 

    //If one node has a duplicate, then the entire tree is NOT mono 
    if (node_is_mono(t) == 0) return 0; 
    else return(tree_is_mono(t->left) && tree_is_mono(t->right)); 
} 

---

的algoritm

在樹中的每個節點的說明，您需要執行以下步驟。

1. 從右側節點的子節點找到節點的最左側節點。如果它們的值相等，則該樹是不是單聲道（停止搜索並且return false）
2. 從左側節點的子節點找到節點的最右側節點。如果它們的值相等，那麼樹是非單聲道（停止搜索和return false）
3. 我們發現沒有節點值相等，所以樹是單聲道！ return true