Двоичное дерево из предзаказа цепочки

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, который имеет ссылки на левый и правый узлы. Затем все, что вам нужно сделать, это перемещаться по узлам.