Информатика и технология программирования


Двоичное дерево


Двоичным деревом называется дерево, каждая вершина которого имеет не более двух потомков. Кроме того, на данные, хранимые в вершинах дерева, вводится следующее правило упорядочения: значения вершин левого поддерева всегда меньше, а значения вершин правого поддерева -больше значения в самой вершине.


struct btree
{
int val;
btree *left,*right;
};

Указанное свойство позволяет применить в двоичном дереве алгоритм двоичного поиска. Действительно, каждое сравнение искомого значения и значения в вершине двоичного дерева позволяют выбрать для следующего шага правое или левое поддерево. Алгоритмы включения и исключения вершин дерева не должны нарушать указанное свойство: при включении вершины дерева поиск места ее размещения производится путем аналогичных сравнений:


//------------------------------------------------------bk55-06.cpp


//----- Рекурсивный поиск в двоичном дереве---------------


// Возвращается указатель на найденную вершину


btree *Search(btree *p, int v)
{
if (p==NULL) return(NULL); // Ветка пустая


if (p-&#62val == v) return(p); // Вершина найдена


if (p-&#62val &#62 v) // Сравнение с текущим


return(Search(p-&#62left,v)); // Левое поддерево


else
return(Search(p-&#62right,v)); // Правое поддерево


}
//----- Включение значения в двоичное дерево--------------


// функция возвращает указатель на созданную вершину,


// либо на существующее поддерево


btree *Insert(btree *pp, int v)
{
if (pp == NULL) // Найдена свободная ветка


{ // Создать вершину дерева


btree *q = new btree; // и вернуть указатель


q-&#62val = v;
q-&#62left = q-&#62right = NULL;
return q;
}
if (pp-&#62val == v) return pp;
if (pp-&#62val &#62 v) // Перейти в левое или


pp-&#62left=Insert(pp-&#62left,v); // правое поддерево


else
pp-&#62right=Insert(pp-&#62right,v);
return pp;
}
void main()
{
btree *ss=Search(ph,5); // пример вызова


ph=Insert(ph,6);
}

Двоичное дерево имеет также естественное представление и в обычном массиве.


- Начало -  - Назад -  - Вперед -



Книжный магазин