Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

While notEOF(F) do


Begin

Var

Var

Type

Uses

Begin

Begin

Begin

Begin

Begin

Begin

Var

Var

Begin

Var

Begin

Begin

Begin

Begin

Begin

Var

Begin

Else

End

Begin

Else

Begin

Begin

Begin

Else

End

Begin

Begin

Begin

Readln(F, S);

 

ifS = ‘’ thenAway(1); // Пустая строка нам ни к чему

 

iDepth := 0;

whileS[1] = ‘ ‘ do// Число пробелов есть глубина узла

Inc(iDepth);

Delete(S, 1, 1);

end;

 

ifS = ‘’ thenAway(2); // Пустая строка нам ни к чему

 

New(pCurr);

pCurr^.iKey := StrToInt(S);


{$IFDEF StaticArrayOfChildren }

for i := 1 to N do pCurr^.mpChild[i] := nil;

{$ENDIF}

 

{$IFDEF DynamicArrayOfChildren }

Finalize(pCurr^.mpChild);

{$ENDIF}

 

{$IFDEF ListOfBrothers}

pCurr^.pChild := nil;

{$ENDIF}

 


ifiDepth = iDepthPrev then

ifiDepth = 0 thenAway(3);

ifiDepth > iDepthPrev then

ifiDepth <> iDepthPrev+1 thenAway(4);

// У бабушки не может быть внуков (правнуков и т.д.), если у неё не было детей

end;

 

SetLength(mPath, iDepth+1);

end;

 

mPath[iDepth] := pCurr;

 


ifiDepth > 0 then

pParent := mPath[iDepth-1];

// Фиксируем родителя

 

{$IFDEF StaticArrayOfChildren }

Inc(npChild);

if npChild > N then Away(5);

pParent^.mpChild[npChild] := pCurr;

{$ENDIF}

 

{$IFDEF DynamicArrayOfChildren }

i := Length(pParent^.mpChild);

SetLength(pParent^.mpChild, i+1);

pParent^.mpChild[i] := pCurr;

{$ENDIF}

 


{$IFDEF ListOfBrothers}

pAux := pParent^.pChild;

 

ifpAux = nil then

// Это будет первый (старший) из потомков родителя

pParent^.pChild := pCurr

// Это будет последний (младший) из потомков родителя

whilepAux^.pNext <> nil do

pAux := pAux^.pNext;

// Прошли по списку «братьев» до самого младшего

 

pAux^.pNext := pCurr;

// Линейный список «братьев» пополнен НОВЫМ младшим «братом»

end;

 

pCurr^.pNext := nil;

// Нет ещё более младших «братьев»

{$ENDIF}

// iDepth = 0

ifpRoot <> nil thenAway(6);

 

pRoot := pCurr;

end;

 

iDepthPrev := iDepth;

end;

 

CloseFile(F);

 

Finalize(mPath);

end;

procedureMyTableProc(varpThis: pMyTreeNode);

// Пополнение (корректировка) таблицы посещаемости ключей дерева

i, j: integer;

i := Length(mTable);

 

forj := 0 toi-1 do

ifpThis^.iKey = mTable[j].iKey then

Inc(mTable[j].nKey);

exit;

end;

 

SetLength(mTable, i+1);



mTable[i].iKey := pThis^.iKey;

mTable[i].nKey := 1;

end;

procedureMyIncFreqProc(varpThis: pMyTreeNode);

Inc(pThis^.nKey);

end;

 

procedureMyDelProc(varpThis: pMyTreeNode);

Dispose(pThis);

pThis := nil;

end;

 

procedureMySearchKeyProc(varpThis: pMyTreeNode);

ifpThis^.iKey = iKeySought then

writeln(iKeySought, ‘ was found!’);

end;

 


procedureShowMyTable;

i, j: integer;

i := Length(mTable);

 

forj := 0 toi-1 do

Writeln('iKey=', mTable[j].iKey, ' nKey=', mTable[j].nKey);

end;

 


procedureDetourTree(MyProc: MyProcType);

iDepth: integer;

 

procedureDetourSubTree(pFrom: pMyTreeNode; MyProc: MyProcType);

i: integer;

{$IFDEF ListOfBrothers}

pCurr: pMyTreeNode;

{$ENDIF}

 

fori := 1 toiDepth doWrite(' ');

Writeln(pFrom^.iKey);

 

Inc(iDepth);

 

 

{$IFDEF StaticArrayOfChildren }

fori := 1 tonpChild do

