Св-во. Дълж.на външ.пътища в вс.бинар. дърво с N вътр.възела е с 2N по-гол. от дълж.на външ.пътища-Док.се по индукция
Св-во. Височ.на бинар.дърво с N вътр.възела е >= от lgN и <= N-1
Док.Най-лошия сл.е дегенерирано дърво с 1листо,с N-1 връзки от корена до листото. Най-добрият сл.е балансирано дърво с 2 i вътр.възли за всяко ниво i,освен за най-долното.Ако височ.е h,трд имаме:
2 h-1 < N+1 <= 2 h Тъй като имаме N+1 външ.възела. Височ. в най-добрия сл.ще е = lgN
Св-во. Дълж.на вътр.пътища в бинар. дър-во с N вътр.въз.е>=Nlg(N/4) и <=N(N-1)/2
Бинар.дърв.се появяват мн.често в комп. прилож.и произв-стта е best при баланс.дър
Обхожданенадървоиграф.
Ще разгл.алг.за най-осн.обработваща дърв. ф-я:обхождане.При бин.дърв.имаме 2 връз-ки=>3 осн.последов.,по които да посет.въз.
преред – посещ.възела,после лявото и дясното поддърво
постред – посещ.лявото и дясното поддъ-рво и после възела
Тези 3 метода са за обхожд.в дълбочина.Те мд се реализ.чрез рекурс.прог:
void traverse (link h, void ( *visit)(link))
{if(h==NULL)return;(*visit)(h);
traverse (h->l, visit); traverse (h->r, visit); }
Тази рекурс.ф-я взема връзка към дърво като арг.и вика ф-ята visit с арг.всеки от въз-лите на дървото..Ако премест.викането на visit м/у рекурс.обръщ.,имаме поредно обхожд., а ако премест.след тях,имаме постред.обхож.
При използ.на нерекурс.,които използ.стек, правим опер.за вмъкване на дървото,които зав.от желаната последов.на обхожд:
преред – вмък.в стека дясното поддърво после лявото и накрая възела
постред – вмък.в стека възела,после дяс-ното поддърво и накрая лявото поддърво. В стека не се вмък.нулевите връзки.
Друга стратегия за обхожд.е просто да посещаваме възлите отгоре надолу и отляво надясно – обхождане в широчина,защото вс.възли от дадено ниво се появяват заедно
