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

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);
}