include stdio include stdlib define TREE struct node struct node int i

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
#include <stdio.h>
#include <stdlib.h>
#define TREE struct node *
struct node
{
int info;
struct node *left, *right;
};
TREE new_node (int x) //функция создания нового узла
{
TREE ptr;
ptr = (TREE) malloc (sizeof(struct node));
ptr->info = x;
ptr->left = ptr->right = NULL;
return ptr;
}
TREE add_node(int x, TREE pn) //функция добавления узла в дерево
{
TREE ptr = pn;
if (pn == NULL)
return new_node (x);
if (x < pn->info)
pn->left = add_node (x, pn->left);
else
pn->right = add_node (x, pn->right);
return ptr;
}
void print_sim (TREE pn) //функция печати дерева в симметричном порядке
{
if (pn->left)
print_sim (pn->left);
printf ("%d ",pn->info);
if (pn->right)
print_sim (pn->right);
}
void del_tree(TREE pn) //функция удаления дерева
{
if (pn->left)
del_tree(pn->left);
if (pn->right)
del_tree(pn->right);
free (pn);
}
void Del (TREE *q, TREE *r); //вспомогательная функция для удаления узла с обоими сыновьями
void Delete (TREE *p, int x) //функция удаления узла со значением х из дерева
{
TREE q;
if (*p==NULL) { return;}
if (x<(*p)->info)
Delete (&(*p)->left, x); //ищем в левом поддереве
else
if (x>(*p)->info)
Delete (&(*p)->right, x); //ищем в правом поддереве
else //нашли
{
q = *p;
if ((*p)->left==NULL) //нет левого сына
*p = (*p)->right; // "поднимаем" правого
else
if ((*p)->right==NULL) //нет правого сына
*p=(*p)->left; // "поднимаем" левого
else //есть оба сына
Del (&q, &(*p)->right);
free (q);
}
}
void Del (TREE *q, TREE *r)
{
if ((*r)->left)
Del (q, &(*r)->left); //добираемся до самой левой компоненты
else
{
(*q)->info = (*r)->info; //переписываем информационное поле в удаляемый элемент
*q = *r; //переставляем указатель на освободившийся элемент, чтобы освободить память
*r = (*r)->right; // "поднимаем" правого сына переставленного узла
}
}
main()
{
TREE t=NULL;
int mas[] = {8,3,11,1,5,9,14,6,10,12,15,7,13}, i;
for(i=0; i<13; i++)
t = add_node(mas[i], t);
print_sim (t); printf("\n");
Delete(&t,1); //удаление листа
print_sim (t);printf("\n");
Delete(&t,6); //удаление узла с одним сыном
print_sim (t);printf("\n");
Delete(&t,11); //удаление узла с двумя сыновьями
print_sim (t);printf("\n");
del_tree(t);
system("pause");
return 0;
}