二叉搜索树上的预购遍历

对于二叉搜索树：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

二叉搜索树上的预购遍历

回答

相关问题