Сборник по задачам и примерам Assembler

       

Дерево



Дерево

То, что неясно, следует выяснить. То, что трудно творить, следует делать с великой настойчивостью.

Конфуций Деревом называется сетевая структура, обладающая следующими свойствами:

  • среди всех узлов существует один, который не имеет ребер, входящих от других узлов, — этот узел называется корнем;
  • все узлы, за исключением корня, имеют одно и только одно входящее ребро;
  • ко всем узлам дерева имеется путь, начало которого лежит в корне дерева. Графически дерево изображают так, как показано на Рисунок 2.18.
  • Рисунок 2.18. Изображение дерева и соответствующего ему связного списка

    Следуя терминологии дерева, можно ввести некоторые определения, касающиеся его структуры. Ребра, соединяющие смежные узлы дерева, называются ветвями. Оконечные узлы дерева, которые не ссылаются на другие узлы, называются листьями. Другие узлы дерева, за исключением корня, называются узлами ветвления. Две смежные вершины дерева состоят в «родственных» отношениях. Вершина X, находящаяся на более высоком уровне дерева по отношению к вершине Y, называется отцом. Соответственно, вершина Y по отношению к X называется сыном. Если вершина X имеет несколько сыновей, то по отношению друг к другу последних называются братьями. В принципе, вместо этих терминов можно использовать следующие: родитель, потомок и т. п. Классификация деревьев производится по степени исхода ветвей из узлов деревьев. Дерево называется m-арным, если степень исхода его узлов не превышает значения m.

    В практических приложениях широко используется специальный класс деревьев — бинарные деревья. Бинарное дерево — m-арное дерево при m = 2. Это означает, что степень исхода его вершин не превышает 2. В случае когда m равно 0 или 2, имеет место полное бинарное дерево. Важно то, что любое m-арное дерево можно преобразовать в эквивалентное ему бинарное дерево. В свою очередь, в силу ограничений по степени исхода вершин бинарное дерево легче представлять в памяти и обрабатывать. По этой причине мы основное внимание уделим работе с бинарными деревьями.

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

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


  • Содержание раздела