3-й семестр / Лекция 1 - Нелинейные структуры данных
.pdf
|
9 |
4 |
A |
0 |
|
10 |
1 |
C |
0 |
root |
9 |
|
|
|
Рис.8. Реализация списка левых сыновей и правых братьев в форме таблицы
struct TNode{ |
|
int Left; |
//левое поддерево |
char Nod; |
//метка |
int Right; |
//правое поддерево |
End; |
|
struct Ttree{ |
|
TNode tabl[MaxLen]; |
//таблица сыновей |
Tifo info[MaxLen]; |
//значения узлов |
Int Root; |
//корень |
}; |
|
3 Алгоритмы обхода K– арного дерева
K-арное дерево типа T это: |
|
|
|
1. |
Пустая структура или |
|
|
2. |
Состоит из 1-го узла n типа T |
или |
|
3. |
Состоит из узла, с которым связано конечное число древовидных |
||
|
структур с корнями (n1,n2,…nk) базового типа |
T , называемых |
|
|
поддеревьями. |
|
|
Обход дерева – это алгоритм, обеспечивающий посещение каждого узла дерева с целью выполнить операцию с данными узла.
Обход дерева возможен, если дерево упорядочено.
Так как дерево является частным случаем графа, то можно использовать два вида обходов, допустимых над графами:
обход в глубин - это посещение узлов по поддеревьям (ветвям).;
обход в ширину это обход по уровням (обход сыновей)..
3.1Алгоритмы обхода в глубину
Существует три вида алгоритмов обхода в глубину: прямой, обратный,
симметричный.
Схемы обходов
Рассмотрим схемы алгоритмов для дерева, представленного на рисунке 8. Дерево с корнем А имеет два поддерева – левое А и правое В.
Прямой обход предусматривает посещение узлов в следующем порядке: корень, левое поддерево, правое поддерево, т.е. АВС.
Симметричный обход предусматривает посещение узлов в следующем порядке: левое поддерево, корень, правое поддерево, т.е. ВАС.
Обратный обход предусматривает посещение узлов в следующем порядке: левое поддерево, правое, поддерево корень, т.е. ВСА.
|
А |
|
1 |
|
2 |
В |
С |
|
1 |
Рис. 8. Дерево с двумя поддеревьями
Алгоритм прямого обхода непустого К - арного дерева
1.Сначала посещается корень дерева (узел n).
2.Затем осуществляется обход левого поддерева Т1 дерева Т в прямом порядке (т.е. этим же алгоритмом).
3.После обхода Т1 последовательно осуществляется обход в прямом порядке поддеревьев Т2, Т3, Тк.
Пример 5. Список узлов, в порядке посещения для дерева, представленного на рисунке 9.
Т
1 |
Т1 |
|
|
Т3 |
|
|
|
|
2 |
|
7 |
8 |
|
|
|
|
5 |
9 |
|
Т2 |
|
|
|
10 |
6 |
3 |
4 |
12 |
13 |
|
|
11 |
1
Рис.9. Дерево Т из трех поддеревьев Т1, Т2, Т3
Посещение узлов будем представлять в виде списка узлов. Список узлов при прямом обходе.
Список посещенных узлов Комментарии к операции
1 |
Посетили корень дерева и переходим к левому |
|||
|
сыну |
|
|
|
1,2 |
Посещаем корень дерева Т1 и обходим дерево |
|||
|
Т1 прямым обходом. У Т1 есть левый сын, |
|||
|
тогда надо обойти его прямым обходом. |
|
||
1, 2, 5 |
5 –левый сын узла 2. Узел 5 имеет левое |
|||
|
поддерево, тогда надо обойти его прямым |
|||
|
обходом. |
|
|
|
1, 2, 5. 6 |
6 - левый сын узла 5. Узел 6 не имеет |
|||
|
поддеревьев, следовательно, его обход |
|||
|
завершен. Но узел 6 имеет правых братьев. |
|||
|
Надо обойти их, согласно алгоритму. |
|
||
1, 2, 5. 6. 3 |
3 – правый брат узла 6 (в терминологии дерева |
|||
|
это поддерево для узла 5), обходим поддерево |
|||
|
с корнем 3 в прямом порядке, но у него нет |
|||
|
поддеревьев, |
поэтому |
его |
обход |
|
завершен.Обход следующего поддерева узла 5. |
|||
1, 2, 5. 6. 3, 4 |
4 – следующий правый брат узла 6 и правый |
|||
|
брат узла 3, надо обойти и его поддеревья, но |
|||
|
их нет и больше нет правых братьев у узла 6. |
Обход дерева узла 5 завершен, в дереве Т1 посещено левое поддерево, но не посещено правое, согласно алгоритма теперь надо обойти правое поддерево Т1 в прямом порядке.
1, 2, 5. 6. |
3, 4, 9 |
9 – корень правого поддерева дерева Т1. Затем |
|
|
обходим левое поддерево узла 9 |
1, 2, 5. 6. |
3, 4, 9, 11 |
11 – корень левого поддерева узла 9. Узел не |
|
|
имеет поддеревьев, поэтому его обход |
|
|
завершен. Переходим к обходу остальных |
|
|
поддеревьев узла 9. |
1, 2, 5. 6. |
3, 4, 9, 11, 12 |
Узел 12 не имеет поддеревьев, поэтому его |
|
|
обход завершен. Переходим к обходу |
|
|
следующего поддерева узла 9. |
1, 2, 5. 6. |
3, 4, 9, 11, 12, 13 |
Узел 13 не имеет поддеревьев, поэтому его |
|
|
обход завершен. Переходим к обходу |
|
|
следующего поддерева узла 9, но поддеревьев |
|
|
больше нет, т. е. обход дерева с узлом 9 |
|
|
завершен. |
Пройдены все поддеревья поддерева Т1 дерева Т и тем самым все левое поддерево дерева Т. Надо обойти следующие поддеревья дерева Т. Это дерево Т2.
1, 2, 5. 6. 3, 4, 9, 11, 12, 13, |
7 |
– корень дерева Т2. У этого дерева нет |
7 |
поддеревьев. Надо перейти на дерево Т3. |
|
Обход дерева Т2 завершен, так кА у него одно поддерево – это левое. |
||
1, 2, 5. 6. 3, 4, 9, 11, 12, 13, |
8 |
– корень дерева Т3. У него есть одно |
7, 8 |
поддерево. Раз оно одно, то оно левое |
|
поддерево. Надо его посетить. |
1, 2, 5. 6. 3, 4, 9, 11, 12, 13, |
10 – левое поддерево Т3. Больше у Т3 нет |
7, 8, 10 |
поддеревьев. Его обход завершен. |
Обход дерева Т3 завершен, так кА у него одно поддерево – это левое.
Обход дерева Т по алгоритму прямого обхода завершен.
Алгоритм симметричного обхода непустого К - арного дерева
1.Сначала обходим левое поддерево Т1 дерева Т алгоритмом симметричного обхода.
2.Затем посещается корень дерева Т.
3.После посещения корня осуществляется последовательный обход всех остальных поддеревьев дерева Т Т2, Т3, Тк в симметричном порядке.
Пример 6. Список узлов дерева Т, представленного на рис.9. при симметричном обходе.
6, 5, 3, 4, 2, 11, 9, 12, 13, 1, 7, 10, 8
Алгоритм обратного обхода непустого К - арного дерева
4.Сначала обходим левое поддерево Т1 дерева Т алгоритмом симметричного обхода.
5.Затем осуществляется последовательный обход всех остальных поддеревьев дерева Т: Т2, Т3, Тк в обратном порядке.
6.Затем посещается корень дерева Т.
Пример 7 . Список узлов дерева Т, представленного на рис.9. при обратном обходе.
6, 3, 4, 5, 11, 12, 13, 9, 2, 7, 10, 8, 1
Алгоритм обхода в глубину
Осуществляется сверху вниз по уровням.
Пример 8 . Список узлов дерева Т, представленного на рис.9. при обходе в глубину.
1, 2, 7, 8, 5, 9, 10, 6, 3, 4, 11, 12, 13
Выводы. Рассмотренные алгоритмы обхода применяются для структуры определяемой рекурсивно. Из определений алгоритмов видно, что они так же рекурсивные. Реализация алгоритмов обхода может быть как рекурсивной, так и не рекурсивной.
Реализация рекурсивных алгоритмов обхода
Введем абстрактный тип данных – дерево (Tree) и определим в нем данные (дерево) и операции над деревом.
АТД Tree
Данные
// TNode – тип значения метки узла //TLabel - Тип индекса элемента в дереве Узел (n), являющийся корнем дерева. Список из К узлов (n1, n2, ……nk).
Операции
//Создание дерева из К узлов.
Procedure CreateT(var T:Tree); //Поиск левого сына узла n
function LeftSon(n:TNode;const T:Ttree):Tlabel; //Поиск правого брата n
function rightBrather(n:TNode;const T:Ttree):Tlabel; //Поиск родителя узла n
function Parent(n:TNode;const T:Ttree):Tlabel; //Корень дерева
function Root(n:Tlabel;const T:Ttree):TNode; //проверка не пусто ли дерево
function Empty(T:TNodeR):Boolean; Procedure PreOrder(n:Tlabel;const T:Ttree); end ATD
Реализация АТД Tree на таблице левых сыновей и правых братьев //Модуль Unit с реализацией
unit Unit1;
interface |
|
Const MaxNodes=100; |
|
type |
|
TNode=char; |
|
Tlabel=integer; |
|
TNodeR=record |
|
Left:integer; |
|
Node:TNode; |
|
Right:integer; |
|
End; |
|
Ttree=record |
|
Sons:array [1..MaxNodes] of TNodeR; |
//таблица сыновей |
//ValuesNode: array [1..MaxNodes] of TValue |
;//значения узлов |
Root:integer; |
//корень |
countNodes:integer; |
|
End; |
|
Procedure CreateT(var T:Ttree); |
|
function LeftSon(n:TNode;const T:Ttree):Tlabel; |
|
function rightBrather(n:TNode;const T:Ttree):Tlabel; |
|
function Parent(n:TNode;const T:Ttree):Tlabel; function Root(n:Tlabel;const T:Ttree):TNode; function Empty(T:TNodeR):Boolean; Procedure PreOrder(n:Tlabel;const T:Ttree);
implementation
Procedure CreateT(var T:Ttree); var i,w:integer;
begin T.Root:=1;
writeln('countNodes=');
readln(T.countNodes);
for i:=1 to MaxNodes do //обнуление дерева begin
T.Sons[i].Node:=' ';
T.Sons[i].Left:=0;
T.Sons[i].Right:=0
end;
for i:=1 to T.countNodes do begin
writeln('Koren - Metka uzla char ', i); readln(T.Sons[i].Node);
end;
for i:=1 to T.countNodes do begin
writeln('Left uzla ',T.Sons[i].Node); readln(T.Sons[i].Left); writeln('right uzla'); readln(T.Sons[i].right);
end;
end;
function LeftSon(n:TNode;const T:Ttree):Tlabel; var i:integer;
begin i:=1;
while (i<= T.countNodes) and (T.Sons[i].Node<>n) do
inc(i);
if i>T.countNodes then LeftSon:= 0
else
LeftSon:= T.Sons[i].left;
end;
function rightBrather(n:TNode;const T:Ttree):Tlabel; var i:integer;
begin i:=1;
while (i<= T.countNodes) and (T.Sons[i].Node<>n) do
inc(i);
if i>T.countNodes then rightBrather:= 0
else
rightBrather:= T.Sons[i].right;
end;
function Parent(n:TNode;const T:Ttree):Tlabel; var i:integer;
begin
//найти индекс узла n i:=1;
while (i<= T.countNodes) and (T.Sons[i].Node<>n) do inc(i);
if i>T.countNodes then result:= 0
else begin
//если узел найден то //искать индекс в списке индексов левых сыновей result:=i;
i:=1;
while (i<= T.countNodes) and (T.Sons[i].left<>result) do inc(i);
if i>T.countNodes then begin
//поиск индекса в списке правых братьев i:=1;
while (i<= T.countNodes) and (T.Sons[i].right<>result) do inc(i);
if i>T.countNodes then result:=0
else
result:=i; end
else result:=i;
end;
end;
function Root(n:Tlabel;const T:Ttree):TNode; begin
result:=T.Sons[n].Node;
end;
function Empty(T:TNodeR):Boolean; begin
result:=T.Node=' '; end;
Procedure PreOrder(n:Tlabel;const T:Ttree);
Var
L,R:Tlabel;
Begin
If (n<>0)and not Empty(T.Sons[n]) then
begin
writeln(Root(n,T)); //можно заменить функцией обработки данных узла
L:= LeftSon(root(n,T),T); PreOrder(L,T);
While (L<>0) and (not Empty(T.Sons[L])) do Begin
R:=rightBrather(Root(L,T),T);
PreOrder(R,T);
End; End
End;
end.
Тестирующая программа для дерева рисунка 8.
program Project2;
{$APPTYPE CONSOLE}
uses SysUtils,
Unit1 in 'Unit1.pas';
var T:Ttree; w:Tlabel;
begin CreateT(T);
w:=rightBrather('B',T);
writeln(w);
preorder(T.Root,T);
readln;
end.