Код:
#include <stdio.h>
#include <stdlib.h>
struct treeNode
{
int value;
struct treeNode *left;
struct treeNode *right;
};
/* Функция, создающая ветвь дерева и устанавливающая значения её параметров */
struct treeNode *treeCreate(int n)
{
struct treeNode *nel;
/* Выделяем память для ветви */
nel = malloc(sizeof(struct treeNode));
/* Если удалось выделить - записываем туда значения параметров */
if(nel != NULL)
{
nel->left = NULL;
nel->right = NULL;
nel->value = n;
}
/* Возвращаем адрес созданной ветви (или NULL если создать не удалось) */
return nel;
}
/* Рекурсивная функция, которая добавляет ветвь в дерево */
void treeAdd(struct treeNode *root, int n)
{
/* Определяем, в какую ветвь нужно добавить число - в левую или правую */
if(n <= root->value)
{
/* Если в левую */
/* Если левой ветви нет - создаём её и записываем в ней число,
иначе - продолжаем рекурсию с неё */
if(root->left == NULL)
root->left = treeCreate(n);
else
treeAdd(root->left, n);
} else
{
/* Если в правую - действия аналогичны левой */
if(root->right == NULL)
root->right = treeCreate(n);
else
treeAdd(root->right, n);
}
}
/* Рекурсивная функция, выводящая ветви дерева на экран */
void treeNodePrint(struct treeNode *root, int m, char ch)
{
int i;
/* Если указатель ревен нулю - конец рекурсии, если нет - выполняем вывод */
if(root != NULL)
{
/* Выводим отступ */
for(i = 0; i < m; i++)
putchar(' ');
/* Выводим значение текущего элемента */
printf("|-%c: %d\n", ch, root->value);
/* Запускаем рекурсивный вывод для левой, а затем для правой ветвей */
treeNodePrint(root->left, m + 2, 'L');
treeNodePrint(root->right, m + 2, 'R');
}
}
/* Функция, выводящая всё дерево на экран */
void treePrint(struct treeNode *root)
{
int i;
/* Печатаем верхний разделитель */
for(i = 0; i < 20; i++)
putchar('-');
putchar('\n');
/* Печатаем дерево начиная с корня */
treeNodePrint(root, 0, 'T');
/* Печатаем нижний разделитель */
for(i = 0; i < 20; i++)
putchar('-');
putchar('\n');
}
/* Функция запроса дальнейших действий */
int ask()
{
int d;
printf("What we should to do?\n");
printf("0. exit;\n");
printf("1. print tree;\n");
printf("2. add new node.\n");
printf("Please, enter answer: ");
scanf("%d", &d);
return d;
}
int main()
{
struct treeNode *root;
int n;
/* Запрашиваем значение корня */
printf("Enter value of root: ");
scanf("%d", &n);
/* Создаём корень */
root = treeCreate(n);
/* Если не удалось создать корень - выходим */
if(root == NULL)
{
printf("Error!");
return 1;
}
/* Бесконечный цикл с запросом и выполнением действий */
while(1)
{
switch(ask())
{
case 1:
treePrint(root);
break;
case 2:
printf("Enter value to add: ");
scanf("%d", &n);
treeAdd(root, n);
break;
default:
return 0;
}
}
}
Вот, тут все элементы хранят числа типа
int.
Реализована операция добавления и вывод дерева на экран, что бы посмотреть правильность выполнения операции добавления.
Вродь всё!