Презентация, доклад на тему Двоичные деревья в Паскаль.

как корень), и отношений («родительских»), образующих иерархическую структуру узлов.

Формально дерево ( tree ) определяется как конечное множество T одного или более узлов со следующими свойствами:
• Существует один выделенный узел, а именно – корень ( root ) данного дерева;
• Остальные узлы (за исключением корня) распределены среди m >0 непересекающихся множеств T 1 , T 2 , …. T m , и каждое из этих множеств, в свою очередь, является деревом; деревья T 1 , T 2 , ... T m называются поддеревьями данного корня.

же узел также является корнем этого дерева.
• Пусть n – это узел, а T 1 , T 2 , ... T m – деревья с корнями n 1 , n 2 , … n m соответственно. Можно построить новое дерево, сделав n родителем узлов n 1 , n 2 , … n m . В этом дереве n будет корнем, а T 1 , T 2 , ... T m – поддеревьями этого корня. Узлы n 1 , n 2 , … n m называются сыновьями узла n .

некоторого поддерева данного дерева.

Количество поддеревьев узла называется степенью этого узла. Узел с нулевой степенью называется концевым узлом или листом. Неконцевой узел называется узлом ветвления. Каждый узел имеет уровень, который определяется следующим образом: уровень корня дерева равен нулю, а уровень любого другого узла на единицу выше, чем уровень корня ближайшего поддерева, содержащего данный узел.

и { C , D , E , F , G }. Корнем дерева{ C , D , E , F , G } является узел C . Уровень узла C равен 1 по отношению ко всему дереву. Он имеет три поддерева { D }, { E }и { F , G }, поэтому степень узла C равна 3. Концевыми узлами (листьями) являются узлы B , D , E , G .

Путем из узла n 1 в узел n k называется последовательность узлов n 1 , n 2 , … n k , где для всех i , 1, i , k , узел n i является родителем узла n i +1 . Длиной пути называется число, на единицу меньше числа узлов, составляющего этот путь.

в этом случае узел a называется предком узла b , а узел b – потомком узла a . Любой узел одновременно является предком и потомком самого себя.
Например, на рисунке предками узла G будут сам узел G и узлы F , C и A . Потомками узла C будут являться сам узел C и узлы D , T , F , G . В дереве только корень не имеет предков, а листья не имеют потомков.

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

до какого-либо листа. Глубина узла определяется как длина пути от корня до этого узла.
Лес – это множество (обычно упорядоченное), содержащее несколько непересекающихся деревьев. Узлы дерева при условии исключения корня образуют лес.

1 , T 2 , ... T m , то дерево является упорядоченным.
Сыновья узла обычно упорядочиваются слева направо. Поэтому деревья, приведенные на рисунке, являются различными.

используемых способа :
прямой,
обратный,
симметричный .
Все три способа можно определить следующим образом:
• Если дерево T является нулевым деревом, то в список обхода записывается пустая строка;
• Если дерево T состоит из одного узла, то в список обхода записывается этот узел;

T 2 , ... T m , как показано на рисунке

Тогда для различных способов обхода имеем следующее:
Прямой обход . Сначала посещается корень n , затем в прямом порядке узлы поддерева T 1 , далее все узлы поддерева T 2 и т.д. Последними посещаются в прямом порядке узлы поддерева T m .
Обратный обход . Сначала посещаются в обратном порядке все узлы поддерева T 1 , затем в обратном порядке узлы поддеревьев T 2 … T m , последним посещается корень n .
Симметричный обход . Сначала в симметричном порядке посещаются все узлы поддерева T 1 , затем корень n , после чего в симметричном порядке все узлы поддеревьев T 2 … T m .

2 3 5 8 9 6 10 4 7.
Обратный обход этого же дерева даст нам следующий порядок узлов: 2 8 9 5 10 6 3 7 4 1.
При симметричном обходе мы получим следующую последовательность узлов:
2 1 8 5 9 3 10 6 7 4.

помеченным деревом.
Метка узла – это значение, которое «хранится» в узле.
Полезна следующая аналогия:
дерево –это список,
узел – это позиция,
метка –это элемент.

Самым простым представлением дерева T будет линейный массив A , где каждый элемент A [ i ] содержит номер родительского узла (является курсором на родителя). Поскольку корень дерева не имеет родителя, то его курсор будет равен 0.

