如何在二叉樹中找到下一個繼承者？

Question

我想在自己的TreeSet類中實現一個Iterator。 但是，我的創建它的嘗試只能在當前節點爲根的情況下才有效。 迭代器看起來是這樣的：

構造：

public TreeWordSetIterator() 
{ 
    next = root; 

    if(next == null) 
     return; 

    while(next.left != null) 
     next = next.left; 
} 

hasNext：

public boolean hasNext() 
{ 
    return next != null; 
} 

下一頁：

public TreeNode next() 
{ 
    if(!hasNext()) throw new NoSuchElementException(); 

    TreeNode current = next; 

    next = findNext(next); // find next node 

    return current; 
} 

FindNext中：

private TreeNode findNext(TreeNode node) 
{ 
    if(node.right != null) 
    { 
     node = node.right; 

     while(node.left != null) 
      node = node.left; 

     return node; 
    } 
    else 
    { 
     if(node.parent == null) 
      return null; 

     while(node.parent != null && node.parent.left != node) 
      node = node.parent; 

     return node; 
    } 
} 

這工作得很好，直到我到達我的根節點。所以我只能遍歷根的左邊的孩子，而不是正確的。任何人都可以給我一些關於我在做什麼錯誤的提示嗎？我不期望一個解決方案，只是一些提示。

問題：如何在給定每個節點指向其父，左孩子和右孩子的TreeSet中找到下一個節點。

在此先感謝

Answer 1

它有助於考慮Binary Search Tree的規則。讓我們假設先前所返回的節點是n：

• 如果n有右子樹，然後下一個值的節點將是右子樹的最左邊的節點。
• 如果n沒有右子樹，然後下一個值的節點將是n始祖包含在其左子樹n。

您的代碼正確處理第一個案件，但不是第二個。考慮node是樹最左邊的葉子（起始情況）的情況。 node沒有合適的孩子，所以我們直接去else。 node有一個父項，所以if-子句被跳過。 node.parent.left == node，因此跳過while子句而根本不執行。最終結果是返回node。我希望你的迭代器能夠永久地繼續返回同一個節點。

Answer 2

主要有3種方法，你可以遍歷一個binarry樹

private void inOrder(TreeNode node) { 
    if(isEmpty())return; 
    if(node.getLeftNode()!=null)inOrder(node.getLeftNode()); 
    System.out.print(node.getNodeData()+" "); 
    if(node.getRightNode()!=null)inOrder(node.getRightNode()); 
} 

private void preOrder(TreeNode node) { 
    if(isEmpty())return; 
    System.out.print(node.getNodeData()+" "); 
    if(node.getLeftNode()!=null)preOrder(node.getLeftNode()); 
    if(node.getRightNode()!=null)preOrder(node.getRightNode()); 
} 

private void postOrder(TreeNode node) { 
    if(isEmpty())return; 
    if(node.getLeftNode()!=null)postOrder(node.getLeftNode()); 
    if(node.getRightNode()!=null)postOrder(node.getRightNode()); 
    System.out.print(node.getNodeData()+" "); 
} 

//use 
inOrder(root); 
preOrder(root); 
postOrder(root); 

其作爲簡單，你的代碼並沒有真正對我來說很有意義，有沒有別的東西，你除了以這種方式之一進行迭代之外，還試圖做些什麼？

Answer 3

我想你需要保存以前的點在你的迭代器，所以你知道你去過的地方之前

這裏是一些代碼，但要知道，這是不完整的，你應該自己做，它只是展示你的想法。它也不處理根節點。

findNext(TreeNode node, TreeNode previousNode) { 

    if(node.left != null && node.left != previousNode && node.right != previousNode){ //go left if not been there yet 
    return node.left; 
    } 
    if(node.right != null && node.right != previousNode){ //go right if not been there yet 
    return node.right; 
    } 
    return findNext(node.parent, node); //go up and pass current node to avoid going down 
} 

Answer 4

一個好方法是使用堆棧來管理排序，如果您使用遞歸遍歷（而不是試圖根據SteveL的答案中所述構建一個Iterator），那麼這是一種完成的方式。

當你想從左邊開始，你第一次加載到堆棧中根節點並以正確的順序最左邊的孩子（推而下降，從根左）。

總是彈出來自堆棧的頂部的下一個，並返回你只是突然一個前推其右孩子（如果有的話）及其所有最左邊的孩子，讓他們在旁邊一行。

通過這種方法，堆棧的頂部總是會返回下，當堆棧是空的，沒有更多...

在代碼：

import java.util.Iterator; 
import java.util.NoSuchElementException; 
import java.util.Stack; 

public class TreeNodeInOrderIterator<T> implements Iterator<T> { 

    private final Stack<TreeNode<T>> stack; 

    public TreeNodeInOrderIterator(TreeNode<T> root) { 
     this.stack = new Stack<TreeNode<T>>(); 
     pushLeftChildren(root); 
    } 

    @Override 
    public boolean hasNext() { 
     return !stack.isEmpty(); 
    } 

    @Override 
    public T next() { 
     if (!hasNext()) 
      throw new NoSuchElementException(); 
     TreeNode<T> top = stack.pop(); 
     pushLeftChildren(top.right); 
     return top.val; 
    } 

    @Override 
    public void remove() { 
     throw new UnsupportedOperationException(); 
    } 

    private void pushLeftChildren(TreeNode<T> cur) { 
     while (cur != null) { 
      stack.push(cur); 
      cur = cur.left; 
     } 
    } 

} 

在這碼，TreeNode由

public class TreeNode<T> { 
    T val; 
    TreeNode<T> left; 
    TreeNode<T> right; 
    TreeNode(T x) { val = x; } 
} 

如果你想擁有每個節點還知道它的父定義，這是確定的，但所有的遍歷是通過什麼是在堆棧上，並增加了堆棧使用left和right子鏈接。