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