Рекурсивное определение дерева и рекурсивный же алгоритм его обхода позволяют выполнить просмотр всех вершин дерева и получить общие характеристики всего дерева. Естественным выглядит здесь обратное накопление результата в рекурсивной функции: потомки возвращают значения, которые интегрируются с результатом текущей вершины и возвращаются к предку.
C
//------------------------------------------------------82-01.cpp// Алгоритмы, основанные на полном обходе дереваstructtree1{int val;int n;
tree1 *ch[10];};//-------- Количество вершин в деревеintF1(tree1 *p){int s=1;for(int i=0;i < p->n; i++) s+=F1(p->ch[i]);return s;}//--------- Сумма значений в вершине дереваintF2(tree1 *p){int s=p->val;for(int i=0;i < p->n; i++) s+=F2(p->ch[i]);return s;}
Из приведенных примеров видно, что обе функции накапливают сумму некоторых значений, получаемых от потомков. Ответ на вопрос «Сумму чего?» следует искать в другом месте: результат зависит от того, что добавляет в сумму текущая вершина.
C
//------- Максимальное значение в вершине дереваintF3(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;}//----------- Максимальная длина ветви дереваintF4(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.
C
//----- Суммарное расстояние до корня - степень сбалансированностиintF6(tree1 *p,int L){int s=L;for(int i=0;i < p->n; i++)
s+=F6(p->ch[i],L+1);return s;}doublemain6(tree1 *p){return((double)F6(p,1))/F1(p);}
При поиске в дереве вершины, значение в которой удовлетворяет заданному условию, кроме непосредственно обнаружения вершины нужно еще оборвать процесс рекурсивного обхода у всех вершин – предков, которым передается указатель на найденную вершину.
C
//-------- Поиск первого значения, удовлетворяющего условию
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;}// Обработка результата предкомreturnNULL;}
Кажущийся парадокс алгоритма, работающего с деревом. Действие, выполняемое в вершине – предке, связанное с получением результата, записано в теле функции после действия, вызвавшее его в потомке.
До сих пор мы использовали для сохранения результата явном виде результат рекурсивной функции. Даже для вершин, не принимающих участия в его формировании, его надо явно передавать от потомков к предку. Иногда бывает удобнее использовать в качестве формального параметра ссылку на общую переменную – результат, которая играет роль глобальной для множества экземпляров рекурсивной функции, соответствующих вершинам дерева (хотя синтаксически может таковой и не являться).
C
//----------------------------------------------------------------82-02.cpp// Поиск свободной вершины с min глубиной// Ссылки на параметры, общие для всех вершин// lmin - минимальная глубина// pmin - вершина минимальной глубиныvoidfind_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++)// Количество потомков = Nfind_min(p->ch[i],level,lmin,pmin);}}voidmain(){
tree *pp2;…..// Корневая вершина
tree *q;// Результат – указатель на найденнуюint lm=-1;// Результат – минимальная глубинаfind_min(pp2,0,lm,q);…}
Обратите внимание на элемент оптимизации: если обнаружена вершина со свободной ветвью на некоторой глубине, то обход дерева ограничивается этой глубиной: заведомо худшие варианты уже не проматриваются.
Сохранение дерева в последовательный поток #
До сих пор мы рассматривали сохранение в последовательном текстовом потоке данных, хранимых в линейных структурах. Для дерева возможны два варианта:
сохранение данных, хранящихся в вершинах дерева. В этом случае структура (топология) дерева теряется и при загрузке этих же данных в новое дерево его топология будет уже другой. Возможны и парадоксы. При сохранении данных сбалансированного двоичного дерева (см.8.5) в файле получится упорядоченная последовательность, обратная загрузка которой простейшим алгоритмом приведет к вырождению дерева в линейный список;
для сохранения структуры (топологии) дерева достаточно использовать рекурсивный последовательный формат, например, записывать количество прямых потомков в вершины и вызывать для них рекурсивно функцию сохранения.
C
//-------------Сохранение в последовательный потокvoidsave(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)
C
//---------------------------------------------------------------------- 82-02.cpp//-------------Сохранение в последовательный потокvoidsave(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;}
Горизонтальный обход дерева #
Рекурсивный обход дерева связан со стеком, который используется рекурсивным алгоритмом для сохранения вызовов. В принципе, стек можно сделать и явным, последовательность обхода от этого не изменится. В стек помещаются указатели на вершины-потомки, причем в обратном порядке (для их извлечения в прямом). Рекурсия превращается в цикл: на каждом шаге из явного стека извлекается очередная вершина, при ее обработке стек дополняется указателями на потомков.
C
//------------------------------------------------------------------82-02.cpp// Полный рекурсивный обход дерева с явным использованием стекаvoidscan1(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). Тогда можно естественным образом реализовать алгоритмы, использующие свойство «близости» к корню, например, построить сбалансированное дерево, размещая вершины на ближайшие свободные места. С практической точки зрения эта задача является чисто умозрительной: на самом деле включение вершин в дерево осуществляется по правилам, сохраняющим определенные свойства, установленные для дерева (например, упорядочение или нумерация в порядке обхода).
C
//------------------------------------------------------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;// Очередь пуста – вершина не найденаreturnNULL;}
Аналогичный алгоритм на основе рекурсивного обхода был рассмотрен выше. Забегая вперед, рассмотрим более эффективный (жадный) алгоритм, основанный на выборе единственного потомка с минимальным числом (счетчиком) вершин в его поддереве. Этот счетчик является элементом избыточности, и его необходимо корректировать в процессе движения по всем проходимым вершинам.
C
//-------------------------------------------------------------------------82-02.cpp// Вставка в поддерево с минимальным количеством вершин
tree *create(int vv){
tree *q=new tree;
q->val=vv;
q->n=0;
q->cnt=1;return q;}voidinsert_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++)// Количество потомков = Nif(p->ch[i]->cnt < p->ch[k]->cnt)
k=i;// Искать потомка с mininsert_min(p->ch[k],vv);// числом вершин в поддереве и выбрать его}