Как распечатать BST на C ++

Question

Моя программа на C ++ создает двоичное дерево поиска. Я знаю, как распечатать значения в предварительном порядке, после заказа и в порядке.

Однако я хочу сделать что-то более сложное. Я хочу распечатать значения так, как они будут выглядеть, если бы кто-то нарисовал дерево на бумаге. У него будет корень в центре вверху, слева от него и слева от него, а справа - справа и снизу. Остальные узлы будут нарисованы соответственно.

Как я могу это сделать?

Answer 1

Эта статья содержит код для того, что вам нужно, кажется:

альтернативный текст http://www.cpp -programming.net / wp-content / uploads / 2007/12 / ascii_tree.jpg

Редактировать: этот сайт перешел в автономный режим

Вот еще один , исследующий некоторые другие варианты.

Answer 2

Вот примерный псевдокод для этого. Основная идея состоит в том, чтобы пройтись по дереву послойно, печатая все узлы в каждом слое в одну строку. Каждый узел разделен вдвое больше места, чем узлы под ним. Поскольку дерево не все одинаковой глубины, оно искусственно заполнено виртуальными узлами, чтобы занять пустые места, где узлов не существует.

measure the depth of the tree, call that D
have two queues, called Q1 and Q2
enque the top node of the tree in Q1
for (i = D; --i>=0; ){
  foreach node in Q1 {

    on first iteration of this inner loop, print 2^i - 1 spaces,
    else print 2^(i+1) - 1 spaces.

    if node == null print blank
    else print node.value

    if node.left exists enque node.left in Q2
    else enque null in Q2

    if node.right exists enque node.right in Q2
    else enque null in Q2
  }
  copy Q2 to Q1
  clear Q2
  print end-of-line
}

Каждое печатное место является шириной одного числового поля. Предположим, что дерево имеет глубину D = 4. Тогда печать идет так:

// it looks like this, and the space sequences are
i = 3: -------n 7
i = 2: ---n-------n 3 7
i = 1: -n---n---n---n 1 3 3 3
i = 0: n-n-n-n-n-n-n-n 0 1 1 1 1 1 1 1

Answer 3

    void print(node *p,int start)
    {
        start++;
        if (p->right != NULL)
        {
            print(p->right,start);
        }
        for (int i = 0; i <= start; i++)
        {
            cout<<"    ";
        } 
        cout << p->value<<endl;
        if (p->left != NULL)
        {
            print(p->left, start);
        }
    }

Answer 4

Одним из способов является использование graphviz. В частности, используйте его «точечную» программу, но получить вывод, который будет выглядеть точно так, как вы описали, может быть невозможно.

Answer 5

ну, в терминале это сложно ... так как может не подойти. Но есть библиотеки для рисования графиков, которые могут сделать красивые картинки для вас. Существует графвис, который является одним из самых популярных.

редактирование: если вы действительно просто хотите напечатать текст, у graphvis есть язык разметки, который пользователь может передать в graphvis, который, в свою очередь, создает красивые картинки.