Динамични структури от данни, двоично дърво за търсене

дърво # 151; набор от елементи, наречени възли (в този случай един от тях се определя като корен) и взаимоотношения (родител-дете) възли, образуващи йерархична структура. Възли могат да бъдат стойностите на който и да е прост или структуриран вид, с изключение на файла. Възли, които нямат следващ възел, наречени листа.

В двоичен (бинарна) дърво, всеки възел може да бъде свързан с не повече от две други възли. Рекурсивно двоично дърво се определя както следва: двоично дърво или е празен (не съдържа един възел), или съдържа възел наречен корена. както и два независими поддърво - лявото поддърво и дясното-дървото.

Binary търсене дърво може да бъде празно или го има свойството, че основния елемент е по-важно място, отколкото който и да е елемент в лявото-дървото, и по-малка или равна от елементите в дясно-дървото. Каза свойство се нарича характерно свойство на двоично дърво за търсене и има за всеки възел на дървото, включително корена. В това, което следва, ние считаме, само двоично дърво за търсене. Това име двоично търсене дървета, получени по причина, че скоростта на търсене за тях е почти същото като в сортиран масив: O (N) = C • log2n (в най-лошия случай O (N) = N).

Пример. За набор от данни, 9, 44, 0, -7, 10, 6, -12, 45 за изграждане на двоично дърво за търсене.

По дефиниция номер 9 търсене двоично дърво поставено в основата на всички стойности по-малко от неговия - в лявата-дървото, по-голямо или равно - в дясно. Всеки поддърво следващия елемент може да се разглежда като корен и да действа по същия алгоритъм. В резултат на това, ние получаваме

Ние избираме типичните операции на двоично дърво за търсене:

добавяне на елемент в дървото;
премахване на елемент от дърво;
дърво прекосява (печатни елементи и т.н.);
Търсене в дървото.

От определението на двоично дърво рекурсивно, всички тези стандартни операции може да се прилага като рекурсивни подпрограми (на практика, този вариант е най-често се използва). Ние само се отбележи, че използването на рекурсия забави вашата програма, и консумира над памет, когато тя се изпълнява.

Нека двоично търсене дърво е описана от вида на

Ние показваме два варианта да добавят елемент на едно дърво: повтарящ се и рекурсивни.

По същия начин, в C ++.

Има няколко начина да работят около (изпускане) на всички дървесни възли. Три от най-често използваните от тях се нарича заобикаляне на живо (префикс) ред. заобикаляйки обратното (Postfix) начина и заобикаля вътрешния ред (или балансиран разходка). Всеки от заобикаляния се осъществява чрез използване на рекурсия.

По-долу са подпрограма печат елементи на дървото с помощта на преминаването двоично дърво за търсене в обратен ред на.

Прилагане на функция, която връща истина (1) ако даден елемент присъства в дървото, и невярно (0) - в противен случай.

В сравнение с предходната задача да изтриете възел се изпълнява малко по-сложно от едно дърво. Можем да различим два случая премахнете елемент х (в случай на нито един елемент в дървото е дегенерат)

1) възел, съдържащ елемент х. Той има степен на не повече от 1 (възел степен - броят на поддървета, произтичащи от този възел);

2) комплект, съдържащ елемент х. 2 притежава.

Случаят 1 е лесно. Предишна възел е свързан или отстранява с един поддърво на възел (ако възелът се отстранява степен 1), или няма да има поддърво изцяло (ако възелът е 0 градуса).

Много по-трудно, ако отстраненото възел има две поддървета. В този случай е необходимо да се замени подвижен елемент най-дясната елемент на лявото му поддърво.

Забележка. Ако даден елемент се повтаря в дървото няколко пъти, отстранен само първата поява на него.

Разработва процедури за създаването на двоично дърво за търсене, съдържаща наш елементи.

Контролни въпроси и задачи

Какво е рекурсивен алгоритъм?
Какви са части, построени определение на рекурсивен алгоритъм?
Какво е задължително във всеки рекурсивен алгоритъм?
Мога ли да заменя рекурсия итерация? Възможно ли е да се замени итерация рекурсия?
Какъв е принципът на динамичната структура на "дървото"?
Списък на сходствата и различията на динамични структури като "линеен списък", "стек", "дърво".
Избройте структури, които могат да бъдат представени под формата на дърво, които се случват в ежедневието.
Довършете изречението: "Linear списък - едно дърво, което ...".
Прилагане итеративни версии на алгоритмите дървопреработвателни, които са представени в рекурсивно форма.
Напишете рекурсивна процедура, която отпечатва елементите на всички листата на дървото.
Напишете рекурсивна функция, която определя дълбочината на даден артикул в дървото и се връща -1, ако няма такъв елемент.
Напиши рутина, който се печата (еднократно) всички на върха на дървото.
Напиши процедура, която, предвид н брои всички възли на дълбочина н в определения дървото.
Напиши процедура, която определя дълбочината на дървото.

Сайта е създаден в uCoz система