java - 如何使用来自 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 + " ");
}

但是，我得到了 this starter file其中树数据在3个数组中:key[]、left[]和right[]，所以key[]元素是节点的数据，left和right元素是第i个节点的左右 child 的索引, 所以节点根是 keys[0], 左子 keys[left[0]] 和 keys[right[0].

我不确定如何(或是否需要)使用 Node 和 BinaryTree 类将 3 个数组转换为二叉树。 Node 和 BinaryTree 类应该去哪里？在 tree_orders 之外？在 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;
}

我开始学习编程(选择 Java)才 5 个月，之前我曾使用过 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 个节点和给节点命名，以及迭代/递归缓慢。真是一团乱麻!

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

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

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 个节点并不算多。让它不应该在内存方面或速度方面造成问题(除非你开始进行复杂的搜索、索引或其他有趣的事情)。注意:在看到对运行此代码的线程施加的人为限制后，这可能是一个问题。

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

编辑:关于您的入门文件

这完全是废话:

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

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

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

您应该如何输入有效的二叉树？ left[] 和 right[] 中的值实际上是 key[] 的索引，因此您必须在键入时弄清楚每个子节点将存储在哪个索引中？疯狂的事情。给你布置这项任务的人有点虐待狂。有很多更好的方法可以将二叉树存储在单个数组中，例如参见 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();
}

这里是类 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 个数组)进行遍历。