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

Question

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

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

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

Answer 1

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

alt text http://www.cpp-programming.net/wp-content/uploads/2007/12/ascii_tree.jpg

Edit: этот сайт ушел в оффлайн

Вот another one изучает другие варианты.

Answer 2

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

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

Answer 3

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

Answer 4

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

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 5

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