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

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 + " ");
}

但是，我给出了这个起始文件，其中树数据是三个数组:key[]、left[]和right[]，所以key[]元素是节点的数据，left和right元素是第i个节点的左子节点和右子节点的索引，所以节点根是keys[0]，左子节点keys[left[0]]和keys[right[0]。

我不确定如何（或者是否需要）使用Node和BinaryTree类将3个数组转换为二叉树。节点和BinaryTree类该何去何从？树序之外？在tree_orders内部但在TreeOrders外部？（抱歉“创意”命名惯例，不是我的）

我需要迭代三个数组来构建树节点吗？

我尝试实现下面的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），我以前也和树一起工作过，但是这个入门对我来说是一个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

多糟糕的设计啊，那些阵列。不管怎么说，如果你想要或者需要坚持下去，遍历树也不算太差：

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

对于其他遍历命令也是如此。我假设-1在left或right中表示没有偏斜。要打印整个树，请调用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