想不通前序遍歷

public void traverse(ListItem root) { 
     //preorder traversal - going to left childs first 
     ListItem focusNode; 
     ListItem parentNode; 
     if (root == null) { 
      System.out.println("Empty tree"); 
     } else { 
      if (root.leftLink != null) { 
       System.out.println(root.getValue()); 
       parentNode = root; 
       while (parentNode.leftLink != null) { 
        focusNode = parentNode.leftLink; 
        System.out.println(focusNode.getValue()); 
        parentNode = focusNode.leftLink; 
       } 
      } 
     } 
    }

所以這就是我到目前爲止。我認爲這能夠打印出樹的左邊的所有節點，但我還沒有找到一種方法來避免更好的術語跳回到先前的條目，並測試是否存在左節點，如果不是去一個正確的節點。想不通前序遍歷

來源

2016-02-17 Giancarlo Gatti

你可以嘗試遞歸或堆棧。 – Thomas

使用遞歸，你可以做這樣的事情：

public void traverse(ListItem node) { 
    if (node== null) { 
     System.out.println("Empty tree"); 
    } else { 
     if (node.leftLink != null) { 
      traverse(node.leftLink); 
     } 
     if (node.rightLink != null) { 
      traverse(node.rightLink); 
     } 

     System.out.println(node.getValue());    
    } 
}

這將檢查左子是否存在和遞歸調用的左子樹（子），則確實爲右孩子相同的方法。在所有的孩子打印完畢後，節點將自己的值打印出來。

例子：

假設下面的樹

A 
/\ 
    B C 
/\ \ 
D E F

調用traverse(A)將導致folling輸出：

D 
E 
B 
F 
C 
A

來源

2016-02-17 14:03:24 Thomas

我沒有研究過遞歸，但我看到了類似的代碼在YouTube上，我得到，你必須檢查是否左側和右側的子樹，然後使用預序方法，但然後像這樣：遍歷（node.leftLink）;在它後面沒有實現，它遵循預訂方法... –

@GiancarloGatti我沒有得到你的評論，但基本上你再次調用'遍歷'左邊，然後右邊的孩子。調用堆棧將爲您處理訂單。 – Thomas

如果您刪除了輸出「空樹」的必要性，那麼您可以消除在遞歸算法中執行的兩個空檢查之一。傳統上，您在不打電話之前檢查何時被叫。 – Neil

想不通前序遍歷

回答

相關問題