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

Question

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

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

在我的币树类中，每个节点都有一个左子、右子和一个值（String）。我有三个方法，printinorder-，插入和find节点。查找节点接收一个字符串，并查看该字符串是否存储在任何节点值中。

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

我有另一个类，需要一个接一个地获取节点，但是我不确定从另一个类中获取的最佳方式是什么。我可以从类内部遍历树，但不能从不同的类遍历。

Answer 1

假设你有一个树类，先写一个遍历树的方法(广度/深度搜索)。在遍历的每个节点上，假设您的节点是某种类型的对象，在它的一个变量中保存一个单词，访问该节点并更改存储的单词。基本上，在你的二叉树类中编写函数，让你这样做，并在你的其他类中调用它们。

Answer 2

看templatetypedef的回答，这是更高效的方法。我所介绍的方法的优点是，它不需要对现有的节点类进行任何修改，并且使用与PrintInOrder相同的模式。它只依赖于节点类的公共属性，所以应该可以从一个单独的类中使用。

public List<Node> nodes GetAllNodes(Node root) {
    List<Node> nodes = new ArrayList<Node>();
    if (root != null) {
        nodes.addAll(GetAllNodes(root.left));
        nodes.add(root);
        nodes.addAll(GetAllNodes(root.right));
    }
    return nodes;
}

我没有编译或测试这个，所以可能有错误。

Answer 3

遍历二叉树中所有节点的一种方法是执行以下操作，这将启动最左侧的节点并重复迁移到当前节点的顺序后继节点：

>

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

要从一个节点转到下一个应该访问的节点，请执行以下操作：

如果节点有右子节点，则下降到
1. 右侧子节点，然后尽可能连续下降到左侧子节点。您在要访问的下一个节点结束。
否则，请反复向上从节点
2. 向上走到其父节点，直到从左子节点向上走到其父节点的边。你最终到达的地方是新节点。

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

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

希望这有帮助！