МIНIСТЕРСТВО ОСВIТИ І НАУКИ УКРАЇНИ Національний унiверситет "Львiвська полiтехнiка"
СТВОРЕННЯ I ВЕДЕННЯ БІНАРНИХ ДЕРЕВ 1. МЕТА РОБОТИ Ознайомитися iз способом подання даних в оперативнiй пам'ятi ЕОМ у виглядi бінарних дерев. Оволодiти методами роботи iз бінарними деревами. 2. КОРОТКІ ТЕОРЕТИЧНI ВIДОМОСТI Для описання будь-якої структури, яка характеризується ієрархiчними зв'язками, є корисними дерева. Дерево - це визначена множина одного чи кількох вузлів, таких, що: Є спеціально визначений вузол, що називається коренем. Інші вузли є розділениними на підмножини, що не перетинаються Т1, Т2, Т3,..., Тn (n>=0), кожна з яких є деревом. Кожне Ті(1<=i<=n) називається піддеревом вузла. Рівнем вузла є 1 плюс довжина шляху до нього від кореня. Степенем вузла є кількість піддерев, які з нього виходять. Впорядкованим називається дерево, у якого вузли на кожному рівні впорядковані певним чином. Якщо видалити корінь із гілками, то отримується множина незв'язаних дерев. Кожен набір незв'язаних дерев називається лісом. Бінарним деревом називається множина m (m>=0) вузлів, що є або порожньою (m=0), або містить кореневий вузол, який має два незв'язаних бінарних піддерева, що називається лівим піддеревом і правим піддеревом. Бінарне дерево, у якого кожний вузол має степінь 0 чи 2, називається повністю бінарним деревом. Оскільки бінарні дерева легко зображати і маніпулювати з ними, зручно перетворити будь-яке дерево в еквівалентну бінарну форму (якщо можливо). 2.1. Процедура претворення дерева у бінарний еквівалент Крок 1. Видаляються всі гілки, якi виходять із вузлів, крім найлівіших для кожного вузла, що породжує їх. Крок 2. Вибір правого і лівого нащадка для кожного вузла: лівий нащадок є вузлом, що знаходиться під вузлом. Правий нащадок міститься одразу праворуч на одній горизонтальній прямій із заданим вузлом. 2.2. ВСТАВКА У БІНАРНЕ ДЕРЕВО Припустимо, що бажане дерево має зберігатися у певнiй послiдовностi. Наприклад, потрібно зберігати список імен у лексичній послідовності. Це означає, що ліве піддерево дерева (або піддерева) має містити вузли, чиї імена є лексично меншими, ніж ім'я кореневого вузла дерева (піддерева). Праве піддерево міститиме вузли, чиї імена є лексично більшими, ніж ім'я у корені дерева (піддерева). ІНДИВІДУАЛЬНЕ ЗАВДАННЯ Сформувати бінарне дерево і посортувати його в порядку зростання. Текст програми Program l3; const n=16; Type pt=^uzl; uzl=Record lson, rson: pt; kl:byte; End; Var j:word; y:uzl; coren:pt; Procedure Vkl(Var cor:pt; y:uzl); Var nov,ss,tt: pt; b: Boolean; Begin New(nov); nov^:=y; If cor = Nil Then cor:=nov Else Begin tt:=cor; Repeat ss:=tt; b:=y.kl < ss^.kl; If b Then tt:= tt^.lson Else tt:=tt^.rson Until tt = Nil; If b Then ss^.lson:=nov Else ss^.rson:=nov End; End; Procedure Obrab(ss:pt); Begin Write(ss^.kl:5) End; Procedure Obhod(ss:pt); Type pnt=^z; z=Record sl:pt; ssl:pnt End; Var tt: pt; q,t: pnt; Begin t:=Nil; Repeat While ss <> Nil do Begin While ss^.lson <> Nil do Begin New(q); q^.sl:= ss; q^.ssl:= t; t:= q; ss:= ss^.lson End; Obrab(ss); ss:= ss^.rson End; q:= t; If t <> Nil Then Begin ss:=t^.sl; t:= t^.ssl; Dispose(q); Obrab(ss); ss:= ss^.rson End; Until q=Nil End; Begin Randomize; coren:=Nil; y.lson:=Nil; y.rson:=Nil; writeln(' rezyltat binarnogo dereva'); For j:= 1 to n do Begin y.kl:=Random(50); Vkl(coren, y) End; Obhod(coren); readln; end. Висновок Виконав[ім’я автора приховано]