Поиск высоты бинарного дерева

Вычисление высоты бинарного дерева поиска на С++

Никак не могу вывести нормально высоту дерева, уже второй день маюсь, подскажите пожалуйста, в чем проблема ?
Например : Высоту бинарного дерева с узлами f, e, a, c, d, f, b Выводит : 2, Хотя должно вывести : 5

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119

#include "stdafx.h" #include #include #include using namespace std; struct Node { Node *l,*r; char x; }; void add(char x,Node *&MyTree) { if (NULL==MyTree) { MyTree=new Node; MyTree->x=x; MyTree->l=MyTree->r=NULL; } else { if (xMyTree->x) //Если нововведенный элемент x меньше чем элемент x из семечка дерева, уходим влево { if (MyTree->l!=NULL) add(x,MyTree->l); else { MyTree->l=new Node; MyTree->l->l=MyTree->l->r=NULL; MyTree->l->x=x; } } if (x>=MyTree->x) //Если нововведенный элемент x больше чем элемент x из семечка дерева, уходим вправо { if (MyTree->r!=NULL) add(x,MyTree->r); else { MyTree->r=new Node; MyTree->r->l=MyTree->r->r=NULL; MyTree->r->x=x; } } } } //Обход в инфиксном порядке void Show(Node *&tree) { if (NULL==tree) return; Show(tree->l); cout->x; Show(tree->r); } /*void Show(Node *&tree) // Обход в прямом порядке   if (NULL==tree) return; //Если дерева нет, выходим coutx  Show(tree->l); //Обошли левое поддерево Show(tree->r); //Обошли правое поддерево >*/ int lookup(Node *&tree) { int h1=0,h2=0; if (NULL==tree) {return 0; } if(tree->l){h1=lookup(tree->l);} if(tree->r){h1=lookup(tree->r);} return(max(h1,h2)+1); } void main() { setlocale(LC_ALL,"Russian"); int n,how_much; char x; Node *MyTree=NULL; cout  <"Сколько узлов будет в дереве ? (Введите кол-во узлов (min : 2))"  ; for(int menu=0;menu==0;) { cin >> n; if(n>1) {menu++;} else {cout  <"Введено неправильное кол-во узлов. Попробуйте еще."  ;} } for (int i=0;in;i++) { cout<"Vvedite element #" +1  <" : "; cin>>x; add(x,MyTree); } Show(MyTree); // Простой обход how_much=lookup(MyTree); cout  <" Высота данного бинарного дерева : "   ; getch (); }

Источник

how to find the height of a node in binary tree recursively

this is my sample code for find the Height, is defined as the length of the longest path by number of nodes from self to a leaf. The height of a leaf node is 1. it doesn’t work.

Actually, I just need an algorithm. Because, my code doesn’t work. And if you know the solution, maybe pseudo code 😛

@thg435 My guess is: «why doesn’t it work?» The poster seems to be struggling with English, so I would give him a break here. That being said, I wouldn’t give the code (since it looks like a homework to me), but explain some of the more blatant mistakes that he made.

@TGulmammadov: two options. Option 1: draw a tree on a piece of paper and try to find the height for any given node manually. Note your steps. Try to describe what you’re doing first in pseudocode and then in python. Option 2: sit back and wait for some nice guy to post the codez for you.

Do you have an example where it fails? How does it fail? Let me guess: it always counts the depth of the leftmost path, not of arbitrary paths?

6 Answers 6

What you’re doing isn’t recursive, it’s iterative. Recursive would be something like:

def height(node): if node is None: return 0 else: return max(height(node.left), height(node.right)) + 1 

return max(height(node.left), height(node.right)) + 1 returns a value >= 1 however leaf nodes have height zero. @mata Could you please clarify. Thanks.

@harishvc — Looking at the edit history, I had return -1 , which means a leaf would have a height of 0 (which is usually how the hight of a tree is defined), but the OP specified «The height of a leaf node is 1», so that’s probably why I changed it.

A leaf node will have None for node.left and node.right , therefore ending the recursion there, there’s no need to treat leaf or inner or root nodes differently.

@Illusionist — for any node the height ist the height of it’s largest child tree (that’s what the max function does) + 1. For a leaf node where both node.left and node.right are None heigh will return 0 for both and the recursion ends there.

You were given the solution by mata, but I suggest you also look at your code and understand what it is doing:

 while self.right != None: self = self.right path = path +1 

What will this do? it will find the right child, then its right child, and so on. So this checks only one path of the «rightmost» leaf.

This does the same for the left:

 while self.left != None: self = self.left path = path +1 

The idea in recursion is that for each subproblem, you solve it using the exact same recipe for all other subproblems. So if you would apply your algorithm only to a subtree or a leaf, it would still work.

Also, a recursive definition calls itself (although you can implement this with a loop, but that is beyond the scope here).

Recursion: see definition of Recursion.

Источник

Как найти высоту бинарного дерева ( поиска )

Кстати, хочу заметить, что высота определяется одним и тем же алгоритмом независимо от того, является ли дерево поисковым или просто двоичным деревом.

То есть алгоритм не привязан к значению ключей узлов рассматриваемого двоичного дерева.

➡ Так как значения ключей вершин дерева ни на что не влияют, то я буду оперировать анонимным бинарным деревом при рассмотрении алгоритма нахождения высоты двоичного дерева.

Рисунок — стандартное анонимное бинарное дерево ( поиска )

А что, собственно, понимают под высотой бинарного дерева?

