Последовательности (деревья)

Деревья

Конечное корневое дерево $$T$$ формально определяется как непустое множество упорядоченных узлов, таких, что существует один выделенный узел, называемый корнем дерева, а оставшиеся узлы разбиты на $$m \geqslant 0$$ поддеревьев $$T_1,T_2,\ldots,T_m$$. Будем рассматривать только корневые деревья. Узлы, не имеющие поддеревьев, называются листьями ; остальные узлы называются внутренними узлами.

В первой лекции уже было использовано дерево - при изучении необходимого числа взвешиваний в задаче о фальшивой монете с $$n$$ монетами. Так "рано" деревья появились в тексте не случайно, поскольку понятие дерева используется в различных важных аспектах данного курса. Посредством деревьев изображаются иерархические организации, поэтому они являются наиболее важными нелинейными структурами в комбинаторных алгоритмах.

В описании соотношений между узлами дерева используем терминологию, принятую в генеалогических деревьях. Так, говорят, что в дереве или поддереве все узлы являются потомками его корня, и наоборот, корень есть предок всех своих потомков. Корень именуют отцом корней его поддеревьев, которые в свою очередь будут сыновьями корня. Например, на рис. 4.1 узел $$A$$ является отцом узлов $$B,G$$ и $$I$$ ; $$J,K$$ - сыновья $$I$$, а $$C,E,F$$ - братья.

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

Определим лес как упорядоченное множество деревьев; в связи с этим можно перефразировать определение дерева: дерево есть непустое множество узлов, такое, что существует один выделенный узел, называемый корнем дерева, а оставшиеся узлы образуют лес с $$m \geqslant 0$$ поддеревьями корня. Важной разновидностью корневых деревьев является класс бинарных деревьев. Бинарное дерево $$T$$ либо пустое, либо состоит из выделенного узла, называемого корнем, и двух бинарных поддеревьев: левого $$T_l$$ и правого $$T_r$$. Бинарные деревья не являются подмножеством множества деревьев, они полностью отличаются по своей структуре, поскольку два следующих рисунка не изображают одно и то же бинарное дерево.

Как деревья, однако, они не отличаются от дерева, изображенного на рис. 4.4.

Различие между деревом и бинарным деревом состоит в том, что дерево не может быть пустым, а каждый узел дерева может иметь произвольное число поддеревьев; в то же время, бинарное дерево может быть пустым. Каждая из вершин бинарного дерева может иметь 0, 1 или 2 поддерева, и существует различие между левым и правым поддеревьями.

Представления

Почти все машинные представления деревьев основаны на связанных распределениях. Каждый узел состоит из поля $$INFO$$ и нескольких полей для указателей. Например, представление, которое будет удобным для изложения множества и мультимножества, для каждого узла имеет единственное поле для указателя $$FATHER$$, указывающего на отца данного узла. При этом приведенное на рис. 4.1 дерево будет выглядеть так, как показано на рис. 4.5. Такое представление полезно, если необходимо подниматься по дереву от потомков к предкам. Такая операция встречается довольно редко. Чаще требуется опуститься по дереву от предков к потомкам.

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

Каждый узел в этом случае имеет три поля: $$LEFT$$, указатель местоположения корня левого поддерева, $$INFO$$, содержимое узла, и $$RIGHT$$, указатель местоположения корня правого поддерева. Все сказанное выше проиллюстрировано на рис. 4.6.

Можно представлять деревья как бинарные, используя узлы фиксированного размера, представляя каждый узел леса в виде узла, состоящего из полей $$LEFT$$, $$INFO$$, $$RIGHT$$. При этом $$LEFT$$ предназначается для указания самого левого сына данного узла, а поле $$RIGHT$$ - для указания следующего брата данного дочернего/сыновнего узла.

Прохождения

Во многих приложениях необходимо пройти лес, заходя в узлы, то есть обрабатывая их некоторым систематическим образом. Посещение каждого узла может быть связано с простой операцией, такой как печать содержимого, или со сложной, такой как вычисление функции. Будем предполагать, что при посещении узла структура леса не меняется. Рассмотрим четыре основных способа прохождения леса: в глубину, снизу вверх, в горизонтальном порядке и для бинарных деревьев - в симметричном порядке.

При прохождении в глубину, известном также как прохождение в прямом порядке, узлы леса проходятся в соответствии со следующей рекурсивной процедурой:

Например, для леса, показанного на рис. 4.7, узлы будут проходиться в следующем порядке: $$A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S$$.

Название "в глубину" отражает тот факт, что после посещения некоторого узла мы продолжаем прохождение в глубь дерева всякий раз, когда это возможно. Такой порядок особенно полезен в процедурах поиска.

Для бинарных деревьев эта процедура упрощается и выглядит следующим образом.

