Succesor AVL樹C++

Question

我試圖實現AVL樹的succesor，我不會覆蓋我所有的代碼，這是最重要的部分（所有其他部分100％的作品）。我有class avltree,struct node與element,left,right和parent。我也有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; 
    } 
} 

而在這裏，我如何定義主這一切的東西： INT主要（）

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