0

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

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

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

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

我有另一个班级，需要一个接一个地到达节点，但我不确定从另一个班级做这件事的最佳方法是什么。我能够从类内遍历树，但不能从不同的类遍历树。

4

4 回答 4

1

遍历二叉树中所有节点的一种方法是执行以下操作，它从最左边的节点开始并反复迁移到当前节点的中序后继节点：

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

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

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

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

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

希望这可以帮助！

于 2013-01-11T00:31:43.413 回答
0

假设您有一个树类，首先编写一个首先遍历树的方法（广度/深度搜索）。在遍历中的每个节点上，假设您的节点是某种类型的对象，其中一个变量中包含一个单词，请访问该节点并更改存储的单词。基本上在您的二叉树类中编写函数让您执行此操作，并在您的其他类中调用它们。

于 2013-01-10T23:51:10.920 回答
0

对于搜索：

您可以将树排序为二叉搜索树。或者在构建树时，构建二叉搜索树。这将是最好的搜索方式。O(logn).

搜索应该在您的findNode(String value)方法中实现

或者您在执行搜索时遇到问题？

于 2013-01-11T00:20:09.457 回答
0

阅读 templatetypedef 的答案，这是一种更有效的方法。我介绍的方法的优点是它不需要对现有的 Node 类进行任何更改，并且使用您已经用于 PrintInOrder 的相同模式。它仅依赖于 Node 类的公共属性，因此应该可以从单独的类中使用。

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;
}

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

于 2013-01-11T00:30:35.310 回答