Java中的遍历树

Question

我在遍历树时遇到了问题，并且输出如下。

如果树是这样的图像。 [http://www.java-forums.org/attachments/advanced-java/3355d1332821031t-traversing-binary-tree-root-each-branch-binarytree.png][1]

输出：

1. A，A1，A2，B1，B2
2. A，A1，B1，A2，B2
3. A，A1，B1，B2，A2
4. A，B1，A1，A2，B2
5. A，B1，A1，B2，A2
6. A，B1，B2，A1，A2

我知道这和前序遍历非常相似，但当节点分裂成左右节点时，preorder不会再输出父节点。有什么建议么？

这是我的代码，但我坚持打印出来。

public class BinaryTreeTest { 

/** 
* @param args the command line arguments 
*/ 
public static void main(String[] args) { 
    // TODO code application logic here 

    int countA = 0; 
    int countB = 0; 
    ArrayList listA = new ArrayList(); 
    ArrayList listB = new ArrayList(); 
    listA.add("A1"); 
    listA.add("A2"); 
    listA.add("A3"); 
    listB.add("B1"); 
    listB.add("B2"); 
    listB.add("B3"); 
    //listB.add("B1"); 
    Node root = new Node("START"); 
    constructTree(root, countA, countB, listA, listB); 

    //printInOrder(root); 
    //printFromRoot(root); 



} 


public static class Node{ 
    private Node left; 
    private Node right; 
    private String value; 
    public Node(String value){ 
     this.value = value; 
    } 
} 

public static void constructTree(Node node, int countA, int countB, ArrayList listA, ArrayList listB){ 
    if(countA < listA.size()){ 
     if(node.left == null){ 
      System.out.println("There is no left node. CountA is " + countA); 
      System.out.println("Created new node with value: " + listA.get(countA).toString() + " with parent, " 
        + node.value); 
      System.out.println(); 
      node.left = new Node(listA.get(countA).toString()); 
      constructTree(node.left, countA+1, countB, listA, listB);  
     }else{ 
      System.out.println("There is a left node. CountA + 1 is " + countA+1); 
      constructTree(node.left, countA+1, countB, listA, listB);  
     } 
    } 
    if(countB < listB.size()){ 
     if(node.right == null){ 
      System.out.println("There is no right node. CountB is " + countB); 
      System.out.println("Created new node with value: " + listB.get(countB).toString() + " with parent, " 
        + node.value); 
      System.out.println(); 
      node.right = new Node(listB.get(countB).toString()); 
      constructTree(node.right, countA, countB+1, listA, listB); 
     }else{ 
      System.out.println("There is a right node. CountB + 1 is " + countB+1); 
      constructTree(node.right, countA, countB+1, listA, listB); 
     } 
    } 
} 

Answer 1

你想要做的就是用深度优先算法遍历树。

你会在互联网上找到很多例子。取决于你如何制作你的树。如果你已经加载了一个对象树，你可以做一个递归算法从左到右传递每个孩子或者使用访问者模式。

首先，看看http://en.wikipedia.org/wiki/Tree_traversal#Depth-first