c++ - 后继AVL树c++

Question

我已经尝试实现 AVL 树的后继，我不会涵盖我的所有代码，这是最重要的部分(所有其他部分 100% 有效)。我有 class avltree、struct node with element、left、right 和 父级。我还有 typedef struct node *nodeptr; 以方便使用。

nodeptr avltree::find(int x,nodeptr &p)
{
    if (p==NULL)
    {
        cout<<"NOT EXISTS\n"<<endl;
        return NULL;
    }
    else
    {
        if (x < p->element)
        {
            return find(x,p->left);
            // return p;
        }
        else
        {
            if (x>p->element)
            {
                return find(x,p->right);
                // return p;
            }
            else
            {
                // cout<<"EXISTS\n"<<endl;
                return p;
            }
        }
    }
}
nodeptr avltree::succ(int x, nodeptr &p){
    p=find(x, p);
    if (p->right){
        return findmin(p);
    }
    else {
        while(   (p->parent)->left!=p  ){
            p=p->parent;

        }
        return p;
    }
}

在这里，我如何在 main 中定义所有这些东西: 内部主要()

{
    nodeptr root, max;
    avltree bst;
    root=NULL;


    for(int i=0; i<=5; i++){
        bst.insert(i, root);
    }


    bst.getneighbors(root);
    max=bst.succ(3, root);
    cout<<max->element;

    return 0;
}

void avltree::getneighbors(nodeptr &p){ //get parents
    while(!p->left){
        nodeptr p2;
        p2=p->left;
        p2->parent=p;
        getneighbors(p2);
    }
    while(!p->right){
        nodeptr p2;
        p2=p->right;
        p2->parent=p;
        getneighbors(p2);
    }
}

所以，我已经实现了函数 getParents。但是没有任何效果，例如计算 0 中的 succ(3)。你能帮我弄清楚问题是什么吗？如果您需要其他代码 - 我会发布它。提前致谢。

Answer 1

nodeptr avltree::succ(int x, nodeptr &p){
    p=find(x, p);
    if (p->right){
        //////////////////////////
        return findmin(p->right);
        //////////////////////////
    }
    else {
        //////////////////////////
        while(true){
            if (p->parent == NULL)
                return NULL;
            if ((p->parent)->left == p)
                return p->parent;
            else
                p=p->parent;
        }
        //////////////////////////
    }
}