Высота двоичного дерева — это количество ветвей между его корнем и наиболее глубоко расположенным листовым узлом ( этот лист лежит на самом нижнем уровне ). Связи между узлами дерева называют ветвями ( реже ребрами ).

Для анонимного двоичного дерева, представленного на рисунке выше, высота будет иметь такое представление ( с точки зрения ветвей ):

Рисунок — анонимное двоичное дерево с высотой, выраженной через ветви

Следовательно, рассматриваемое анонимное бинарное дерево ( поиска ) имеет высоту, равную $4$:

Рисунок — анонимное бинарное дерево высотой $4$

💡 Но, лично мне, крайне интересно понять, а чему, например, будет равна высота пустого двоичного дерева, или дерева, в котором только одна вершина! Эти моменты крайне важно понимать при анализе алгоритма, так как они являются своего рода пограничными.

Если бинарное поисковое дерево пустое, то есть не содержит ни одного элемента, то принято его высоту считать равной $-1$:

Если бинарное дерево состоит только из одной вершины, то по определению высота такого дерева равна $0$. Некоторые новички в программировании и структурах данных ошибочно считают, что такое дерево имеет высоту, равную $1$. Но это неправильно. Только $0$.

Рисунок — бинарное дерево высоты $0$

Хочу подытожить некоторую информацию относительно высоты бинарного дерева:

#	Количество вершин в двоичном дереве	Как рассчитывается высота дерева
$1$	$0$ ( пустое дерево )	$-1$
$2$	$1$	$0$
$3$	$>1$	по формуле

➡ Очевидно, что моя задача понять, по какой формуле следует рассчитывать высоту заданного двоичного дерева.

Учитывая, что древовидные структуры крайне удобно обрабатывать рекурсивно, то я буду мыслить в сторону рекурсивной обработки.

В результате долгих размышлений и анализа у меня получилась следующая рекурсивная функция ( каскадная рекурсия ):

➡ Подобные реализации я всегда отношу к разряду сложных, так как «за кулисами» работы рекурсии скрыто куча важнейших мелочей. Правильно и быстро программировать такие функции — достаточно сложная задача, требующая высокой квалификации программиста.

А сейчас я распишу логику этого алгоритма в табличной форме, чтобы улучшить читателям понимание принципа работы рекурсивной функции Height().

Для этого мне потребуется рассмотреть не анонимное двоичное дерево, а «нормальное», у которого узлы имеют конкретные значения ключей. Например, я хочу рассмотреть такое двоичное дерево поиска ( ключами выступают целые числа ):

Рисунок — двоичное дерево поиска ( «красный» путь показывает высоту дерева )

Анализирую логику алгоритма вычисления высоты двоичного дерева в табличной форме ( в данном случае эта форма наиболее наглядная и понятная ):

#	Ключ	Формула	Высота
$1$	$100$	max( Height( $50$ ), Height( $150$ ) ) + $1$	$?$
$2$	$50$	max( Height( $25$ ), Height( $75$ ) ) + $1$	$?$
$3$	$150$	max( Height( $125$ ), Height( $200$ ) ) + $1$	$?$
$4$	$25$	лист	$0$
$5$	$75$	max( Height( $63$ ), Height( $87$ ) ) + $1$	$?$
$6$	$125$	лист	$0$
$7$	$200$	max( Height( $190$ ), Height( NULL ) ) + $1$	$?$
$8$	$63$	лист	$0$
$9$	$87$	max( Height( NULL ), Height( $90$ ) ) + $1$	$?$
$10$	$190$	лист	$0$
$11$	$90$	лист	$0$

Сейчас я буду подниматься снизу вверх по этой таблице, подставляя известные значения в формулы. Ответ, который меня интересует, будет получен в самой верхней строке таблицы. Я выделю это значение красным цветом.

➡ Напомню, что высота несуществующего двоичного дерева составляет $-1$, то есть Height( NULL ) = $-1$.

#	Ключ	Формула	Высота
$1$	$100$	max( Height( $50$ ), Height( $150$ ) ) + $1$	$4$
$2$	$50$	max( Height( $25$ ), Height( $75$ ) ) + $1$	$3$
$3$	$150$	max( Height( $125$ ), Height( $200$ ) ) + $1$	$2$
$4$	$25$	лист	$0$
$5$	$75$	max( Height( $63$ ), Height( $87$ ) ) + $1$	$2$
$6$	$125$	лист	$0$
$7$	$200$	max( Height( $190$ ), Height( NULL ) ) + $1$	$1$
$8$	$63$	лист	$0$
$9$	$87$	max( Height( NULL ), Height( $90$ ) ) + $1$	$1$
$10$	$190$	лист	$0$
$11$	$90$	лист	$0$

В итоге хочу продемонстрировать бинарное дерево, у которого для каждой вершины проставлена соответствующая высота:

Рисунок — бинарное дерево с простановкой высот для каждой вершины

Еще хотелось бы пояснить за вычислительную сложность рассмотренного алгоритма. Очевидно, что в процессе вычисления высоты дерева приходится обойти каждый его узел, следовательно, вычислительная сложность составляет $O( n )$, где $n$ — количество вершин дерева.

Существуют ли более эффективные алгоритмы, чем $O( n )$? Возможно, но я таких не знаю 😎

Пишите в комментариях, все ли понятно по алгоритму нахождения высоты бинарного дерева, а также рассказываете, в каких случаях на практике вам потребовалось определять высоту дерева.

ВНИМАНИЕ

Для заказа программы на двоичное дерево ( поиска ) пишите на мой электронный адрес proglabs@mail.ru

Источник