Как распечатать BST в C ++
-
19-09-2019 - |
Вопрос
Моя программа C ++ создает двоичное дерево поиска. Я знаю, как распечатать значения в предварительном заказе, после порядка и по заказу.
Тем не менее, я хочу сделать что -то более сложное. Я хочу распечатать значения так, как они смотрят, если кто -то нарисовал дерево на бумаге. У него будет корень в центре наверху, он левый ребенок вправо и слева от него, и он находится в правом ребенке, справа и справа от него. Остальные узлы будут нарисованы соответственно.
Как я могу это сделать?
Решение
эта статья Содержит код для того, что вам нужно, кажется:
Alt Text http://www.cpp-programming.net/wp-content/uploads/2007/12/ascii_tree.jpg
РЕДАКТИРОВАТЬ: этот сайт снялся в автономном режиме
Вот Еще один Изучение некоторых других вариантов.
Другие советы
Вот приблизительный псевдокод, чтобы сделать это. Основная идея-пройти по слону дерева, распечатать весь узел в каждом слое на одной линии. Каждый узел разделен на два раза больше места, чем узлы под ним. Поскольку дерево не со всей однородной глубиной, оно искусственно сочетается с виртуальными узлами, чтобы заняться пустыми пространствами, где узлов не существует.
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
Одним из способов является использование Graphviz. В частности, используйте его программу «DOT», но получение вывода, чтобы выглядеть точно так же, как вы описываете, может быть невозможным.
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);
}
}
Ну, в терминале это сложно ... так как это может не подходить. Но есть библиотеки рисования графиков, которые могут сделать для вас хорошие снимки. Есть график, который является одним из самых популярных.
РЕДАКТИРОВАТЬ: Если вы действительно просто хотите печатать текст, у Graphvis есть язык разметки, который пользователь может передать Graphvis, который, в свою очередь, делает хорошие картинки.