8.2. Рекурсивный обход дерева
Рекурсивное определение дерева и рекурсивный же алгоритм его обхода позволяют выполнить просмотр всех вершин дерева и получить общие характеристики всего дерева. Естественным выглядит здесь обратное накопление результата в рекурсивной функции: потомки возвращают значения, которые интегрируются с результатом текущей вершины и возвращаются к предку.
//------------------------------------------------------82-01.cpp
// Алгоритмы, основанные на полном обходе дерева
struct tree1{
int val;
int n;
tree1 *ch[10];};
//-------- Количество вершин в дереве
int F1(tree1 *p){
int s=1;
for (int i=0;i < p->n; i++) s+=F1(p->ch[i]);
return s;}
//--------- Сумма значений в вершине дерева
int F2(tree1 *p){
int s=p->val;
for (int i=0;i < p->n; i++) s+=F2(p->ch[i]);
return s;}Из приведенных примеров видно, что обе функции накапливают сумму некоторых значений, получаемых от потомков. Ответ на вопрос «Сумму чего?» следует искать в другом месте: результат зависит от того, что добавляет в сумму текущая вершина.
//------- Максимальное значение в вершине дерева
int F3(tree1 *p){
int s=p->val;
for (int i=0;i < p->n; i++)
{ int vv=F3(p->ch[i]); if (vv > s) s=vv; }
return s;}
//----------- Максимальная длина ветви дерева
int F4(tree1 *p){
int s=0;
for (int i=0;i < p->n; i++)
{ int vv=F4(p->ch[i]); if (vv > s) s=vv; }
return s+1;}Аналогично обстоит дело с контекстом поиска максимума: в первом примере более-менее ясно, что в вычислении максимума от потомков участвует значение в текущей вершине, что однозначно определяет общий результат. Во втором случае не все так очевидно. Логический анализ не позволяет сформулировать результат: Функция возвращает максимальное значение «чего-то», полученного от потомков, увеличивая его в текущей вершине на 1. Только исторический анализ и непосредственное наблюдение за программой позволяют догадаться, что результатом функции (а также инвариантом рекурсивного алгоритма) является максимальная длина ветви: текущая вершина удлиняет путь на 1.
Рекурсивный обход позволяет получить другие характеристики дерева, например, передавая в качестве формального параметра текущую «глубину» вершины, можно подсчитать сумму длин ветвей (расстояний до корня), что служит характеристикой сбалансированности дерева: в сбалансированном дереве оно близко к log2(N), в вырожденном списке – к N/2.
//----- Суммарное расстояние до корня - степень сбалансированности
int F6(tree1 *p, int L){
int s=L;
for (int i=0;i < p->n; i++)
s+=F6(p->ch[i],L+1);
return s;}
double main6(tree1 *p){ return ((double)F6(p,1))/F1(p); }При поиске в дереве вершины, значение в которой удовлетворяет заданному условию, кроме непосредственно обнаружения вершины нужно еще оборвать процесс рекурсивного обхода у всех вершин – предков, которым передается указатель на найденную вершину.
//-------- Поиск первого значения, удовлетворяющего условию
tree1 *F7(tree1 *p, int vv){ // Действие, выполняемое потомком
if (p->val ==vv) return p; // Найдено в текущей вершине - вернуть
for (int i=0;i < p->n; i++){
tree1 *q=F7(p->ch[i]); // Найдено у потомка – прекратить обход
if (q!=NULL) return q; } // Обработка результата предком
return NULL;} Кажущийся парадокс алгоритма, работающего с деревом. Действие, выполняемое в вершине – предке, связанное с получением результата, записано в теле функции после действия, вызвавшее его в потомке.
До сих пор мы использовали для сохранения результата явном виде результат рекурсивной функции. Даже для вершин, не принимающих участия в его формировании, его надо явно передавать от потомков к предку. Иногда бывает удобнее использовать в качестве формального параметра ссылку на общую переменную – результат, которая играет роль глобальной для множества экземпляров рекурсивной функции, соответствующих вершинам дерева (хотя синтаксически может таковой и не являться).
//----------------------------------------------------------------82-02.cpp
// Поиск свободной вершины с min глубиной
// Ссылки на параметры, общие для всех вершин
// lmin - минимальная глубина
// pmin - вершина минимальной глубины
void find_min(tree *p, int level, int &lmin, tree *&pmin){
if (p==NULL) return;
if (lmin!=-1 && level >=lmin) return; // Заведомо худший вариант
if (p->n!=N && (lmin==-1 || level<=lmin)) // Вершина ближе
{ lmin=level; pmin=p; return; }
for (int i=0; i<p->n;i++) // Количество потомков = N
find_min(p->ch[i],level,lmin,pmin);
}}
void main(){
tree *pp2;….. // Корневая вершина
tree *q; // Результат – указатель на найденную
int lm=-1; // Результат – минимальная глубина
find_min(pp2,0,lm,q);…}Обратите внимание на элемент оптимизации: если обнаружена вершина со свободной ветвью на некоторой глубине, то обход дерева ограничивается этой глубиной: заведомо худшие варианты уже не проматриваются.
Сохранение дерева в последовательный поток
До сих пор мы рассматривали сохранение в последовательном текстовом потоке данных, хранимых в линейных структурах. Для дерева возможны два варианта:
сохранение данных, хранящихся в вершинах дерева. В этом случае структура (топология) дерева теряется и при загрузке этих же данных в новое дерево его топология будет уже другой. Возможны и парадоксы. При сохранении данных сбалансированного двоичного дерева (см.8.5) в файле получится упорядоченная последовательность, обратная загрузка которой простейшим алгоритмом приведет к вырождению дерева в линейный список;
для сохранения структуры (топологии) дерева достаточно использовать рекурсивный последовательный формат, например, записывать количество прямых потомков в вершины и вызывать для них рекурсивно функцию сохранения.
//-------------Сохранение в последовательный поток
void save(tree *p, FILE *fd){
fprintf(fd,"%d %d %d\n",p->cnt,p->val,p->n);
for (int i=0;i<p->n;i++)
save(p->ch[i],fd);
}
//-------------Загрузка из последовательного потока
tree *load(FILE *fd){
tree *p=new tree;
fscanf(fd,"%d %d %d\n",&p->cnt,&p->val,&p->n);
for (int i=0;i<p->n;i++)
p->ch[i]=load(fd);
return p;
}![Рис. 82.1. Сохранение дерева в последовательный поток]./assets/082-01.png)
//---------------------------------------------------------------------- 82-02.cpp
//-------------Сохранение в последовательный поток
void save(tree *p, FILE *fd){
fprintf(fd,"%d %d %d\n",p->cnt,p->val,p->n);
for (int i=0;i<p->n;i++)
save(p->ch[i],fd);
}
//-------------Загрузка из последовательного потока
tree *load(FILE *fd){
tree *p=new tree;
fscanf(fd,"%d %d %d\n",&p->cnt,&p->val,&p->n);
for (int i=0;i<p->n;i++)
p->ch[i]=load(fd);
return p;
}Горизонтальный обход дерева
Рекурсивный обход дерева связан со стеком, который используется рекурсивным алгоритмом для сохранения вызовов. В принципе, стек можно сделать и явным, последовательность обхода от этого не изменится. В стек помещаются указатели на вершины-потомки, причем в обратном порядке (для их извлечения в прямом). Рекурсия превращается в цикл: на каждом шаге из явного стека извлекается очередная вершина, при ее обработке стек дополняется указателями на потомков.
//------------------------------------------------------------------82-02.cpp
// Полный рекурсивный обход дерева с явным использованием стека
void scan1(tree *p){
tree **stack=new tree*[1000]; // Явный стек
int sp=-1;
stack[++sp]=p; // В стеке есть вершины
while(sp!=-1){
tree *q=stack[sp--]; // Извлечь очередную
printf("cnt=%d val=%d\n",q->cnt,q->val);
for (int i=q->n-1; i>=0; i--) // Запись в стек в обратном порядке
stack[++sp]=q->ch[i];
}
delete stack;}Если же вместо стека применить очередь, то обход дерева будет происходить «по горизонтали» (см. также 7.5). Тогда можно естественным образом реализовать алгоритмы, использующие свойство «близости» к корню, например, построить сбалансированное дерево, размещая вершины на ближайшие свободные места. С практической точки зрения эта задача является чисто умозрительной: на самом деле включение вершин в дерево осуществляется по правилам, сохраняющим определенные свойства, установленные для дерева (например, упорядочение или нумерация в порядке обхода).
//------------------------------------------------------82-02.cpp
// Поиск ближайшей к корню вершины со свободной ветвью
// с использованием очереди вершин
tree *find_first(tree *ph,int sz){
int fst=0,lst=0;
tree **Q=new tree *[sz]; // Циклическая очередь
Q[lst++]=ph; // Поместить исходную в очередь
while(fst!=lst){ // Пока очередь не пуста
tree *q=Q[fst++]; // Извлечь указатель на очередную вершину
if (fst==sz) fst=0;
if (q->n !=N) { // Найдена первая со свободными ветвями
delete Q;
return q;
}
for (int i=0;i<q->n;i++){
Q[lst++]=q->ch[i]; // Помещение всех потомков в очередь
if (lst==sz) lst=0;
}
}
delete Q; // Очередь пуста – вершина не найдена
return NULL;}Аналогичный алгоритм на основе рекурсивного обхода был рассмотрен выше. Забегая вперед, рассмотрим более эффективный (жадный) алгоритм, основанный на выборе единственного потомка с минимальным числом (счетчиком) вершин в его поддереве. Этот счетчик является элементом избыточности, и его необходимо корректировать в процессе движения по всем проходимым вершинам.
//-------------------------------------------------------------------------82-02.cpp
// Вставка в поддерево с минимальным количеством вершин
tree *create(int vv){
tree *q=new tree;
q->val=vv;
q->n=0;
q->cnt=1;
return q; }
void insert_min(tree *&p, int vv){ // Ссылка на указатель на текущую вершину
if (p==NULL) { p=create(vv); return; }
p->cnt++; // Наращивать счетчик в промежуточных вершинах
if (p->n!=N) { // Есть свободная ветка – создать вершину
p->ch[p->n++]=create(vv);
return;
}
for (int i=1,k=0; i<N;i++) // Количество потомков = N
if (p->ch[i]->cnt < p->ch[k]->cnt)
k=i; // Искать потомка с min
insert_min(p->ch[k],vv); // числом вершин в поддереве и выбрать его
}