Поиск и включение в двоичное дерево

Свойства двоичного дерева позволяют применить в нем алгоритм поиска, аналогичный двоичному поиску в массиве. Каждое сравнение искомого значения и значения в вершине позволяет выбрать для следующего шага правое или левое поддерево. Алгоритмы включения и исключения вершин дерева не должны нарушать указанное свойство: при включении вершины дерева поиск места ее размещения производится путем аналогичных сравнений. Эти алгоритмы являются линейно рекурсивными или циклическими. //----- Обход двоичного дереваvoid Scan(btree *p, int level){if (p==NULL) return;Scan(p->left,level+1);printf("l=%d val=%d\n",level,p->val);Scan(p->right,level+1); } //----- Поиск в двоичном дереве--------------- // Возвращается указатель на найденную вершину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); } // Правое поддерево //----- Включение значения в двоичное дерево-------------- // Используется ссылка на указатель на текущую вершинуvoid Insert(btree *&pp, int v){ if (pp == NULL) { // Найдена свободная ветка pp = new btree; // Создать вершину дерева pp ->val = v; pp->left = pp->right = NULL; return; }if (pp->val > v) // Перейти в левое илиInsert(pp->left,v); // правое поддеревоelse Insert(pp->right,v);} Обратите внимание, что указатель ppссылается на то место в дереве, где находится указатель на текущую вершину, а потому под него можно производить запись (присваивание) при создании новой вершины. При замене рекурсии циклом пришлось бы довольствоваться явным двойным указателем btree **pp.