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

Answer 1

您可以实现三种类型的二叉树遍历：

例：

考虑以下二叉树：

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

Answer 2

codeMan是对的。 遍历将访问左侧的每个节点。 一旦它到达左侧的最后一个节点，它就开始沿着右侧节点返回。 这是深度优先搜索（DFS）遍历。 因此，每个节点仅被访问一次，并且算法在O（n）时间内运行。 快乐的编码。