이진 트리의 순차 후계자

Question

이진 트리 (이진 검색 트리가 아님)의 순서대로 후행을 찾는 코드를 작성했습니다. 그것은 단지 연습 문제 일뿐입니다. 나무 개념을 닦는 것이 더 좋아.

이전 노드를 순차적으로 탐색하고 추적하고있었습니다. 이전 노드가 후행 노드를 검색하는 노드와 동일해질 때마다 현재 노드를 인쇄합니다.

void inOrder(node* root , node* successorFor) { 
    static node* prev = null; 
    if(!root) 
    return; 
    inOrder(root->left,successorFor); 
    if(prev == successorFor) 
    print(root); 
    prev = root; 
    inOrder(root->right,successorFor); 
} 

내 솔루션이 실패 할 수있는 몇 가지 테스트 사례를 찾고 있었습니까? 내 접근 방식이 맞는지 아닌지. 그렇지 않다면 어떻게해야합니까?

Answer 1

이 알고리즘의 기본 논리는 tree walk입니다. 전화 걸기 print(TREE-SUCCESSOR(root, k).key)

TREE-SUCCESSOR(root, k) 
    if root == NIL 
     return NIL 
    left = TREE-SUCCESSOR(root.left, k) 
    right = TREE-SUCCESSOR(root.right, k) 
    successor = NIL 
    if root.key > k 
     successor = root 
    if left 
     if k < left.key 
      if successor 
       if left.key < successor.key 
        successor = left 
      else 
       successor = left 
    if right 
     if k < right.key 
      if successor 
       if right.key < successor.key 
        successor = right 
      else 
       successor = right 
    return successor