бинарное дерево со специальным свойством

Question

Существует двоичное дерево со специальным свойством, что все его внутренние узлы имеют val = 'N', а все листья имеют val = 'L'.Учитывая его предзаказ.создайте дерево и верните корневой узел.

каждый узел может иметь двух детей или не иметь детей

Answer 1

Рекурсия - ваш друг.

Tree TreeFromPreOrder(Stream t) {

    switch (t.GetNext()) {

        case Leaf: return new LeafNode;

        case InternalNode:
            Node n = new Node;

            n.Left = TreeFromPreOrder(t);
            n.Right = TreeFromPreOrder(t);
            return n;

        default:
            throw BadPreOrderException;
    }
}

Рассматривая ее как рекурсивный метод, становится легко увидеть, как делать другие вещи.

Например, скажем, мы хотели напечататьInOrder обход.Код будет выглядеть примерно так:

void PrintInorderFromPreOrder(Stream t) {

    Node n = new Node(t.GetNext());

    switch (n.Type) {

        case Leaf: return;

        case InternalNode:

            PrintInorderFromPreOrder(t);

            print(n.Value);

            PrintInorderFromPreOrder(t);

        default:
            throw BadPreOrderException;
    }
}

Кроме того, я хотел бы отметить, что это не настолько искусственно.Этот тип представления может фактически использоваться для экономии места, когда нам нужно сериализовать двоичное дерево: Эффективное хранение массива для двоичного дерева .

Answer 2

Просто основная идея: сохранить стек, где заголовок является «текущим» узлом, и последовательно прочитать строку, представляющую предзаказ.

Теперь, если вы встретите «L», то это означает, что «текущий» узел имеет дочерний лист, так что вы можете «переключиться» на правый дочерний элемент и возобновить построение соответствующего поддерева, толкая корень этого поддерево; если при обнаружении «L» у «текущего узла» уже есть два потомка, вытолкнуть элемент из стека.