二叉樹，返回預先遍歷中的下一個節點

Question

我有一個任務，我需要一些方法的幫助。

所以我有這樣的樹：

   A 
      / \ 
      B  C 
     / \/ \ 
      D E F  G 
     / \ 
     H  I 
    / \ 
    J  K 

，我的方法是：

public BinaryTree preorderNext(BinaryTree t, BinaryTree v, BinaryTree prev) {  

    prev = t; 

    if(t.getLeft() != null) { 
     preorderNext(t.getLeft(), v, prev); 
    } 

    if(t.getRight() != null) { 
     preorderNext(t.getRight(), v, prev); 
    } 


    if(prev == v) { 
     return t; 
    } 

    return null; 
} 

講師給了一個簡單的實現樹。這個類被稱爲BinaryTree，如果你想建立一個到它的節點鏈接，那麼你可以指定左邊和右邊的BinaryTree節點是什麼。

一個節點有兩個鏈接（一個到左邊，另一個到右邊的孩子），沒有鏈接到頭部。

因此，使用當前的方法，我能夠成功地進行預遍歷，我通過編寫存儲在節點的元素的打印語句來測試。

但是當我運行測試時，它告訴我A的下一個前序節點是B，K的下一個前序節點會拋出一個空異常，但它應該是I？

任何想法，我哪裏去錯了？變量prev應該保存對訪問的最後一個節點的引用，所以如果它等於節點v（這是我指定的節點，在v之後返回節點），我不應該得到下一個節點嗎？

Answer 1

這裏是preorder traversal遞歸完成的實現。

public void preOrderTraversal(BinaryTree root){ 
    if(root == null) return; 

    System.out.println(root); 
    preOrderTraversal(root.getLeft()); 
    preOrderTraversal(root.getRight()); 
} 

注：

1. 我不知道你的做法;你爲什麼要返回一個節點？在任何情況下，當root爲空時，您可以返回「emptyNode」並通過if語句處理它。
2. 正如你所看到的，我只處理root，任何級別的root變化。試着用一個run-through來想象這個，你會理解這個概念。
3. 您在開始時缺少對空節點的檢查（特別是對於t）。

您可以繼續調整您的結果。

最後要說的是這種方法的運行時複雜性，我強烈建議理解遞歸函數的運行時複雜性。它將在未來幫助你很多。檢查this wikipedia article重現關係。

Answer 2

我不確定遞歸執行該任務是否容易。

解決任務使用堆棧可能是一個更好的方法迭代方式：

public BinaryTree preOrderNext(BinaryTree toSearch) { 

    Stack<BinaryTree> openList = new Stack<BinaryTree>(); 

    openList.push(root); 

    while (openList.empty() == false) { 
     BinaryTree curr = openList.pop(); 

     if (curr.getRight() != null) 
      openList.push(curr.getRight()); 

     if (curr.getLeft() != null) 
      openList.push(curr.getLeft()); 

     if (curr.equals(toSearch) && openList.empty() == false){ 
      return openList.pop(); 
     } 
    } 
    return null; 
} 

，此方法是測試，但應該工作。

Answer 3

我提供了一個運行在O(h)運行時間的答案。

class Node { 
    public int key; 
    public Node l; 
    public Node r; 
    public Node p; 

    public Node(int key) { 
     this.key = key; 
     this.l = null; 
     this.r = null; 
     this.p = null; 
    } 
} 

public Node preorderNext(Node v) { 
    if (v.l != null) { 
     return v.l; 
    } else if (v.r != null) { 
     return v.r; 
    } else { 
     while (v.p != null) { 
      if (v == v.p.l) { 
       if (v.p.r != null) { 
        return v.p.r; 
       } else { 
        v = v.p; 
       } 
      } else { 
       if (v.p.p == null) { 
        return null; 
       } else if (v.p == v.p.p.l) { 
        if (v.p.p.r != null) { 
         return v.p.p.r; 
        } else { 
         v = v.p; 
        } 
       } else { 
        v = v.p; 
       } 
      } 
     } 
     return null; 
    } 
}