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

@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

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

Новые блоги и статьи Все статьи Все блоги /
Java и Eclipse Store: Сверхбыстрые приложения с In-Memory DB Javaican 15.07.2025 Eclipse Store — это микро-движок персистентности для Java, который позволяет хранить и извлекать нативные Java-объекты без необходимости преобразования данных или использования объектно-реляционного. . .	EmBitz, создание проекта, отладка, прошивка locm 15.07.2025 Создание проекта для Blue Pill (STM32F103C8T6) в EmBitz 2. 30, написания кода blink, запуск отладки в ОЗУ, заливка релизной прошивки во flash используя ST-Link и др. . . .	Трассировка корутин Kotlin с OpenTelemetry mobDevWorks 14.07.2025 Асинхронное программирование меняет правила игры, особенно когда речь заходит о трассировке операций. В Kotlin с его корутинами эта проблема приобретает особый оттенок, который я хотел бы детально. . .	Облачные приложения на Rust: руководство по архитектуре микросервисов golander 13.07.2025 Когда я впервые взялся за проектирование облачной платформы для одного из наших клиентов, выбор стоял между привычными Go и Java. Но после нескольких месяцев разработки микросервисной системы,. . .	Как Node.js выполняет асинхронные операции Reangularity 13.07.2025 Каждый раз, когда я рассказываю про Node. js, возникает один и тот же вопрос: "Как эта штука может быть быстрой, если JavaScript — однопоточный язык?" И это действительно кажется парадоксом. Ведь в. . .
Как писать чистый, тестируемый и качественный код на Python py-thonny 12.07.2025 Помню свой первый проект на Python. Работал тогда быстро, грязно, лишь бы работало. Код был похож на запутанный клубок - переменные по одной букве, функции на 200 строк, комментарии отсутствовали как. . .	Blazor и контроллер сервопривода IoT Meadow Maple Wired 11.07.2025 Я решил разобраться, как можно соединить современные веб-технологии с миром "железа". Интересная комбинация получилась из Blazor в качестве веб-интерфейса и микроконтроллера Meadow с его веб-сервером. . .	Генерация OpenQASM из кода Q# EggHead 10.07.2025 Летом 2024-го я начал эксперименты с библиотекой Q# Bridge, и знаете что? Она оказалась просто находкой для тех, кто работает на стыке разных квантовых экосистем. Основная фишка этой библиотеки -. . .	Изучаем новый шаблон ИИ-чата .NET AI Chat Web App stackOverflow 10.07.2025 В . NET появилось интересное обновление - новый шаблон ИИ-чата под названием . NET AI Chat Web App. Когда я впервые наткнулся на анонс этого шаблона, то сразу понял, что Microsoft наконец-то. . .	Результаты исследования от команды ARP (июль 2025 г.) Programma_Boinc 10.07.2025 Результаты исследования от команды ARP (июль 2025 г. ) Африканский проект по дождям (ARP) World Community Grid снова запущен! Мы рады поделиться обновленной информацией о нашем прогрессе с осени. . .

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