Добавил:
FluffyUnicorn
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз:
Предмет:
Файл:Структуры данных примеры / Дерево / tr_bin_search
.cpp//Дерево бинарного поиска. Вставка и удаление элемента
#include <stdio.h>
#include <stdlib.h>
#define TREE struct node *
struct node
{
int info;
node *left, *right;
};
TREE new_node (int x)
{
node *ptr;
ptr = new 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 if (x > pn->info)
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);
delete 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 (p, p->right);
delete 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,13);
print_sim (t);printf("\n");
Delete(t,11);
print_sim (t);printf("\n");
del_tree(t);
system("pause");
return 0;
}
Соседние файлы в папке Дерево