java - 迭代访问所有二叉树节点？

Question

我有一个二叉树，每个节点上都有一个单词。

在另一个类中，我需要一个接一个地访问节点，然后操作单词。从另一个类逐个访问节点的最佳方法是什么？

在我的 BinaryTree 类中，每个节点都有一个左子节点、右子节点和一个值(字符串)。我有三种方法，printinorder、insert 和 findnode。查找节点接收一个字符串并查看该字符串是否存储在任何节点值中。

public void printInOrder(Node node) {
    if (node != null) {
        printInOrder(node.left);
        System.out.println(node.value);
        printInOrder(node.right);
    }

我有另一个类，需要逐一获取节点，但我不确定从另一个类执行此操作的最佳方法是什么。我可以从类内部遍历树，但不能从不同的类遍历树。

Answer 1

遍历二叉树中所有节点的一种方法是执行以下操作，从最左边的节点开始并重复迁移到当前节点的 inorder successor :

1. 首先，尽可能向左走，不要从树上掉下来。这是您的第一个节点。

2. 要从一个节点到达下一个应访问的节点，请执行以下操作:

   1. 如果该节点有右子节点，则下降到右子节点，然后尽可能地不断下降到左子节点。您将到达下一个要访问的节点。
   2. 否则，重复从该节点向上走到其父节点，直到从左子节点向上走到其父节点。你最终到达的地方就是新节点。

这最终在所有节点上只花费 O(n) 时间，因此这是一种在节点之间迁移的非常快速的方法。

为了使其工作，您需要让每个节点存储一个父指针，或者必须维护从起始节点向下到当前节点的节点路径堆栈。然而，对于相当平衡的树，这比填充树中节点的整个列表并返回它更节省空间。

希望这有帮助!