使用二叉搜索樹查找重複項

Question

我實現了二叉搜索樹。我的代碼非常簡單。

struct Tree{ 
    Tree* left; 
    Tree* right; 
    int value; 
}; 

這裏我聲明瞭基本的結構。

Tree* makenode(int val){ 

    Tree* tmp= new Tree; 
    tmp->left=tmp->right=NULL; 
    tmp->value=val; 
    return tmp; 
} 

創建另一個結構類型樹的函數。

void setLeft(Tree* x,int val){ 
    x->left=makenode(val); 
} 

void setRight(Tree* x,int val){ 
    x->right=makenode(val); 
} 

void insertt(Tree *x,int val){ 

    while(1){ 
     if(val < x->value){ 
      if(x->left!=NULL){ 
       x=x->left; 
      }else{ 
       setLeft(x,val); 
       break; 
      } 
     }else{ 
      if(x->right!=NULL){ 
       x=x->right; 
      }else{ 
       setRight(x,val); 
       break; 
      } 
     } 
    } 

} 

循環遍歷樹並在正確的位置插入值=在添加樹時排序樹。

什麼是製造麻煩給我的是這個小功能

void travel(Tree *x){ 

    if(x->left!=NULL){ 

     travel(x->left); 
    } 
    Tree *b; 
    b=x->right; 
    if(x->value == b->value){ 
     cout << "Duplicate is " << x->value << endl; 
     return ; 
    } 
    cout << "Value is " << x->value << endl; 

    if(x->right!=NULL){ 
     travel(x->right); 
    } 
} 

如果我省略

Tree *b; 
b=x->right;  
if(x->value == b->value){ 
       cout << "Duplicate is " << x->value << endl; 
       return ; 
} 

我想它來檢查enxt值它很好地打印值時，其打印當前值，它兩者都是相同的=我們重複。但它總是讓我的程序崩潰。這是什麼造成的？排序的行爲，可能是這裏唯一的問題是遞歸的行爲，但我不能找出

我試圖改造它作爲

void travel(Tree *x, vector<int> &y){ 
    vector<int>::iterator it; 
    if(x->left!=NULL){ 
     if(x->value == x -> left -> value){ 
      it=find(y.begin(), y.end(), x->value); 
      if(it==y.end()){ 
       y.push_back(x->value); 
      } 

     } 
     travel(x->left, y); 
    } 


    cout << "Value is " << x->value << endl; 

    if(x->right!=NULL){ 
     if(x->value == x -> right -> value){ 
      it=find(y.begin(), y.end(), x->value); 
      if(it==y.end()){ 
       y.push_back(x->value); 
      } 

     } 
     travel(x->right,y); 
    } 

} 

但有了這個功能主要

int main() 
{ 
    vector<int> dups; 


    Tree * node = makenode(55); 
    insertt(node,99); 
    insertt(node,5); 
    insertt(node,99); 
    insertt(node,100); 
    insertt(node,13); 
    insertt(node,99); 
    insertt(node,55); 

    travel(node,dups); 

    printDup(dups); 
    return 0; 
} 
and printDup 

using namespace std;

void printDup(vector<int> &y){ 
    cout << "Duplicates are: "; 
    for(int i = 0; i < y.size(); i++){ 
     cout << y[i] << " "; 
    } 

} 

它只打印99，爲什麼其他值被推入矢量？另外我怎樣才能讓旅行功能變得更優雅？

Answer 1

它只打印99，爲什麼其他值被推入矢量？

後插入值55，99，5，99，100，13，99，55你的樹是這個樣子：

  55 
     /\ 
     / \ 
     / \ 
     5  99 
     \ /\ 
     13 55 99 
        \ 
        100 
        /
        99 

所以你的算法來找到重複只能識別99，怎麼一回事，因爲您只檢查節點的子節點是否與節點自身具有相同的value。

注意子樹中節點的繼承者是其右子節點的左外節點，前者是其左子節點的右外節點。

適應你這樣的代碼，並使用std::set存儲重複：

#include <set> 

int outerleft(Tree *x) 
{ 
    while (x->left != nullptr) x = x->left; 
    return x->value; 
} 

int outerright(Tree *x) 
{ 
    while (x->right != nullptr) x = x->right; 
    return x->value; 
} 

void travel(Tree *x, std::set<int> &dups) 
{ 
    if (x->left != nullptr) 
    { 
     if (x->value == outerright(x->left)) 
      dups.insert(x->value); 
     travel(x->left, dups); 
    } 

    std::cout << "Value is " << x->value << std::endl; 

    if (x->right != nullptr) 
    { 
     if (x->value == outerleft(x->right) ) 
      dups.insert(x->value); 
     travel(x->right, dups); 
    } 
} 

void printDup(const std::set<int> &dups) 
{ 
    std::cout << "Duplicates are: "; 
    for(int v : dups) 
     std::cout << v << " "; 
}