Дървовидни структури съществуват две дефиниции на дървовидна структура или дърво. Нерекурсивна



страница1/4
Дата04.06.2022
Размер1.39 Mb.
#114535
  1   2   3   4
Дървета
Свързани:
топологично сортиране на граф, пропускливост на мрежа, МПТПротоколПлан

ДЪРВОВИДНИ СТРУКТУРИ

Съществуват две дефиниции на дървовидна структура или дърво.
Нерекурсивна: Дърво е свързан граф без цикли.
Рекурсивна: Дърво от тип Т е структура, образувана от данна от тип Т, наречена “корен”, и крайно множество (възможно и празно) елементи - дървета от тип Т, наречени “поддървета”.

Всяко дърво се образува от възли и дъги, които ги свързват. Върховете могат да бъдат от два вида:


- родител
- наследник
Върхът без родител се нарича “корен” и всяко дърво има само един такъв връх.
От всеки връх могат да излизат няколко дъги (техния брой се нарича “степен” на елемента), но влиза само една дъга, т. е. връзката “родител-наследник” е еднопосочна и не позволява цикли:
Оттук се вижда, че структурата едносвързан списък представлява частен случай на дърво или т.н. “изродено” дърво.
Степен на дърво се нарича максималната степен на елемент от тази структура. За горния пример тя е 3.
Върховете без наследници се наричат “листа”.
Височина на дърво е дължината на най-дългия път от корена до листо.
От дефиницията следва, че между два произволни върха в едно дърво съществува единствен път.

Например:



Дървото има степен 2
Височината на дървото е 5
Динамично представяне на структурата дърво (със степен 3):

struct elem


{char key; elem *p1, *p2, *p3;} *root;

В така описаното дърво се съхраняват символни данни. Коренът на дървото е свързан с указателя root. В контекста посочената в примера дефиниция, представеното по-горе дърво може да се изобрази като:




Терминология:

Връх (vertex)


Възел (node)
Ребро (edge)
Дъга (arc)
Път (path)




Най-голямо приложение намира частния случай на дървовидна структура - двоично или бинарно дърво


Двоично дърво е дървовидна структура от степен 2, т.е. всеки възел има не повече от два наследника - ляв и десен:



Динамично представяне на двоично дърво.

struct elem


{char key; elem *left, *right;} *root;
Няколко допълнителни дефиниции:
- Дължина на пътищата в дърво е сумата на нивата на неговите възли (за даденото дърво - 28).
- Дължина на вътрешните пътища в бинарно дърво е сумата от нивата на всички негови вътрешни възли (за даденото дърво - 8).
- Дължина на външните пътища в бинарно дърво е сумата от нивата на всички негови външни възли (за даденото дърво - 20).


Основни математически свойства на двоичните дървета:

- Двоични дървета с N вътрешни възли има N+1 външни възли.


- Двоично дърво с N вътрешни възли има 2N връзки: N-1 връзки към вътрешни възли и N+1 връзки към външни възли.
- Дължината на външните пътища във всяко двоично дърво с N вътрешни възли е с 2N по-голямо от дължината на вътрешните пътища.
- Височината на бинарно дърво с N вътрешни възли е не по-малка от Log2N и не по-голяма от N - 1. Ако височината е h (за даденото дърво - 3), тогава трябва да имаме:


Сподели с приятели:
  1   2   3   4




©obuch.info 2024
отнасят до администрацията

    Начална страница