Николай Ненков
преподава по Математика
в град Варна
Големина на текста:
Йерархични структури от данни
двоично дърво и граф
1.Двоично дърво
Логическо описание
Двоично дърво от тип Т е структура от данни, която е или празна,
или е образувана от
- данна от тип T, наречена корен (връх) на двоичното дърво от тип
Т;
- двоично дърво от тип T, наречено ляво поддърво на двоичното
дърво от тип Т (ЛПД);
- двоично дърво от тип T, наречено дясно поддърво на двоичното
дърво от тип Т (ДПД).
Примери:
Нека a, b, c, d, e, f и g са данни от тип Т. Тогава следните
графични представяния определят двоични дървета от тип Т.
а) аб) а в) а
b c b
d e c
f gd
Посоката на линиите, свързващи върховете с поддървета, позволява да
се различи ляво от дясно поддърво. Двоичните дървета
aa
и
b b
са различни. В единия случай дясното поддърво е празно, а в другия -
дясното дърво не е празно.
Някои определения
Листо - това е връх с празни поддървета.
Пример: Върховете d, c, f и g
а
b c
d e
f g
са листа.
Върховете, които не съвпадат с корена и листата, се наричат
вътрешни върхове.
Пример: b и e, от примера по-горе, са вътрешни върхове на
двоичното дърво от тип Т.
Всяко поддърво се нарича наследник (син) по отношение на своето
дърво и родител (баща) по отношение на своите поддървета.
Над структурата от данни двоично дърво са възможни следните
операции:
- достъп до връх
2
Възможен е пряк достъп до корена и непряк достъп до всеки от
останалите върхове на двоичното дърво.
- включване и изключване на връх
Включването и изключването са възможни в произволно място на
двоичното дърво. В резултат се получава двоично дърво от тип T.
Обхождане на двоично дърво
Обхождането на двоично дърво дава метод, позволяващ да се
осъществи достъп до всеки връх на дървото един единствен път.
Осъществява се чрез изпълнение на следните три действия в някаква
последователност:
- обработка на корена;
- обхождане на лявото поддърво;
- обхождане на дясното поддърво,
т.е. процесът на обхождане е рекурсивен. Съществуват шест различни
начина за обхождане на двоично дърво: ЛКД (смесено обхождане), КЛД
(низходящо обхождане), ЛДК (възходящо обхождане), ДКЛ, КДЛ и ДЛК,
където К - означава корен, Л - ляво поддърво, Д - дясно поддърво.
Обхождането ЛКД например означава, че първо се обхожда лявото
поддърво, след него се обработва коренът и накрая се обхожда дясното
поддърво.
Всеки аритметичен израз може да се представи чрез двоично дърво, в
листата на което са операндите, а във вътрешните върхове и корена -
операциите.
Пример: Изразът x-y/(3-2*a) може да се представи чрез двоично
дърво по следния начин
-
x /
y -
3 *
3

Това е само предварителен преглед

За да разгледате всички страници от този документ натиснете тук.
Последно свалили материала:
ДАТА ИНФОРМАЦИЯ ЗА ПОТРЕБИТЕЛЯ
10 сеп 2021 в 12:54 потребител
 
Домашни по темата на материала
Да се напише програма при която в двумерен масив да се въвежда текст от 5 реда. Да се въведе един символ в променливата ch. Да се определи колко пъти се среща символът ch в текста и на какви места.
добавена от venelinvasilev 27.09.2014
0
4
Подобни материали
 

Задача по C++

24 окт 2006
·
616
·
1
·
208
·
225

Урок по програмиране на Английски език.
 

Програмиране - C и C++

12 дек 2007
·
1,149
·
155
·
36,823
·
853
·
1
·
1
·

С и С++ са най - важните световни програмни езици . Всъщност, за да бъдете професионален програмист днес означава опитност в тези два езика.Те са основата, върху която е изградено модерното програмиране. С беше изобретен от Денис Ричи през 1970г...
 

Основи на входно/изходния интерфейс в среда Windows

09 мар 2006
·
376
·
4
·
684
·
44
·
1

Работа с текст.. Клавиатура.. Мишка.. Таймер..Дъщерни контроли..
 

Проследяване изпълнението и настройване на програми на C/C++ с Turbo Debugger

16 мар 2006
·
153
·
8
·
690
·
57

Проследяване изпълнението и настройване на програми на C/C++ с Turbo Debugger - задачи с решения към тях.
 

Настройване на програми на асемблерен език

16 мар 2006
·
204
·
9
·
1,651

Настройване на програми на асемблерен език - задачи с решения към тях. Упражнение.
1 2 3 4 5 » 11
 
Онлайн тестове по Програмиране
Програмиране в интернет среда (X)HTML и CSS
изпитен тест по Програмиране за Студенти от 3 курс
Тестът е използван в МГУ “Св. Иван Рилски” и включва 30 въпроса, изискващи един верен отговор. Подходящ за проверка на знанията в областта.
(Труден)
30
12
1
5 мин
01.10.2014
ПСТ-1
изпитен тест по Програмиране за Студенти от 3 курс
Тест по ПСТ-1 ТУ София, ИПФ Сливен. Всеки въпрос има само един верен отговор.
(Труден)
21
8
1
3 мин
28.05.2015
» виж всички онлайн тестове по програмиране

Програмиране C++ - глава 16

Материал № 54083, от 09 дек 2007
Свален: 155 пъти
Прегледан: 84 пъти
Качен от:
Предмет: Програмиране, Информатика, ИТ
Тип: Урок
Брой страници: 31
Брой думи: 2,256
Брой символи: 18,577

Потърси помощ за своята домашна:

Имаш домашна за "Програмиране C++ - глава 16"?
Намери бързо решение, с помощтта на потребители на Pomagalo.com:

Намери частен учител

Виторио Белоречки
преподава по Програмиране
в град София
с опит от  4 години
367 40

Николай Ненков
преподава по Математика
в град Варна
с опит от  2 години
516 94

виж още преподаватели...
Последно видяха материала
Сродни търсения