c++ - 获取后继二进制搜索树 C++ 数据结构

Question

我有二叉搜索树，我想得到它的元素的后继我看到我的代码很好，但我不知道出了什么问题 115 是运行时错误，5 是 5，应该是 6

    #include<bits/stdc++.h>
    using namespace std;

    struct Node
    {
        int data;
        Node *root;
        Node *left;
        Node *right;

    };

    typedef Node *ptr;

     ptr search(ptr tree,int key)
    {
        if(tree==NULL)return tree;
        if(tree->data==key)
            return tree;
        else if(tree->data>key)
            search(tree->right,key);
        else search(tree->left,key);
    }

    ptr most_left(ptr tree)
    {
        ptr result=tree;
        if(tree==NULL)return NULL;
        while(result->left!=NULL)
            result=result->left;
        return result;
    }

    ptr most_right(ptr tree)
    {
        ptr result=tree;
        if(tree==NULL)return NULL;
        while(result->right!=NULL)
            result=result->right;
        return result;
    }

    ptr min_element(ptr tree)
    {
        ptr result=tree;
        if(tree==NULL)return NULL;
        while(result->left!=NULL)
            result=result->left;
        return result;
    }

    ptr max_element(ptr tree)
    {
        ptr result=tree;
        if(tree==NULL)return NULL;
        while(result->right!=NULL)
            result=result->right;
        return result;
    }
    ptr temp=NULL;
    ptr insert_element(ptr &tree,int key)
    {

        if(tree==NULL)
        {
        tree=new Node();
        tree->data=key;
        tree->root=temp;
        return tree;
        }
        else if(tree->data>=key)
        {
        temp=tree;  
        insert_element(tree->left,key);
        }
        else 
        {
            temp=tree;
            insert_element(tree->right,key);
        }

    }

    void in_order(ptr tree)
    {
        if(tree == NULL) return;
        in_order(tree->left);
        cout<<tree->data<<" ";
        in_order(tree->right);
    }

    void pre_order(ptr tree)
    {
        if(tree == NULL) return;

        cout<<tree->data<<" ";
        pre_order(tree->left);
        pre_order(tree->right);
    }

    void post_order(ptr tree)
    {
        if(tree == NULL) return;
        post_order(tree->left);
        post_order(tree->right);
        cout<<tree->data<<" ";
    }

    ptr succesor(ptr node)
    {
        if(node->right != NULL) return min_element(node->right);
         ptr y = node->root;
        while(y != NULL && node == y->right ) {
            node = y;
            y = y->root;

        }
        return y;
    }

    int main() 
    {   
        ptr tree = NULL;
        insert_element(tree,7);
        insert_element(tree,5);
        insert_element(tree,55);
        insert_element(tree,6);
        insert_element(tree,15);
        insert_element(tree,60);
        insert_element(tree,10);
        insert_element(tree,115);
        ptr inserted = insert_element(tree,5);
        insert_element(tree,6);
        insert_element(tree,12);
        cout<<"succesor "<<succesor(inserted)->data;
        cout<<"\nData Inserted \n"<<"In order : ";
        in_order(tree);
        cout<<endl;
        cout<<"Pre order : ";
        pre_order(tree);
        cout<<endl;
        cout<<"Post order : ";
        post_order(tree);
        cout<<endl;
        cout<<"Minimum : "<<min_element(tree)->data<<endl;
        cout<<"Maximum : "<<max_element(tree)->data<<endl;
        return 0;
    }

Answer 1

1. “5应该是6”
   不，程序绝对正确。
   在 insert_element 函数中，您检查 tree->data >= key(注意 >=)，所以如果已经有一个元素与要插入的key相同的数据，新的key会被插入到左子树中。这就是为什么最后插入的 5 的后继是前一个插入的 5。如果将 >= 替换为 >，第二个 5 将被插入到右子树中，因此它的继任者如预期的那样是 6。

2. 115 的后继者运行时错误
   当然，115没有后继者，因为这是最大的值(value)。因此，后继函数返回一个 NULL 指针，如果取消引用，将导致未定义的行为。

顺便说一句，程序有更多未定义的行为。函数 search 和 insert_element 可能会在函数末尾流出而不返回值。标准说:

Flowing off the end of a function is equivalent to a return with no value; this results in undefined behavior in a value-returning function. (6.6.3)

在这种情况下，您很幸运，因为在大多数实现中，存储返回值的位置保留其值来自递归调用的返回语句，但是，当然，这应该是固定的。