遍歷通過二進制樹的所有節點在Java中

比方說，我有一個簡單的二進制樹節點類，如下所示：遍歷通過二進制樹的所有節點在Java中

public class BinaryTreeNode { 
    public String identifier = ""; 
    public BinaryTreeNode parent = null; 
    public BinaryTreeNode left = null; 
    public BinaryTreeNode right = null; 

    public BinaryTreeNode(BinaryTreeNode parent, String identifier) 
    { 
     this.parent = parent; //passing null makes this the root node 
     this.identifier = identifier; 
    } 

    public boolean IsRoot() { 
     return parent == null; 
    } 
}

我怎麼想補充，它能夠遞歸地通過任何大小的樹遍歷方法，從左到右訪問每個和每個現有節點，沒有重新訪問已經遍歷的節點？

將這項工作？：

public void traverseFrom(BinaryTreeNode rootNode) 
{ 
    /* insert code dealing with this node here */ 

    if(rootNode.left != null) 
     rootNode.left.traverseFrom(rootNode.left); 

    if(rootNode.right != null) 
     rootNode.traverseFrom(rootNode.right); 
}

來源

2013-03-09 RectangleEquals

看起來很像下面的正確答案。 – 2013-03-09 02:29:49

@PeterWooster - 對，除了我從每個節點調用遍歷方法，導致遞歸發生遞歸爲每個節點，而不是從根 – RectangleEquals 2013-03-09 03:38:04

有3種類型二叉樹的遍歷，你可以實現：

例如：

考慮這個以下二叉樹：

enter image description here

Pre-order traversal sequence: F, B, A, D, C, E, G, I, H (root, left, right) 
In-order traversal sequence: A, B, C, D, E, F, G, H ,I (left, root, right) 
Post-order traversal sequence: A, C, E, D, B, H, I, G, F (left, right, root)

代碼示例：

留給二叉樹，反對權遍歷二叉樹的遍歷順序：

public void traverse (Node root){ // Each child of a tree is a root of its subtree. 
    if (root.left != null){ 
     traverse (root.left); 
    } 
    System.out.println(root.data); 
    if (root.right != null){ 
     traverse (root.right); 
    } 
}

來源

2013-03-09 02:25:43 codeMan

+1，遞歸總是樹的答案。有趣的答案是沒有遞歸做這個。 – 2013-03-09 02:31:40

@Peter Wooster迭代解決方案對於初學者來說更難以理解，所以我想爲什麼會出現複雜問題。 – codeMan 2013-03-09 02:38:03

我同意，我在幾年前的彙編程序中寫過類似的東西，它使用了一堆當然。 – 2013-03-09 02:39:30

codeMan是正確的。遍歷將訪問左側的每個節點。一旦它到達左邊的最後一個節點，它就開始沿着右側節點返回。這是深度優先搜索（DFS）遍歷。因此，每個節點只被訪問一次，算法運行在O（n）時間。快樂的編碼。

來源

2013-03-09 02:29:19 RouteMapper

遍歷通過二進制樹的所有節點在Java中

回答

相關問題