Бинарное дерево на С

[Маньяк]

Бинарное дерево на С

Помогите пожалуйста сделать Бинарное дерево на языке С, под компилятор Dev_cpp в бинарное дерево надо только добавлять значения. Заранее спасибо!

 

[csbwalker]

Так, а бинарное дерево - в смысле обычное int'овое когда сравнивается с уже существующими числами и в зависимости от этого кладётся куда-либо, или же там просто какие-то данные в каждом элементе хранятся(если да, то какие)?

 

[Маньяк]

ну к примеру первое число 10, то 9 запишется в левую часть, а 11 в правую

 

[Маньяк]

Да да сравнивается с уже существующими числами.

 

[csbwalker]

#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.
Реализована операция добавления и вывод дерева на экран, что бы посмотреть правильность выполнения операции добавления.
Вродь всё!

 

[Маньяк]

Спасибо большое!