如何使用来自 3 个数组的数据实现二叉树的中序、前序和 post 序遍历

Question

我明白二叉树可以这样轻松实现：

class Node {
    int key;
    Node left, right;
    public Node(int item) {
        key = item;
        left = right = null;
    }
}

class BinaryTree {
    Node root;
    public BinaryTree() {
      root = null;
    }
}

另外我想到的遍历方法是：

void printInorder(Node node) {
    if (node == null) return;
    printInorder(node.left);
    System.out.print(node.key + " ");
    printInorder(node.right);
}

void printPreorder(Node node) {
    if (node == null) return;
    System.out.print(node.key + " ");
    printPreorder(node.left);
    printPreorder(node.right);
}

void printPostorder(Node node) {
    if (node == null) return;
    printPostorder(node.left);
    printPostorder(node.right);
    System.out.print(node.key + " ");
}

但是，我得到 this starter file 其中树数据位于 3 个数组中：key[]、left[] 和 right[]，因此 key[] 元素是节点的数据，左而right元素是第i个节点的左右子节点的索引，所以节点根是keys[0]，左子keys[left[0]]和keys[right[0].

我不确定如何（或者如果我需要）使用 Node 和 BinaryTree 类将 3 个数组转换为二叉树。 节点和二叉树类应该去哪里？在tree_orders之外？在 tree_orders 之内但在 TreeOrders 之外？（抱歉 "creative" 命名约定，不是我的）

是否需要遍历三个数组来构建树节点？

我尝试实现下面的 insert(int data) 和 insert(Node n, int data) 方法将数组转换为节点，但它似乎没有填满树。

Node insert(int data) {
     root = insert(root, data);
     return node;
}

Node insert(Node node, int data) {
     if (node == null) {
          node = new Node(data)         
     }
     else {
          if (node.left == null) insert(node.left, data);
          else insert(node.right, data);
     }
     return node;
}

我开始学习编程才 5 个月（选择 Java）并且我之前使用过 Trees，但是这个初学者对我来说是一个 OOP 难题，我需要重新检查我的 OOP知识.

这是输入和输出应如何显示的示例（-1 = 空节点/5 = 给定节点数）：

Input:
5
4 1 2
2 3 4
5 -1 -1
1 -1 -1
3 -1 -1

Output:
1 2 3 4 5
4 2 1 3 5
1 3 2 5 4

Answer 1

你的问题不是很清楚。标题询问遍历，但您也担心读取 100.000 个节点和给节点命名，以及 iteration/recursion 缓慢。真是一团糟！

你展示的遍历逻辑乍一看没问题。

假设您想使用来自三个数组的节点 class 构建一个二叉树，您可以这样做（您不需要 BinaryTree class，它只包含根节点） :

class TreeMaker {

    private int[] keys, left, right;

    TreeMaker(int[] keys, int[] left, int[] right) {
        this.keys = keys;
        this.left = left;
        this.right = right;
    }

    public Node make() {
        return makeNode(0);
    }

    private Node makeNode(int index) {
        if (index < 0 || index >= keys.length) {
            return null;
        }
        Node node = new Node(keys[index]);
        node.left = makeNode(left[index]);
        node.right = makeNode(right[index]);
        return node;
    }
}

我认为 100.000 个节点并不算多。让它不应该在内存方面或速度方面造成问题（除非你开始进行复杂的搜索、索引或其他有趣的事情）。注意：在看到对 Thread 运行ning 这段代码施加的人为限制后，这可能是个问题。

您不必将节点存储在命名变量中或以其他方式命名它们。只需确保二叉树节点引用正确的 children 就足够了。

编辑：关于您的入门文件

这完全是废话：

while (!tok.hasMoreElements())
            tok = new StringTokenizer(in.readLine());

首先，StringTokenizer 是遗留的 class，不应再使用（对于新代码）。 String.split() 是现在使用的替代方法。此外，为每一行创建一个新的 StringTokenizer 实例是不必要且浪费的。您一定要使用此代码 as-is 吗？

我知道您应该从命令行输入树数据吗？为什么不从文件中读取数据，这样您只需输入一次呢？

您应该如何输入有效的二叉树？ left[] 和 right[] 中的值实际上是 key[] 的索引，因此您必须在键入时弄清楚每个 child 节点将存储在哪个索引中？疯狂的事情。给你布置这项任务的人有点虐待狂。有很多更好的方法可以将二叉树存储在一个数组中，例如 this lecture.

这也很了不起：

static public void main(String[] args) throws IOException {
        new Thread(null, new Runnable() {
                public void run() {
                    try {
                        new tree_orders().run();
                    } catch (IOException e) {
                    }
                }
            }, "1", 1 << 26).start();
}

此处 class tree_orders（原文如此）在堆栈大小为 1 << 23 的线程中为运行。此堆栈大小提示 Java 运行时间将跟踪嵌套方法调用所需的内存限制为 8388608 字节。这可能是为了让你在递归实现时达到极限，或者确保你不会（我还没弄清楚是哪一个）。

为了在此示例中应用我的 TreeMaker，您可以在 run() method:

public void run() throws IOException {
    TreeOrders tree = new TreeOrders();
    tree.read();

    TreeMaker treeMaker = new TreeMaker(tree.keys, tree.left, tree.right);
    Node root = treeMaker.make();

    printInorder(root);
    printPreorder(root);
    printPostorder(root);
}

但我的印象是你应该只实现三个给定的方法并对现有数据结构（3 个数组）进行遍历。

Answer 2

多么糟糕的设计，那些数组。不管怎样，如果你想或需要坚持下去，遍历树也不错:

void printInorder(int index) {
    if (index == -1) return;
    printInorder(left[index]);
    System.out.print(keys[index] + " ");
    printInorder(right[index]);
}

其他遍历顺序同理。我假设 left 或 right 中的 -1 表示没有后代。要打印整棵树，请调用 printInOrder(0) 因为根在索引 0.

编辑：我相信您的示例给出了以下数组：

    int[] keys = { 4, 2, 5, 1, 3 };
    // indices 0..4
    int[] left = { 1, 3, -1, -1, -1 };
    int[] right = { 2, 4, -1, -1, -1 };

有了这些，调用 printInorder(0) 然后 System.out.println() 打印：

1 2 3 4 5

如何使用来自 3 个数组的数据实现二叉树的中序、前序和 post 序遍历

How to implement in-order, pre-order and post-order traversals of a binary tree with data from 3 arrays

java

algorithm

binary-tree

tree-traversal