DetourSubTree(pFrom^.mpChild[i], MyProc);

{$ENDIF}

{$IFDEF DynamicArrayOfChildren }

fori := 0 toHigh(pFrom^.mpChild) do

DetourSubTree(pFrom^.mpChild[i], MyProc);

{$ENDIF}

 

{$IFDEF ListOfBrothers}

pCurr := pFrom^.pChild;

whilepCurr <> nil do

DetourSubTree(pCurr, MyProc);

pCurr := pCurr^.pNext;

end;

{$ENDIF}

 

 

Dec(iDepth);

 

MyProc(pFrom);

end;

 

 

iDepth := 0;

DetourSubTree(pRoot, MyProc);

end;

 

nAux := 0;

{$IFDEF StaticArrayOfChildren }

Inc(nAux);

{$ENDIF}

 

{$IFDEF DynamicArrayOfChildren }

Inc(nAux);

{$ENDIF}

 

{$IFDEF ListOfBrothers}

Inc(nAux);

{$ENDIF}


if nAux <>1 then Away(0);

// Следует «включать» один и только один из этих трех режимов

 

pRoot := nil;

ReadTree;

Readln;

 

Finalize(mTable);

DetourTree(MyTableProc);

Readln;

 

ShowMyTable;

Readln;

 

iKeySought := '77';

DetourTree(MySearchKeyProc);

Readln;

end.


Двоичные деревья

 

Двоичное дерево может состоять, например, из узлов типа

MyNodeType = record

iKey: integer;

pLeft, pRight: pMyNodeType;

end;

Здесь поле iKey – ключ узла, значение этого поля должно быть уникальным в дереве, поля pLeft, pRight – ссылки на левого и правого потомков. Эти ссылки принимают значение nil, если потомков у узла нет.

Традиционно, тип-ссылка объявляется перед объявлением типа, на который эта ссылка ссылается:

pMyNodeType = ^MyNodeType;

 

 

Обход двоичного дерева

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

 

procedureDetour(pStart: pMyNodeType);

WriteLN(pStart^.iKey);

Detour(pStart^.pLeft);

Detour(pStart^.pRight);

end;

 

Оператор WriteLN(pStart^.iKey) доступен в консольном режиме и показан в качестве простейшего примера; вместо него может быть применен какой-нибудь другой.

Первый экземпляр процедуры (например Detour(pRoot) вызывается по отношению к переменной, которая указывает на корень всего дерева (например, pRoot).

Показанный вариант процедуры Detour понятен, но не очень удобен. Ключи располагаются на экране строго один под другим. Хорошо бы вывод ключей на экран вести так, чтобы полученная картина была похожа на дерево. Простейшим путем этого можно достичь, отступая от края экрана (при выводе ключа) на столько позиций, какова глубина выводимого узла. Например, «подправленная» процедура обхода

 

procedureDetour(pStart: pMyNodeType; Level: integer);

var i: integer;

for i:=1 to Level do Write(Chr(32)); // В начале строки “Level” пробелов

WriteLN(pStart^.iKey);

Detour(pStart^.pLeft, Level + 1);

Detour(pStart^.pRight, Level + 1);

end;

 

впервые вызывается в виде Detour(pRoot, 0).

 


Дерево поиска

 

Деревом поиска называется двоичное дерево, подчиняющееся требованиям:

· для ключевых полей узлов определены отношения «больше» – «меньше» – «равно»,

· ключ каждого из узлов больше ключа левого потомка (если он есть) и меньше ключа правого потомка (если он есть).

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

 

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

Сбалансированное дерево иногда именуется АВЛ-деревом (см ссылку http://ru.wikipedia.org/wiki/%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE).

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


programProject2;

{$APPTYPE CONSOLE}

 

SysUtils;

 

 

pMyNodeType = ^MyNodeType;

MyNodeType = record

iKey: integer;

nKey: integer;

pLeft, pRight: pMyNodeType;

end;

 

 

pRoot: pMyNodeType;

mItem: array ofpMyNodeType;

nItem: integer;

 

procedureReadItems;

F: TextFile;

pCurr: pMyNodeType;

Finalize(mItem);

nItem := 0;

 

AssignFile(F, 'Tree2.txt');

Reset(F);

 

<== предыдущая лекция | следующая лекция ==>
While notEOF(F) do | Сущность экономического роста, его измерение

Дата добавления: 2014-01-03; Просмотров: 209; Нарушение авторских прав?


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2020) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.017 сек.