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

@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

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

Новые блоги и статьи Все статьи Все блоги /
Подключение Box2D v3 к SDL3 для Android: физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .
Влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .

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