二叉搜索樹上的預購遍歷

對於二叉搜索樹：7是根1是左孩子，10是右孩子。二叉搜索樹上的預購遍歷

         7 
             1 10

我試過調試這個函數，看看它是如何工作的，我似乎無法理解一件事。在函數檢查並發現1的左側子項和右側子項都爲空後，它將轉到節點10，然後檢查右側子項是否爲空。有人可以解釋的遞歸模式，爲什麼節點1

private void preOrderTraversal(Node node) 
{  
    if(node == null) return; 
    System.out.println(node.data); 
    preOrderTraversal(node.leftChild); 
    preOrderTraversal(node.rightChild); 
}

來源

2014-12-29 Rez88

不要打擾，重複使用[現有工具]（http://docs.guava-libraries.googlecode。com/git-history/release/javadoc/com/google/common/collect/BinaryTreeTraverser.html） – fge

@fge雖然現有的工具可以幫助你很多，特別是在製作應用程序時，建立自己的東西非常有教育意義。 – RobAu

的方法preOrderTraversal（調用節點= 1作爲一個參數，即與左子）確實存在的初步檢查後，該方法不退出，但那麼控制流將跳回到調用它的方法，這又是preOrderTraversal（用Node = 7，根作爲參數調用）。所以一切都很好。

添加這些行跟蹤代碼，你會
明白我的意思，一切都會變得清晰。

private void preOrderTraversal(Node node) 
{ 
    System.out.println("Now in preOrderTraversal with " + 
         (node==null ? "null." : node.data + ".")); 
    if(node == null) { 
     System.out.println("Done. Exit 1 taken."); 
     return; 
    } 
    System.out.println(node.data); 
    preOrderTraversal(node.leftChild); 
    preOrderTraversal(node.rightChild); 
    System.out.println("Done. Exit 2 taken."); 
}

來源

2014-12-29 23:20:26

謝謝你。但是，如何/爲什麼會跳回到7節點的方法。當然，沒有調用遞歸函數的根是7？ – Rez88

preOrderTraversal應該首先與節點7一起調用，然後它將打印數據7，然後左邊的孩子，然後右邊。調用堆棧可能類似於[7]（第一次調用）[71]（左側子節點）[71null]（左側子節點左側子節點）[71null]（左側子節點右側子節點），然後繼續執行71節點，變爲[7 10 ]等等 – dtortola

歡迎遞歸的世界裏，所以咱們的Calculating Factorial

Resursion

一個非常簡單的例子開始現在你看到的方法調用堆棧已經建立，斷裂點這個遞歸factorial(0) whose result is 1這是第一個值，我們在這一點上程序不會退出獲得

現在，而不是第五呼叫將結果(i.e. 0)返回到第四次調用等等，以便您可以得到最終結果。而一旦任何方法返回它得到了從遞歸的堆棧中刪除結果調用

現在來到您遍歷樹

System.out.println(node.data); // prints 7 for first time 
preOrderTraversal(node.leftChild); // Now the function is called with 7->left 
preOrderTraversal(node.rightChild);// here is is called with 7->right

所以遞歸調用同樣的方式堆棧中創建的例子和計劃，而不是從1退出會返回到調用誰在它的方法（即7->左）現在（7->右）將在外行之三執行

現在遞歸MS

有人在電影院問你，你坐在哪一行，你不想來算，所以你在你的面前，他們正坐在哪一行問的人，知道你會回答一個大於的答案。前面的人會問他們前面的人。這將繼續發生，直到字到達前排，並且很容易迴應：「我在第1排！」從那裏，正確的消息（每行增加一個）最終將返回到詢問的人。

來源

2015-02-10 15:30:15

二叉搜索樹上的預購遍歷

回答

相關問題