1.3.1. Обходы дерева с нумерацией вершин

Способы обхода дерева. В деревьях обход вершин возможен только с использованием рекурсии, поэтому и их логическая нумерация производится согласно последовательности их рекурсивного обхода. Рекурсивная функция в этом случае получает ссылку или указатель на счетчик вершин, который она увеличивает на 1 при обходе текущей вершины. В зависимости от того, кто нумеруется вперед предок или потомки, и в зависимости от направления просмотра потомков имеют место различные способы обхода и нумерации.

//---- Обход дерева с нумерацией вершин сверху вниз, слева направо (прямой обход)

void ScanNum (tree *q, int &n ) {

if (q==NULL) return;

printf("n=%d val=%d\n",n++,q->val);

for (int i=0; i< 4; i++) ScanNum(q->p[i],n);

}

Обход с нумерацией в обычном дереве используется для извлечения вершины по логическому номеру. При достижении вершины с заданным номером обход прекращается (аналогично алгоритму поиска первого подходящего).

//---- Извлечение по логическому номеру с полным обходом дерева

int GetNum (tree *q, int &n, int num ) {

if (q==NULL) return -1;

if ( n++ ==num) return q->val; // Номер текущей совпал с требуемым

for (int i=0; i< 4; i++) { // Обход потомков,

int vv=GetNum (q->p[i],n,num ); // пока не превышен номер

if (n > num) return vv;

}

return -1; }

Если каждая вершина дерева будет содержать дополнительный параметр количество вершин в связанном с ней поддереве, то извлечение по логическому номеру можно выполнить с помощью циклического алгоритма, либо линейной рекурсии, благодаря тому, что можно сразу же определить в каком поддереве находится интересующая нас вершина. Счетчики вершин можно корректировать в самом процессе добавления /удаления вершин.

//--- Извлечение по логическому номеру (счетчик вершин в поддереве)

struct ctree{

int nodes; // Счетчик вершин в поддереве

int val;

ctree *p[4]; };

int GetNum(ctree *q, int num, int n0){

if (q==NULL) return 1; // n0 начальный номер в текущем поддереве

if (n0++==num) return q->val; // начальный номер совпал с требуемым

for (int i=0; i< 4; i++){

if (q->p[i]==NULL) continue;

int nc= q->p[i]->nodes; // число вершин у потомка

if (n0+ nc > num) // выбран потомок

return GetNum(q->p[i],num,n0); // с диапазоном номеров

else // корректировать начальный номер

n0+=nc; // для следующего потомка

}}

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

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

struct btree {

int val;

btree *left,*right; };

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

//----- Обход двоичного дерева

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 .

В двоичном дереве естественная нумерация вершин соответствует обходу в порядке возрастания их значений, то есть левое поддерево текущая вершина правое поддерево.

//---- Обход двоичного дерева с нумерацией вершин

void ScanNum ( btree *q, int &n ) {

if (q==NULL) return;

ScanNum(q->left,n);

printf("n=%d val=%d\n",n,q->val); n++;

ScanNum(q->right,n);}