获取后继二进制搜索树 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

“5 应该是 6”
不，程序绝对正确。
在 insert_element 函数中检查 tree->data >= key（注意 >=），因此如果已经有一个元素与要插入的键具有相同的数据, 新密钥将被插入到左子树中。这就是为什么最后插入的 5 的后继是前一个插入的 5。如果将 >= 替换为 >，则第二个 5 将插入到右子树中，因此它的后继是预期的 6。
115
后继者的运行时错误当然，115没有后继者，因为这是最大的价值。所以后继函数 return 是一个 NULL 指针，如果取消引用，会导致未定义的行为。

顺便说一句，程序有更多未定义的行为。函数 search 和 insert_element 可能会在没有 return 值的情况下流出函数的末尾。标准说：

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)

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

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

get succesor Binary Search Tree c++ Data structure

c++

tree

binary-search-tree

data-structures