Загвоздка с деревом, динамические структуры данных - C (СИ)

Узнай цену своей работы

Формулировка задачи:

Всем доброго времени суток.
Столкнулся с такой проблемой. В языке С новичок и нужно написать программу с динамическими структурами данных. Программу, реализующую структуру данных и методы работы с ней, а также дополнительный метод обработки (1) Элементом структуры должно быть целое число. (1) Двоичное дерево, минимальное значение, пример результата = 57, для следующих элементов 10, 5, 6, 23, 11, 2. Также нужно вставить обязательно в программу следующие блоки кода. 1) Вставка элемента
void tree_insert(
   node* root,
   int x
);
2) Печать всех элементов
void tree_print(
   node* root
);
3) Удаление элемента
void tree_remove(
   node* root,
   int x
);
4) Удаление всех элементов
void tree_erase (
   node* root
);
Смог написать для списка, но на дереве загвоздка. Вот пример списка.
#include <stdio.h>
 
#include <stdlib.h>

struct node {
    int data;
    struct node * next;
};
 
void CreateList(node * list) {
    list->next=NULL;
};
 
void list_insert(node *list, int x) {
    node *uzel;
 
    if (list->next == NULL) {
 
        list->next = (node *) malloc(sizeof(uzel));
        list->next->data = x;
        list->next->next = NULL;
        return;
 
    };
 
    if (list->next->data >= x) {
 
        uzel = (node *) malloc(sizeof(uzel));
        uzel->data = x;
        uzel->next = list->next;
        list->next = uzel;
 
    } else {
        list_insert(list->next, x);
    }
};
 
void list_remove(node *list, int x) {
 
    node * tmp;
 
    if(list->next->data == x) {
 
        tmp = list->next->next;
        free(list->next);
        list->next = tmp;
 
    } else {
        list_remove(list->next, x);
    }
};
 
void list_erase(node *list){
    node * tmp;
 
    tmp = list->next;
    int ms[100]={0};
    int ix=0;
    while(tmp !=NULL) {
        node* next=tmp->next;
        free(tmp);
        tmp=next;
    }
    list->next=NULL;
 
}
 
void list_print(node *list) {
    node * tmp;
    if(list->next == NULL)  {
        printf("List is empty");
        return;
    }
 
    tmp = list->next;
    while(tmp !=NULL) {
        printf("%d ",tmp->data);
        tmp=tmp->next;
    };
};
 
int difference(node *list) {
    int i = 0 ;
    node * tmp = list;
 
    int max=tmp->next->data;
    int min=tmp->next->data;
 
    while(tmp->next != NULL) {
        if(tmp->next->data >max){
            max=tmp->next->data;
        }
        if(tmp->data <min){
            min=tmp->data;
        }
 
        i++;
        tmp=tmp->next;
    };
    return max-min;
};
 
int main () {
 
    node list;
    CreateList(&list);
    int i=0;
    while(i<15){
        list_insert(&list, rand() % 111);
        i++;
    }
    printf("\nPrinting all of the elements....\n");
    list_print(&list);
 
    list_remove(&list, 7);
    list_remove(&list, 41);
    list_remove(&list, 44);
    list_remove(&list, 54);
    list_remove(&list, 62);
 
    printf("\n\nPrinting all of the elements after removing 5 of them....\n");
    list_print(&list);
    
    printf("\n\nThe difference between maximum and minimum : %d\n", difference(&list));

    return 0;
};

Решение задачи: «Загвоздка с деревом, динамические структуры данных»

textual
Листинг программы
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
 
typedef struct _node {
    int x;
    struct _node* left;
    struct _node* right;
} node;
 
node* tree_insert(node** root, int x);
void  tree_remove(node** root, int x);
void  tree_print(FILE* _out, const node* root);
void  tree_erase(node* root);
 
 
int main(void){
    int   i;
    node* tr = NULL;
 
    for(i = 0; i < 30; ++i)
        tree_insert(&tr, rand() % 10);
 
    tree_print(stdout, tr);
    putchar('\n');
 
    tree_remove(&tr, 5);
    tree_remove(&tr, 6);
    tree_remove(&tr, 7);
    tree_print(stdout, tr);
    tree_erase(tr);
    return 0;
}
 
//вставка
node* tree_insert(node** root, int x){
    node* p = *root;
    while(p != NULL){
        if(x == p->x)
            return p;
        else if(x < p->x){
            root = &p->left;
            p    = p->left;
        } else {
            root = &p->right;
            p    = p->right;
        }
    }
 
    p = (node*)malloc(sizeof(node));
    if(p != NULL){
        p->x    = x;
        p->left = p->right = NULL;
        *root   = p;
    }
    return p;
}
 
//удаление
void tree_remove(node** root, int x){
    node* p1, *p2, *p = *root;
    while(p != NULL){
        if(x == p->x)
            break;
        else if(x < p->x){
            root = &p->left;
            p    = p->left;
        } else {
            root = &p->right;
            p    = p->right;
        }
    }
 
    if(p == NULL)
        return;
    else if(p->right == NULL)
        *root = p->left;
    else {
        p2 = p->right;
        if(p2->left == NULL){
            p2->left = p->left;
            *root    = p2;
        } else {
            for(p1 = p2->left; p1->left != NULL; p1 = p2->left)
                p2 = p1;
 
            p2->left  = p1->right;
            p1->left  = p->left;
            p1->right = p->right;
            *root     = p1;
        }
    }
    free(p);
}
 
//печать
void tree_print(FILE* _out, const node* root){
    if(root != NULL){
        if(root->left != NULL)
            tree_print(_out, root->left);
 
        fprintf(_out, "%d ", root->x);
 
        if(root->right != NULL)
            tree_print(_out, root->right);
    }
}
 
//удаление всех
void tree_erase(node* root){
    if(root != NULL){
        if(root->left != NULL)
            tree_erase(root->left);
        if(root->right != NULL)
            tree_erase(root->right);
        free(root);
    }
}

Объяснение кода листинга программы

  1. Создание дерева из 30 элементов со случайными значениями от 0 до 9.
  2. Вставка элемента 5 в дерево.
  3. Вставка элемента 6 в дерево.
  4. Вставка элемента 7 в дерево.
  5. Печать дерева на экран.
  6. Удаление элементов 5, 6, 7 из дерева.
  7. Печать дерева на экран.
  8. Удаление всех элементов из дерева.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

10   голосов , оценка 4.1 из 5
Похожие ответы