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

그리고

:()

{ 
    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 INT 주. 하지만 아무 것도 작동하지 않습니다. 예를 들어 succ (3)는 0을 계산합니다. 문제의 원인을 파악하는 데 도움을 주시겠습니까? 추가 코드가 필요하면 게시 할 것입니다. 미리 감사드립니다.

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