Нумерация вершин в деревьяхСпособы обхода дерева
В любой структуре данных имеется естественная нумерация элементов по их расположению в ней. Массивы и списки не вызывают никаких вопросов - каждый элемент списка или массива имеет свой логический номер в линейной последовательности, соответствующей их размещению в памяти (массив) или направлению последовательного обхода (списки). В деревьях обход вершин возможен только с использованием рекурсии, поэтому и логическая нумерация вершин производится согласно последовательности их рекурсивного обхода. Рекурсивная функция в этом случае получает текущий счетчик вершин, который она увеличивает на 1 при обходе текущей вершины и который она передает и получает обратно из поддеревьев.
//------------------------------------------------------bk55-08.cpp
// Рекурсивный обход двоичного дерева с нумерацией вершин
// снизу-вверх слева-направо, n - текущий номер вершины
int Scan(btree * p, int n)
{
if (p==NULL) retur n n;
Scan(p->lef t,n);
n++;
cout << n << p->val << endl;
n=Scan(p->righ t,n) ;
return n;
}
В приведенном примере обход вершин производится слева-направо, снизу-вверх. В двоичном дереве он обеспечивает просмотр значений вершин в порядке возрастания. Аналогичный обход в порядке справа-налево, снизу-вверх дает в двоичном дереве последовательность в порядке убывания. Следует заметить, что возможны и другие варианты обхода, например сверху-вниз, когда вершина-предок нумеруется перед вершинами-потомками
n++;
cout << n << p->val << endl;
n=Scan(p->left,n);
n=Scan(p->right,n);
Обход с нумерацией двоичного дерева используется для извлечения вершины по логическому номеру, соответствующему упорядочению значений этих вершин в порядке возрастания. В этом случае для нумерации вершин приходится использовать глобальный счетчик
//------------------------------------------------------bk55-09.cpp
// Рекурсивный обход двоичного дерева с последовательной
// нумерацией вершин в возвратом указателя на вершину
// с заданным номером
// Глобальный счетчик вершин передается через указатель
btree *ScanNum(btree *p, int *n)
{
btree *q;
if (p==NULL) return NULL;
q=Scan Num(p->left,n);
if (q!=NULL) return q;
if ((*n)-- ==0) return p;
return Scan Num(p->right,n);
}
void main()
{
btree *ph; int N=26; // Пример вызова
btree *s = ScanNum(ph,&N);
}
