• Списки



• Стеки



• Очереди



• Деревья

Дерево — это совокупность элементов, называемых узлами (при этом один из них определен как корень), и отношений (родительский–дочерний), образующих иерархическую структуру узлов. Узлы могут являться величинами любого простого или структурированного типа, за исключением файлового. Узлы, которые не имеют ни одного последующего узла, называются листьями.

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

Двоичное дерево поиска может быть либо пустым, либо оно обладает таким свойством, что корневой элемент имеет большее значение узла, чем любой элемент в левом поддереве, и меньшее или равное, чем элементы в правом поддереве. Указанное свойство называется характеристическим свойством двоичного дерева поиска и выполняется для любого узла такого дерева, включая корень. Далее будем рассматривать только двоичные деревья поиска. Такое название двоичные деревья поиска получили по той причине, что скорость поиска в них примерно такая же, что и в отсортированных массивах: O(n) = C • log₂n (в худшем случае O(n) = n).

Пример. Для набора данных 9, 44, 0, –7, 10, 6, –12, 45 построить двоичное дерево поиска.

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

Выделим типовые операции над двоичными деревьями поиска:

• добавление элемента в дерево;
• удаление элемента из дерева;
• обход дерева (для печати элементов и т.д.);
• поиск в дереве.

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

Пусть двоичное дерево поиска описывается следующим типом

	struct BinTree{
       BT inf;
       BinTree *L; BinTree *R;
	    };

Покажем два варианта добавления элемента в дерево: итеративный и рекурсивный.

/* Итеративный вариант добавления элемента в дерево*/

BinTree* InsIteration(BinTree *T, BT x)
{ BinTree *vsp, *A;
  A = (BinTree *) malloc(sizeof(BinTree));
  A->inf=x; A->L=0; A->R=0;
  if (!T) T=A;
  else {vsp = T;
	while (vsp)
	{if (A->inf < vsp->inf)
	    if (!vsp->L) {vsp->L=A; vsp=A->L;}
	    else vsp=vsp->L;
	 else
	    if (!vsp->R) {vsp->R=A; vsp=A->R;}
	    else vsp=vsp->R;
	}
	}
return T;
}

/* Рекурсивный вариант добавления элемента в дерево*/

BinTree* InsRec(BinTree *Tree, BT x)
{
  if (!Tree) {Tree = (BinTree *) malloc(sizeof(BinTree));
	      Tree->inf=x; Tree->L=0; Tree->R=0;
	     }
  else if (x < Tree->inf) Tree->L=InsRec(Tree->L, x);
       else Tree->R=InsRec(Tree->R, x);
  return Tree;
}

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

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

	void PrintTree(BinTree *T)
	{
	  if (T) {PrintTree(T->L); cout << T->inf<< " "; PrintTree(T->R);}
	}

Реализуем функцию, возвращающую 1, если элемент присутствует в дереве, и 0 — в противном случае.

int Find(BinTree *Tree, BT x)
{ if (!Tree) return 0;
  else if (Tree->inf==x) return 1;
       else if (x < Tree->inf) return Find(Tree->L, x);
            else return Find(Tree->R, x);
}

По сравнению с предыдущими задача удаления узла из дерева реализуется несколько сложнее. Можно выделить два случая удаления элемента x (случай отсутствия элемента в дереве является вырожденным):

1) узел, содержащий элемент x, имеет степень не более 1 (степень узла — число поддеревьев, выходящих из этого узла);

2) узел, содержащий элемент x, имеет степень 2.

Случай 1 не представляет сложности. Предыдущий узел соединяется либо с единственным поддеревом удаляемого узла (если степень удаляемого узла равна 1), либо не будет иметь поддерева совсем (если степень узла равна 0).

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

BinTree * Delete(BinTree *Tree, BT x)
{ BinTree* P, *v;
  if (!Tree) cout << "такого элемента в дереве нет!" << endl;
  else if (x < Tree->inf) Tree->L = Delete(Tree->L, x);
       else if (x > Tree-> inf) Tree->R = Delete(Tree->R, x);
	    else {P = Tree;
		  if (!Tree->R) Tree = Tree->L; // случай 1
		  else if (!Tree->L) Tree = Tree->R; // случай 1
		       else // случай 2
                            { v = Tree->L;
                              if (v->R)
                              {
			      while (v->R->R) v = v->R; 
			      Tree->inf = v->R->inf;
			      P = v->R; v->R = v->R->L;
                              }
                              else
                              {
                               Tree->inf = v->inf;
                               P = v;
                               Tree->L=Tree->L->L;
                              }
			    }
		  free(P);
		 }
 return Tree;
}

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

1. Что такое рекурсивный алгоритм?
2. Из каких частей строится определение рекурсивного алгоритма?
3. Что является обязательным в любом рекурсивном алгоритме?
4. Можно ли рекурсию заменить итерацией? Можно ли итерацию заменить рекурсией?
5. Каков принцип построения динамической структуры «дерево»?
6. Перечислите сходства и отличия динамических структур типа «линейный список», «стек», «дерево».
7. Перечислите структуры, которые можно представить в виде дерева, которые встречаются в повседневной жизни.
8. Закончите фразу: «Линейный список — это дерево, в котором …».
9. Реализуйте итеративные варианты тех алгоритмов обработки дерева, которые представлены в рекурсивной форме.
10. Написать рекурсивную процедуру, которая печатает элементы из всех листьев дерева.
11. Написать рекурсивную функцию, которая определяет глубину заданного элемента на дереве и возвращает –1, если такого элемента нет.
12. Написать процедуру, которая печатает (по одному разу) все вершины дерева.
13. Написать процедуру, которая по заданному n считает число всех вершин глубины n в заданном дереве.
14. Написать процедуру, которая определяет глубину дерева.