中序遍历二叉树

Question

我在学习java。我在某处看到这段代码。以下代码是否正确遍历它？是否正确调用了结果列表？它会正确附加吗？

public void traverse(Node<T> input, List<T> resultlist) {
   if (input != null) {
      traverse(input.getLeftNode(), resultlist)

      resultlist.add(input.getValue())

      traverse(input.getRightNode(), resultlist)
   }
}

Answer 1

通过询问它是否确实进行了中序遍历（这是否做了它应该做的事情），我猜你只是不明白其中的区别在遍历之间...

入门：

为了真正理解这一点，你需要理解数据结构的一个重要方面：递归。这是你需要掌握的。可能需要一点时间，在尝试不同的练习后..它会点击。

这是一个开始的资源：

http://www.programmerinterview.com/index.php/recursion/explanation-of-recursion/

现在回到你的树遍历问题，典型的约定如下：

预购：

traversalFunction(Node)
   doStuffWithNode(Node)   //prechild traversal
   traversalFunction(Node.left)
   traversalFunction(Node.right)

有序

traversalFunction(Node)
   traversalFunction(Node.left)
   doStuffWithNode(Node)   //within child traversal
   traversalFunction(Node.right)

Post-订单:

traversalFunction(Node)
   traversalFunction(Node.left)
   traversalFunction(Node.right)
   doStuffWithNode(Node)  //post child traversal

所以回答你的问题...如果你有在左右遍历之间的节点上执行操作的方法那么是它是一个有序的遍历。那就是你在做什么。

您可以在此处找到有关遍历的更多信息： https://en.wikipedia.org/wiki/Tree_traversal

现在关于您其余代码的正确性，我不确定，因为您确实没有在您的节点 class 或任何东西上输入任何信息。

中序遍历二叉树

In order traversal binary tree

java

binary-tree