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

Question

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

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

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

从预序位串(通过输入给出)构建二叉树后，我还需要查找高度、路径长度以及二叉树是否完整。然而，我在进展到能够做到这一点时遇到了困难，因为我不知道如何开始在 Java 中实现预序位串 -> 二叉树转换。有人可以提示我如何开始从预序位字符串构建二叉树吗？

Answer 1

您可以从我不久前编写的这个简单程序开始，并对其进行调整以接受二进制字符串作为输入，而不是手动输入:

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

}