Я пытался сделать функцию, которая печатает бинарное дерево (в данном случае это красно-черное дерево) в сторону консоли в красивой форме.Я нашел этот алгоритм в Интернете и адаптировал его к своему проекту.
Примечание: я видел много способов напечатать двоичное дерево на Java здесь, на SO и других веб-сайтах, но они в основном использовали Java Stringили какой-то другой язык высокого уровня, и в C иногда бывает очень сложно адаптировать код.Приведенный ниже код настолько хорош, насколько я понимаю, при печати бинарного дерева.
static void
rbt_display_treeview(Node *root, int depth, char *path, bool is_right)
{
const int spaces = 8;
if (root == NULL)
return;
depth++;
rbt_display_treeview(root->right, depth, path, true);
path[depth - 2] = 0;
if(is_right)
path[depth - 2] = 1;
if(root->left)
path[depth - 1] = 1;
printf("\n");
for (int i = 0; i < depth - 1; i++)
{
if (i == depth - 2)
printf("%c", is_right ? 218 : 192);
else if (path[i])
printf("%c", 179);
else
printf(" ");
for (int j = 1; j < spaces; j++)
if (i < depth - 2)
printf(" ");
else
printf("%c", 196);
}
printf(" %d\n", root->data);
for (int i = 0; i < depth; i++)
{
if (path[i])
printf("%c", 179);
else
printf(" ");
for (int j = 1; j < spaces; j++)
printf(" ");
}
rbt_display_treeview(root->left, depth, path, false);
}
Приведенный выше код называется:
// Red-Black tree is created and elements (int) are added
// Printing the tree
char *path = calloc(10000, sizeof(char));
if (!path)
return;
rbt_display_treeview(tree->root, 0, path, false);
printf("\n");
free(path);
Есть две проблемыхотя: Этот код будет пытаться получить доступ к индексу -1 из char *path, когда узел является корневым, и может быть переполнение char *path, если дерево действительно очень большое.Итак, вот мои первые два вопроса:
- Как предотвратить это поведение, когда узел является корневым?
- Насколько большим должно быть
pathтак что, если пользователь попытается напечатать действительно большое дерево, ему не хватит места в стеке, прежде чем переполнить буфер?
При тестировании я добавил следующие целые числа по порядку в своем красном-черное дерево:
[ 16, -34, 24, 43, 18, 20, 22, -21, 4, 28, 45, 24, -47, -43, 29, 14, -35, 32, 8, -9, -46, 41, 46, -3, 17, -32, 24, 50, -19, -48, 15, 20, 22, -50, -43, 18, -28, 12, -14, 19, 12, 44, 19, 23, 45, -38, 45, -15, -28, 15, 35, 16, -41, -25, 7, -20, -7, -13, -31, -5, -48, -37, -23, -36 ]
И оно вывело следующий вывод:
┌─────── 50
│
┌─────── 46
│ │
│ └─────── 45
│ │
│ └─────── 44
│
┌─────── 43
│ │
│ │ ┌─────── 41
│ │ │
│ └─────── 35
│ │
│ └─────── 32
│
┌─────── 29
│ │
│ │ ┌─────── 28
│ │ │
│ └─────── 24
│ │
│ │ ┌─────── 23
│ │ │
│ │ ┌─────── 22
│ │ │ │
│ └─────── 20
│ │
│ │ ┌─────── 19
│ │ │
│ └─────── 18
│ │
│ └─────── 17
│
16
│
│ ┌─────── 15
│ │
│ ┌─────── 14
│ │ │
│ │ └─────── 12
│ │
│ ┌─────── 8
│ │ │
│ │ │ ┌─────── 7
│ │ │ │
│ │ └─────── 4
│ │ │
│ ┌─────── -3
│ │ │
│ │ │ │ ┌─────── -5
│ │ │ │ │
│ │ │ ┌─────── -7
│ │ │ │ │
│ │ │ ┌─────── -9
│ │ │ │ │
│ │ │ │ └─────── -13
│ │ │ │ │
│ │ └─────── -14
│ │ │
│ │ │ ┌─────── -15
│ │ │ │ │
│ │ └─────── -19
│ │ │
│ │ └─────── -20
│ │ │
└─────── -21
│
│ ┌─────── -23
│ │
│ ┌─────── -25
│ │ │
│ ┌─────── -28
│ │ │
│ │ │ ┌─────── -31
│ │ │ │
│ │ └─────── -32
│ │ │
│ ┌─────── -34
│ │ │
│ │ │ ┌─────── -35
│ │ │ │
│ │ │ ┌─────── -36
│ │ │ │ │
│ │ │ │ └─────── -37
│ │ │ │
│ │ └─────── -38
│ │ │
│ │ └─────── -41
│ │
└─────── -43
│
│ ┌─────── -46
│ │
└─────── -47
│
└─────── -48
│
└─────── -50
Но потом я увидел некоторые строки, которые не должны быть напечатаны, например, те, что ниже цифр 22, 4, -7, -13, -15 и т. Д. Поэтому я добавил еще одно условие в последний цикл for, чтобы посмотреть, смогу ли я отфильтровать эти ненужные строки:
for (int i = 0; i < depth; i++)
{
if (path[i] && (root->left || i != depth -1)) /* Here */
printf("%c", 179);
else
printf(" ");
for (int j = 1; j < spaces; j++)
printf(" ");
}
На самом деле это так, ноЯ до сих пор не знаю почему.Также две строки над узлом -9 все еще печатаются, когда их там не должно быть.Это то, что у меня есть:
┌─────── 50
│
┌─────── 46
│ │
│ └─────── 45
│ │
│ └─────── 44
│
┌─────── 43
│ │
│ │ ┌─────── 41
│ │ │
│ └─────── 35
│ │
│ └─────── 32
│
┌─────── 29
│ │
│ │ ┌─────── 28
│ │ │
│ └─────── 24
│ │
│ │ ┌─────── 23
│ │ │
│ │ ┌─────── 22
│ │ │
│ └─────── 20
│ │
│ │ ┌─────── 19
│ │ │
│ └─────── 18
│ │
│ └─────── 17
│
16
│
│ ┌─────── 15
│ │
│ ┌─────── 14
│ │ │
│ │ └─────── 12
│ │
│ ┌─────── 8
│ │ │
│ │ │ ┌─────── 7
│ │ │ │
│ │ └─────── 4
│ │
│ ┌─────── -3
│ │ │
│ │ │ │ ┌─────── -5
│ │ │ │ │
│ │ │ ┌─────── -7
│ │ │ │
│ │ │ ┌─────── -9
│ │ │ │ │
│ │ │ │ └─────── -13
│ │ │ │
│ │ └─────── -14
│ │ │
│ │ │ ┌─────── -15
│ │ │ │
│ │ └─────── -19
│ │ │
│ │ └─────── -20
│ │
└─────── -21
│
│ ┌─────── -23
│ │
│ ┌─────── -25
│ │
│ ┌─────── -28
│ │ │
│ │ │ ┌─────── -31
│ │ │ │
│ │ └─────── -32
│ │
│ ┌─────── -34
│ │ │
│ │ │ ┌─────── -35
│ │ │ │
│ │ │ ┌─────── -36
│ │ │ │ │
│ │ │ │ └─────── -37
│ │ │ │
│ │ └─────── -38
│ │ │
│ │ └─────── -41
│ │
└─────── -43
│
│ ┌─────── -46
│ │
└─────── -47
│
└─────── -48
│
└─────── -50
- Как предотвратить печать этих двух строк?
PS: красныйРеализация черного дерева работает так же, как и любое другое красно-черное дерево.Вы также можете проверить это в других двоичных деревьях, так как я собираюсь запустить этот код в любом двоичном дереве.