遍历通过二进制树的所有节点在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中

回答

相关问题