二叉樹的有序繼任者

我正在編寫一個代碼來尋找二叉樹（不是二叉搜索樹）的有序繼任者。這只是一個練習題。更喜歡刷樹概念。二叉樹的有序繼任者

我在做一個按順序遍歷並跟蹤前一個節點。每當前一個節點等於我們正在搜索的後繼節點時，就會打印當前節點。

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

我正在尋找一些測試案例，我的解決方案可能會失敗？而且我的方法是否正確？如果不是，那我該怎麼辦呢？

來源

2012-09-17 h4ck3d

'prev'定義在哪裏？ –

我相信這個算法是正確的，但打印successorFor有意義嗎？或者你打算在事實上打印根目錄？ – Marcus

@DavidB完成。它是一個靜態變量。 – h4ck3d

該算法的基本邏輯是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

來源

2012-09-18 10:50:39

它只是一棵二叉樹，我需要找到一個節點的下一個中繼節點，也就是在給定節點之後的樹行走過程中我將獲得的下一個節點。 – h4ck3d

該算法不假設任何有關後繼者的位置，這就是爲什麼有一個遞歸調用到左邊的孩子和右邊的孩子。 –

二叉樹的有序繼任者

回答

相關問題