Прохождение снизу вверх, известное также как обратный порядок или концевой порядок, осуществляется согласно следующей рекурсивной процедуре:

Название "снизу вверх" связано с тем, что в момент посещения произвольного узла его потомки оказываются уже пройденными. Такой порядок прохождения полезен, в частности, потому, что он позволяет вычислять рекурсивно определенные функции на лесах. При этом порядке прохождения узлы леса, показанного на рис. 4.7, проходятся в такой последовательности: $$B,D,E,F,C,G,J,K,I,L,H,A,O,P,N,R,Q,S,M$$. Рекурсивная процедура прохождения снизу вверх применительно к бинарным деревьям имеет следующий вид:

Симметричный порядок для бинарных деревьев определяется рекурсивно следующим образом:

Такой способ прохождения известен также как лексикографический порядок или внутренний порядок. Заметим, что прохождение леса снизу вверх эквивалентно прохождению в симметричном порядке бинарного дерева, соответствующего этому лесу (при естественном соответствии).

Сравнивая рекурсивные процедуры прохождения бинарных деревьев в глубину, снизу вверх и в симметричном порядке, можно обнаружить их значительное сходство:

Это сходство позволяет построить общий нерекурсивный алгоритм, который может быть применен к каждому из этих порядков прохождения бинарных деревьев.

Горизонтальный порядок прохождения. При таком способе узлы леса проходятся слева направо, уровень за уровнем от корня вниз. Таким образом, в соответствии с этой процедурой узлы леса, показанного на рис.4.7, будут проходиться в следующем порядке: $$A,M,B,C,G,H,N,Q,S,D,E,F,I,L,O,P,R,J,K$$. Такое прохождение дерева полезно в определенных алгоритмах на графах.

Длина путей

Деревья можно использовать не только как способ представления структуры данных, но также как средство для анализа поведения определенных алгоритмов. В связи с этим возникает потребность в количественных измерениях различных характеристик деревьев и, в частности, бинарных деревьев.

Наиболее важные количественные характеристики деревьев связаны с уровнями узлов. Уровень $$p$$ определяется рекурсивно и считается равным нулю, если $$p$$ корень $$T$$ ; в противном случае уровень $$p$$ определяется как $$1+\text{уровень}(FATHER(p))$$. Понятие уровня дает возможность определить высоту $$h(T)$$ дерева $$T$$:$$h(T)\max_{p\in T}\text{уровня} (p).$$ Другими словами, высота дерева есть максимальное число ребер, образующих путь от корня к листу дерева.

Задача

Задача 1. Построить алгоритм обхода бинарного дерева (см. рис. 4.6,(а)) в глубину.

Программa

Программа 1. Обход бинарного дерева в глубину

//Обход ориентированных графов - поиск в глубину -
//обобщение обхода дерева в прямом порядке
#include <stdio.h>
#include <string.h>
#include <conio.h>
#include <stdlib.h>

int matr_sm[50][50];
int mark[50];
int n;

void vvod ()
{int v1,v2;
 printf("Введите кол-во вершин в графе:  ");
 do
  {
   scanf("%d",n);
   if (n>51) printf("Ошибка!! Введите кол-во вершин в графе:  ");
  }
 while (n>51);

for (int i=0;i <50;i++) for (int j=0;j <50;j++) matr_sm[i][j]=0;

printf("\nВведите связанные вершины : \n");
  do
  { scanf("%d ",v1);
    if (v1>n) //исходящая вершина
     { printf("ОШИБКА ВВОДА !!!!!!!!!");
       abort();
      }
    if (v1==0){break;} //  конец ввода
    scanf("  %d ",v2);
    if (v2>n) // входящая вершина
     { printf("ОШИБКА ВВОДА !!!!!!!!!");
       abort();
     }
    if (v2==0){break;}   //конец ввода
    matr_sm[v2-1][v1-1]=1;
  }   while(1);
}

void vivod()
{
   for (int j=0;j <n;j++)
   {
     for (int i=0;i<n;i++)  printf("%d ",matr_sm[j][i]);
     printf("\n");
   }
}

void dfs(int v)
{
 int w;
 mark[v]=1; //посетили
 printf("%i ",v+1); //и выдали на экран
 for (w=0;w<n;w++)
  if (matr_sm[v][w]==1);
   else if (mark[w]==0) dfs(w);
}

void main()
{  clrscr();
   vvod();
//   printf("\n"); printf("МАТРИЦА СМЕЖНОСТИ\n");
//   vivod();

printf("\n РЕЗУЛЬТАТ ПОИСКА В ГЛУБИНУ \n");
   for (int v=0;v<50;v++)  mark[v]=0;
   for (v=0;v<n;v++)  //если вершина не посещалась, то посетить
    if (mark[v]==0) dfs(v);

   getch();
}