来自预序位串的二叉树

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

}

Answer 2

您可以从此处开始。如果您了解 C++，请阅读这篇文章 也会很有用。

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