Вывести уровень и узлы из бинарного дерева поиска
Мне нужно выполнить неупорядоченный обход бинарного дерева поиска, и мне нужно напечатать все узлы и уровень, на котором они находятся, но я не могу придумать, как это сделать.
Например:
Если у меня есть это бст, вывод будет таким:
4 #1
5 #0
9 #1
7 #2
10 #2
18 #3
Это пока то, что я получил:
Это структура, которую я использую:
struct tree {
int number;
tree *izq;
tree *der;
};
typedef struct tree *bst;
И это функция, которую я пытаюсь реализовать:
void printTree(bst node) {
if (node==NULL) {
return;
}
else {
if (node->left != NULL) {
printTree(node->left);
}
printf("%d", node->number);
if (node->right !=NULL) {
printTree(node->right);
}
}
}
У кого-нибудь есть идеи? Спасибо :)
мой ответ делает то, что вы ожидаете
Ответы 2
Я реализовал это с помощью Java, но я думаю, что вы можете легко преобразовать его в C:
private static void printWithLevels(TreeNode node) {
printWithLevels(node, 0);
}
private static void printWithLevels(TreeNode node, int level) {
if (node == null) return;
System.out.println(node.value + "(" + level + ")");
printWithLevels(node.left, level + 1);
printWithLevels(node.right, level + 1);
}
Чтобы мое решение было полным, это моя простая/быстрая реализация TreeNode:
private static class TreeNode {
int value;
TreeNode left;
TreeNode right;
TreeNode(int value, TreeNode left, TreeNode right) {
this.value = value;
this.left = left;
this.right = right;
}
}
предупреждение
struct tree {
int number;
tree *izq;
tree *der;
};
должно быть
struct tree {
int number;
struct tree *izq;
struct tree *der;
};
потому что случай, когда node равен NULL, проверяется в начале, вы можете упростить:
void printTree(bst node) {
if (node != NULL) {
printTree(node->izq);
printf("%d", node->number);
printTree(node->der);
}
}
добавление уровня:
void printTree(bst node, int lvl) {
if (node != NULL) {
printTree(node->izq, lvl + 1);
printf("%d #%d\n", node->number, lvl);
printTree(node->der, lvl + 1);
}
}
и вы звоните на корневой уровень с уровнем 0
Делаем полную программу:
#include <stdio.h>
#include <stdlib.h>
struct tree {
int number;
struct tree *izq;
struct tree *der;
};
typedef struct tree *bst;
void printTree(bst node, int lvl) {
if (node != NULL) {
printTree(node->izq, lvl + 1);
printf("%d #%d\n", node->number, lvl);
printTree(node->der, lvl + 1);
}
}
struct tree * mk(int v, struct tree * l, struct tree * r)
{
struct tree * t = malloc(sizeof(struct tree));
t->number = v;
t->izq = l;
t->der = r;
return t;
}
int main()
{
struct tree * r = mk(5, mk(4, NULL, NULL), mk(9, mk(7, NULL, NULL), mk(10, NULL, mk(18, NULL, NULL))));
printTree(r, 0);
}
Компиляция исполнения:
pi@raspberrypi:/tmp $ gcc -pedantic -Wall -Wextra c.c
pi@raspberrypi:/tmp $ ./a.out
4 #1
5 #0
7 #2
9 #1
10 #2
18 #3
@chill о, ты уже принял, я отредактировал, чтобы показать полную программу, да, это работает ^^
@chill Я рекомендую не скрывать указатель через определение типа, потому что это источник множества ошибок и делает код менее читаемым, лучше сделать, например typedef struct tree bst;
ооо последую твоему совету! Я только начинаю с C, и вы не представляете, насколько это полезно: D
@chill во многих случаях мы повторно используем имя структуры, например typedef struct tree { int number; struct tree *izq; struct tree *der; } tree;, но, конечно, это не обязательно. Обратите внимание, что внутри структура необходимо писать структурное дерево *, а не напрямую дерево*, потому что определение типа еще не известен.
Всем привет. Какой результат вы получаете в настоящее время? Если вы печатаете порядок или обход узла, вам нужно где-то выполнить сравнение (сравнить значение поиска с левым/правым узлом и следовать соответствующему?)