java - 来自预序位串的二叉树

Question

我需要从预排序位串（通过管道传输到流中的标准输入）构建二叉树，我想知道我对此的理解是否正确。

如果我有一个 11110001000 的预购位串（其中 1 表示内部节点，0 表示外部节点），会产生这样的二叉树吗？

        1
       / \
      1   0
     / \
    1   1
   / \ / \
  1  00   0
 / \
0   0

从前序位串（通过输入给出）构建二叉树后，我还需要找到高度、路径长度以及二叉树是否完整。但是，我在前进到能够做到这一点时遇到了麻烦，因为我不知道如何开始在 Java 中实现预排序位串 -> 二叉树转换。任何人都可以提供有关我如何开始从预购位串构建二叉树的提示吗？

Answer 1

你可以从这里开始。如果你懂 c++，这篇文章也会很有用。

主要思想是有一个 Node 类，它具有对左节点和右节点的引用。然后，您需要做的就是浏览节点。

Answer 2

您可以从我前段时间制作的这个简单程序开始，并将其修改为接受二进制字符串作为输入，而不是手动输入：

import javax.swing.JOptionPane;

class Node {
    int info;
    Node fs;
    Node fd;
}

class BinaryTree {

    public static void main(String[] args) {

        Node tree = null;
        tree = insertRecursivePreorder(tree);

    }

    static Node insertRecursivePreorder (Node n) {
      String input = JOptionPane.showInputDialog("Insert node, 0 to end: \n");
      int dato = Integer.parseInt(input);

      if (dato == 0) {
          n=null;
      } else {
          n=new Node();
          n.info=dato;
          n.fs=insertRecursivePreorder(n.fs);
          n.fd=insertRecursivePreorder(n.fd);
      }
      return n;
    }

}