правилу:

A [ i ]= j , если узел j является родителем узла i , A [ i ]=0, если узел i является корнем. Тогда массив будет выглядеть следующим образом:

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

хотя они оба похожи на обычное дерево (рис. в)).

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

Е: <тип хранимой информации>;
Left , right : tree ;
End ;

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

пусто, то нужно сравнить искомый ключ с ключом в корне дерева:
- если ключи совпадают, поиск завершен;
- если ключ в корне больше искомого, выполнить поиск в левом поддереве;
- если ключ в корне меньше искомого, выполнить поиск в правом поддереве.
• Если дерево пусто, то искомый элемент не найден.

следующие операции:
• Поиск по дереву;
• Обход дерева;
• Включение узла в дерево;
• Удаление узла из дерева.

p:=root;
while p<>nil do begin
if k=p^.inf then begin { узел с таким ключом есть }
find:=true;
exit;
end;
parent:=p {запомнить указатель на предка}
if k p := p ^. Left {спуститься влево}
else p := p ^. right ; {спуститься вправо}
end;
find:=false;
end;

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

5.

Сравниваем 5 с ключом корня; 5<10, следовательно, уходим в левое поддерево. Сравниваем 5 и 6; 5<6, спускаемся влево. Следующий узел является конечным (листом). Сравниваем 5 и 1; 5>1, следовательно, вставляем правого сына. Получим дерево с новым узлом, которое сохранило все свойства дерева поиска.

tree ; k: integer );
var
p : tree ; {удаляемый узел}
parent : tree ; {предок удаляемого узла}
y : tree ; {узел, заменяющий удаляемый}
function spusk(p:tree):tree;
var
y : tree ; {узел, заменяющий удаляемый}
pred:tree; { предок узла “y”}
begin
y:=p^.right;
if y^.left=nil then y^.left:=p^.left {1}
else {2}
begin
repeat
pred:=y; y:=y^.left;
until y^.left=nil;
y^.left:=p^.left; {3}
pred^.left:=y^.right; {4}
y^.right:=p^.right; { 5}
end;
spusk:=y;
end;
begin
if not find(root, k, p, parent) then {6}
begin writeln(' такого элемента нет '); exit; end;
if p^.left=nil t hen y:=p^.right {7}
else
if p^.right=nil then y:=p^.left {8}
else y:=spusk(p); {9}
if p=root then root:=y {10}
else {11}
if k parent^.left:=y
else parent^.right: =y;
dispose(p); {12}
end.

k удаляемого элемента. С помощью функции find определяются указатели на удаляемый элемент p и его предка parent . Если искомого элемента в дереве нет, то выдается сообщение ( {6}) .
В операторах {7}-{9} определяется указатель на узел y , который должен заменить удаляемый. Если у узла p нет левого поддерева, на его место будет поставлена вершина (возможно пустая) его правого поддерева ({7}).
Иначе, если у узла p нет правого поддерева, на его место будет поставлена вершина его левого поддерева ({8}).
В противном случае, когда оба поддерева существуют, для определения замещающего узла вызывается функция spusk , выполняющая спуск по дереву ({9}).
В этой функции первым делом проверяется особый случай, описанный выше ({1}). Если же этот случай (отсутствие левого потомка у правого потомка удаляемого узла) не выполняется, организуется цикл ({2}), на каждой итерации которого указатель на текущий элемент запоминается в переменной pred .А указатель y смещается вниз и влево до того момента, пока не станет ссылаться на узел, не имеющий левого потомка.
В операторе {3} к этой пустующей ссылке присоединяется левое поддерево удаляемого узла. Перед тем как присоединять к этому узлу правое поддерево удаляемого узла ({5}), требуется «пристроить» его собственное правое поддерево. Мы присоединяем его к левому поддереву предка узла y , заменяющего удаляемый ({4}), поскольку этот узел перейдет на новое место.
Функция spusk возвращает указатель на узел, заменяющий удаляемый. Если мы удаляем корень дерева, надо обновить указатель на корень ({10}), иначе – присоединить этот указатель к соответствующему поддереву предка удаляемого узла ({11}).
После того как узел удален из дерева, освобождается занимаемая им память ({12}).