c++ - 使用二叉搜索树查找重复项

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;
}

创建另一个结构类型 Tree 的函数。

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

使用命名空间 std;

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

}

它只打印 99 ，为什么其他值没有被插入 vector ？另外我怎样才能让旅行功能变得更加优雅？

Answer 1

It only prints 99 , why doesnt the others values get pushed into vector?

插入值 55、99、5、99、100、13、99、55 后，您的树如下所示:

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

因此，您的查找重复项的算法仅识别 99，因为您仅检查节点的子节点是否与节点自身具有相同的值。

请注意，子树中节点的后继节点是其右子节点的外部左节点，前驱节点是其左子节点的外部右节点。

像这样调整您的代码并使用 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 << " ";
}