Дървовидни структури съществуват две дефиниции на дървовидна структура или дърво. Нерекурсивна
Изтегляне 1.39 Mb.
|
Свързани:
топологично сортиране на граф, пропускливост на мрежа, МПТПротоколПлан
- Навигация на страницата:
- PREORDER
| 2h-1 < N +1 <= 2h
Неравенството означава, че височината в най-добрия случай е равна на Log2N, закръглено до най-близкото по-голямо цяло число. - Дължината на вътрешните пътища на двоично дърво с N вътрешни възли е не по-малка от N*Log2 (N/4) и не по-голяма от N*(N-1)/2. Основни операции със структурата дърво . Обхождане на дърво . Добавяне на елемент в дърво . Премахване на елемент от дърво . Търсене на елемент. Инициализация на двоично дърво На указателя към корена на дървото се присвоява стойност NULL при дефинирането на структурата: struct elem {char key; elem *left, *right;} *root=NULL; Обхождане на двоично дърво Обхождането означава посещаване на всеки възел по веднъж. Т.к. дървото е нелинейна структура, обхождането му може да става по различни начини. Различават методи за обхождане в ширина и в дълбочина, като последния се извършва по три стандартни начина: - в прав ред - PREORDER - във вътрешен ред (или симетрично обхождане) - INORDER - в обратен ред - POSTORDER При обхождането в прав ред се възлите се посещават в следната последователност: корен - ляво поддърво - дясно поддърво, което за горния пример на двоично дърво ще даде такава последователност: АBDECF. void preorder(elem *t) { if (t) { cout< preorder(t->left); preorder(t->right); } } Обхождането във вътрешен ред се извършва така: ляво поддърво - корен - дясно поддърво, т.е. за горния пример - DBEACF. Функция за рекурсивно обхождане на двоично дърво във вътрешен ред void inorder(elem *t) { if (t) { inorder(t->left); cout< inorder(t->right); } } Обхождането в обратен ред означава следната последователност на посещаваните възли: ляво поддърво - дясно поддърво - корен, за вече споменатия пример тя е DEBFCA. void postorder(elem *t) { if (t) { postorder(t->left); postorder(t->right); cout< } } Добавяне на елемент в подредено двоично дърво Нови елементи се добавят в структурата във вид на листа. Разгледаната долу операция за добавяне на нов възел в двоично дърво за търсене е реализирана като рекурсивна функция. Изтегляне 1.39 Mb. Сподели с приятели:
|