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

@kation · Регистрация: 26.10.2014

Студворк — интернет-сервис помощи студентам

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

C++
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 <iostream>
#include <conio.h>
#include <cmath>
 
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 (x<MyTree->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<<tree->x<<endl;
    
    
    Show(tree->r); 
}
 
  /*void Show(Node *&tree) // Обход в прямом порядке
{
    if (NULL==tree)    return;    //Если дерева нет, выходим
   
    cout<<tree->x<<endl; //Посетили узел
    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))" << endl;
 for(int menu=0;menu==0;)
 {
 cin >> n;
 if(n>1)
 {menu++;}
 else
 {cout << "Введено неправильное кол-во узлов. Попробуйте еще." << endl;}
 }
  for (int i=0;i<n;i++) 
  {
      cout<<"Vvedite element #"<< i+1 << " : "; 
      cin>>x; 
      add(x,MyTree); 
  }
 
  Show(MyTree); // Простой обход
 how_much=lookup(MyTree);
 
 cout << " Высота данного бинарного дерева : " << how_much << endl ;
 
 
  getch ();
  
}

@Геомеханик · 09.12.2015, 20:25

Сообщение от kation

Хотя должно вывести : 5

Всё правильно, именно 5.

C++
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
#include <iostream>
 
struct Node {
    Node* l, *r;
    char  x;
};  
void Node_Add(Node*& p, char x);
void Node_Clear(Node* p);
int  Node_Height(const Node* p);
 
int main(void){
    char s[] = "feacdfb";
    Node* tr = NULL;
    for(const char* i = &s[0]; *i; ++i)
        Node_Add(tr, *i);
 
    std::cout << "height: " << Node_Height(tr) << std::endl;
    Node_Clear(tr);
    return 0;
}
 
//вставка
void Node_Add(Node*& p, char x){
    if(p == NULL){
        p = new (std::nothrow) Node();
        if(p != NULL){
            p->l = p->r = NULL;
            p->x = x;
        }
    } else if(x < p->x)
        Node_Add(p->l, x);
    else
        Node_Add(p->r, x);
}
 
//удаление всех
void Node_Clear(Node* p){
    if(p != NULL){
        if(p->l != NULL)
            Node_Clear(p->l);
        if(p->r != NULL)
            Node_Clear(p->r);
        delete p;
    }
}
 
//высота дерева
int Node_Height(const Node* p){
    int l, r, h = 0;
    if(p != NULL){
        l = Node_Height(p->l);
        r = Node_Height(p->r);
        h = ((l > r) ? l : r) + 1;
    }
    return h;
}

Пример работы кода

@kation · 09.12.2015, 20:56 **[ТС]**

Ну, я и говорю что пять, просто мне интересно, почему у меня выводит именно два, а не пять ? Х)

Добавлено через 26 минут

Сообщение от Геомеханик

Всё правильно, именно 5.
C++

C++
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
#include <iostream>
struct Node {
 Node* l, *r;
 char x;
}; 
void Node_Add(Node*& p, char x);
void Node_Clear(Node* p);
int Node_Height(const Node* p);
int main(void){
 char s[] = "feacdfb";
 Node* tr = NULL;
 for(const char* i = &s[0]; *i; ++i)
 Node_Add(tr, *i);
std::cout << "height: " << Node_Height(tr) << std::endl;
 Node_Clear(tr);
 return 0;
}
//вставка
void Node_Add(Node*& p, char x){
 if(p == NULL){
 p = new (std::nothrow) Node();
 if(p != NULL){
 p->l = p->r = NULL;
 p->x = x;
 }
 } else if(x < p->x)
 Node_Add(p->l, x);
 else
 Node_Add(p->r, x);
}
//удаление всех
void Node_Clear(Node* p){
 if(p != NULL){
 if(p->l != NULL)
 Node_Clear(p->l);
 if(p->r != NULL)
 Node_Clear(p->r);
 delete p;
 }
}
//высота дерева
int Node_Height(const Node* p){
 int l, r, h = 0;
 if(p != NULL){
 l = Node_Height(p->l);
 r = Node_Height(p->r);
 h = ((l > r) ? l : r) + 1;
 }
 return h;
}

Ладно, хоть переписал под себя твой код и все заработало, спасибо :3

Может кому поможет сдать лабу, я поделюсь таким кодом (Просто пример выше переписал под динамику Х) )

C++
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
#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <iostream>
 
using namespace std;
 
struct Node {
    Node* l, *r;
    char  x;
};  
void Node_Add(Node*& p, char x);
void Node_Clear(Node* p);
int  Node_Height(const Node* p);
 
int main(void){
 
    Node* tr = NULL;
    
 setlocale(LC_ALL,"Russian"); // Моё
    int n,how_much; 
    char x;
 
 cout << "Сколько узлов будет в дереве ? (Введите кол-во узлов (min : 2))" << endl;
 for(int menu=0;menu==0;)
 {
 cin >> n;
 if(n>1)
 {menu++;}
 else
 {cout << "Введено неправильное кол-во узлов. Попробуйте еще." << endl;}
 }
 char *s = new char[n];
  int count=0;
     for(; count<n; count++)
     {
         cout << "Введите элемент #" << count+1 << " : ";
         cin >> s[count];
        Node_Add(tr, s[count]);
     }
 
    cout << "height: " << Node_Height(tr) << std::endl;
    Node_Clear(tr);
    delete []s;
    getch ();
    return 0;
}
 
//вставка
void Node_Add(Node*& p, char x){
    if(p == NULL){
        p = new (std::nothrow) Node();
        if(p != NULL){
            p->l = p->r = NULL;
            p->x = x;
        }
    } else if(x < p->x)
        Node_Add(p->l, x);
    else
        Node_Add(p->r, x);
}
 
//удаление всех
void Node_Clear(Node* p){
    if(p != NULL){
        if(p->l != NULL)
            Node_Clear(p->l);
        if(p->r != NULL)
            Node_Clear(p->r);
        delete p;
    }
}
 
//высота дерева
int Node_Height(const Node* p){
    int l, r, h = 0;
    if(p != NULL){
        l = Node_Height(p->l);
        r = Node_Height(p->r);
        h = ((l > r) ? l : r) + 1;
    }
    return h;
}

@Le_ka · 11.04.2021, 13:05

с написать рекурсивную функцию которая определяет высоту дерева Т (На Си\С++)

Новые блоги и статьи Все статьи Все блоги /
Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем	10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .	Перемещение выделенных строк ТЧ из одного документа в другой Maks 31.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .	Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .
Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .

@Le_ka 0 / 0 / 0 Регистрация: 19.11.2020 Сообщений: 126
	11.04.2021, 13:05
	с написать рекурсивную функцию которая определяет высоту дерева Т (На Си\С++) 0