首页 文章

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

提问于
浏览 次
0

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

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

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

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

我有另一个类，需要逐个进入节点，但我不确定从另一个类做到最好的方法 . 我可以从类中遍历树，但不能从不同的类中遍历 .

java data-structures binary-tree

4 回答

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

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

    回复于
  • 0

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

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

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

    • 如果节点有一个正确的孩子，则下降到右孩子，然后尽可能连续下降到左孩子 . 您将在下一个要访问的节点结束 .

    • 否则，重复从节点向上走到它的父节点，直到从左子节点到其父节点的边缘向上走 . 最终的结果是新节点 .

    这最终只占用所有节点的O（n）时间，因此在节点之间进行迁移是一种非常快速的方法 .

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

    希望这可以帮助！

    回复于
  • 0

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

    回复于
  • 1

    搜索：

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

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

    或者你有问题实施搜索？

    回复于

相关问题