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


Нумерация вершин в деревьяхСпособы обхода дерева


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


//------------------------------------------------------bk55-08.cpp


// Рекурсивный обход двоичного дерева с нумерацией вершин


// снизу-вверх слева-направо, n - текущий номер вершины


int Scan(btree * p, int n)
{
if (p==NULL) retur n n;
Scan(p-&#62lef t,n);
n++;
cout &#60&#60 n &#60&#60 p-&#62val &#60&#60 endl;
n=Scan(p-&#62righ t,n) ;
return n;
}

В приведенном примере обход вершин производится слева-направо, снизу-вверх. В двоичном дереве он обеспечивает просмотр значений вершин в порядке возрастания. Аналогичный обход в порядке справа-налево, снизу-вверх дает в двоичном дереве последовательность в порядке убывания. Следует заметить, что возможны и другие варианты обхода, например сверху-вниз, когда вершина-предок нумеруется перед вершинами-потомками


n++;
cout &#60&#60 n &#60&#60 p-&#62val &#60&#60 endl;
n=Scan(p-&#62left,n);
n=Scan(p-&#62right,n);

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


//------------------------------------------------------bk55-09.cpp


// Рекурсивный обход двоичного дерева с последовательной


// нумерацией вершин в возвратом указателя на вершину


// с заданным номером


// Глобальный счетчик вершин передается через указатель


btree *ScanNum(btree *p, int *n)
{
btree *q;
if (p==NULL) return NULL;
q=Scan Num(p-&#62left,n);
if (q!=NULL) return q;
if ((*n)-- ==0) return p;
return Scan Num(p-&#62right,n);
}
void main()
{
btree *ph; int N=26; // Пример вызова


btree *s = ScanNum(ph,&#38N);
}




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



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