Вы здесь

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

Исходный код на C++: 

Теория

Бинарное дерево имеет рекурсивную структуру, что предполагает использование рекурсивных алгоритмов для манипулирования деревьями. Каждое дерево состоит из вершин и связей между этими вершинными (рис.1). Если вершина X ссылается на вершину Y, тогда вершина Y является потомком для вершины X, а X предком для вершины Y (рис. 1). Узлы, не имеющие дочерних узлов, называются листьями (рис. 1). Каждая вершина бинарного дерева имеет следующую структуру: информационное поле(я), указатель на правое поддерево, указатель на левое поддерево.

Визуальное представление бинарного дерева.
Рис 1 Визуальное представление бинарного дерева.

Рассмотрим несколько основных функций для работы с бинарным деревом: добавление нового узла(add), поиск элемента (serch), обход (view), очистить (clean). Рассмотрим каждую функцию более подробно. Функция add выполняет следующий перечень операций:
1)если достигли дна дерева;
 1.1)создаём новый узел;
 1.2)левый и правый указатель указывают на пусто;
2)иначе выбираем ветку, по которой продолжим просмотр дерева. Выбор ветки поддерева зависит от конкретной реализации дерева. В данном примере в качестве информационного поля(data) выступает целое число(int) и выбор ветки осуществляется следующим образом. Если значение текущего элемента больше искомого, просматриваем левую ветку поддерева, в противном случае правую.
Добавим в дерево новый элемент (add 4). После операции add дерево имеет следующую структуру (рис. 2).

Добавление нового элемента.
Рис 2. Добавление нового элемента.

Добавим ещё несколько значений (add 6 и add 7). Дерево содержит три элемента (рис. 3).

Добавление новых значений.
Рис 3. Добавление новых значений.

Принцип действия функции search заключается в том, что на каждом шаге рекурсии мы сравниваем текущий узел с искомым. Если текущий узел больше искомого, просматриваем левую ветку поддерева, в противном случае правую. Рассмотрим перечень выполняемых операций:
1)если текущий элемент пустой, возвращаем пусто;
2)если текущий узел равен искомому, возвращаем данный узел;
3)если текущий элемент больше искомого, просматриваем левую ветку поддерева, в противном случае правую. Просмотр элементов дерева осуществляется функцией view, которая выполняет следующие операции:
1)если текущий элемент пустой, выходим из функции;
2)просматриваем левую часть дерева;
3)печать информационного поля;
4) просматриваем правую часть дерева.
Для удаления всех элементов в дереве воспользуемся функцией clean. Данная функция аналогична функции view, за исключением одной строки. Заменим строчку «3)Печать информационного поля» в функции view, на «3) Удаление элемента» и получим функцию clean.Функция clean перечень операций:
1)если текущий элемент пустой, выходим из функции;
2)просматриваем левую часть дерева;
3)удаление элемента;
4) просматриваем правую часть дерева.

Программная реализация

typedef int newtp;
struct node//описание структуры
{
newtp data;
node *left;
node *right;
} *head=NULL;
int compare(newtp a,newtp b){return (int)a>(int)b?1:(int)a==(int)b?0:-1;}//фукция сравнивания элементов
void add(node *&t,newtp dt)//добавить узел в дерево
{
if(t==NULL)//создаём уэел и добавляем к концу ветки
{
t=new node;
t->data=dt;
t->left=t->right=NULL;
return ;
}
if(compare(t->data,dt)==1)//сравниваем два значения и выбираем к какой ветки добавить к левой или правой
add(t->left,dt);
else
add(t->right,dt);
}
node* serch(node *t,newtp dt)//поиск узла
{
if(t==NULL) return NULL;// ветка пуста
if(compare(t->data,dt)==0) return t;
if(compare(t->data,dt)==1)//сравниваем два значения и выбираем по какой ветки продолжать поиск левой или правой
serch(t->left,dt);
else
serch(t->right,dt);
}
void clean(node *t)//удалить все элементы из дерева
{
if(t==NULL)return ;
clean(t->left);
delete t;
clean(t->right);
}
void view(node *t)//просмотр элементов дерева
{
if(t==NULL)return ;
view(t->left);
printf ("Value=%d \n",(int)t->data);
view(t->right);
}