struct btree
{
int val;
btree *left,*right;
};
Указанное свойство позволяет применить в двоичном дереве алгоритм двоичного поиска. Действительно, каждое сравнение искомого значения и значения в вершине двоичного дерева позволяют выбрать для следующего шага правое или левое поддерево. Алгоритмы включения и исключения вершин дерева не должны нарушать указанное свойство: при включении вершины дерева поиск места ее размещения производится путем аналогичных сравнений:
//------------------------------------------------------bk55-06.cpp
//----- Рекурсивный поиск в двоичном дереве---------------
// Возвращается указатель на найденную вершину
btree *Search(btree *p, int v)
{
if (p==NULL) return(NULL); // Ветка пустая
if (p->val == v) return(p); // Вершина найдена
if (p->val > v) // Сравнение с текущим
return(Search(p->left,v)); // Левое поддерево
else
return(Search(p->right,v)); // Правое поддерево
}
//----- Включение значения в двоичное дерево--------------
// функция возвращает указатель на созданную вершину,
// либо на существующее поддерево
btree *Insert(btree *pp, int v)
{
if (pp == NULL) // Найдена свободная ветка
{ // Создать вершину дерева
btree *q = new btree; // и вернуть указатель
q->val = v;
q->left = q->right = NULL;
return q;
}
if (pp->val == v) return pp;
if (pp->val > v) // Перейти в левое или
pp->left=Insert(pp->left,v); // правое поддерево
else
pp->right=Insert(pp->right,v);
return pp;
}
void main()
{
btree *ss=Search(ph,5); // пример вызова
ph=Insert(ph,6);
}
Двоичное дерево имеет также естественное представление и в обычном массиве.