Вывести число вершин n-го уровня (Бинарное дерево поиска)

@eddilou · Регистрация: 21.11.2010

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

всем привет, дано такое задание:
Напишите программу, которая формирует бинарное дерево поиска, выводит построенное дерево на экран и подсчитывает число вершин на n-ом уровне сформированного дерева. Корень считать вершиной 0-го уровня. Обход дерева выполните с помощью не рекурсивного алгоритма. Данные могут вводиться с клавиатуры, из файла или генерироваться с помощью генератора случайных чисел. Перед завершением работы программы освободить занимаемую динамическую память. Для этого используйте поэлементное удаление элементов динамической структуры данных.

пока пытаюсь реализовать удаление поэлементное
уже мучаюсь целый день, и не могу понять в чем проблема, почему строчка 87 while ( cin >>dig2 ) TRoot=Del(TRoot, dig2);
неправильно срабатывает... не дает ввести элементы которые надо удалить, а просто пропускает, подскажите в чем дело??
заранее спасибо, вот мой код:

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
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <iostream>
#include <string.h>
#include <iomanip>
using namespace std;
 
struct BSTree   
  { 
    int key;
    BSTree *Left; 
    BSTree *Right; 
  };
BSTree *TRoot=NULL;
int lvl=0;
 
BSTree* AddTree(BSTree *t, int k) 
  
{
    if (t == NULL)
        { 
            t = new BSTree; 
            t->Left = NULL; 
            t->Right = NULL; 
            t->key = k;
        }
    else
        if(t->key==k) return t;
        else             
            {
                if (k > t->key ) t->Right=AddTree(t->Right, k);
                else t->Left=AddTree(t->Left, k);   
            }
    return t;
}
 
void TreeShow(BSTree *t, int lvl ) 
{
    int tab = 5;
    if (t == NULL) cout <<"Derevo pusto \n";
    else
        {
            if (t->Right != NULL) TreeShow(t->Right, lvl+1);
            cout <<setw(tab*lvl) <<t->key <<endl;
            if (t->Left != NULL) TreeShow(t->Left, lvl+1);
        }
}
 
BSTree* Del(BSTree* T, int k)
{ BSTree *P, *v;
  if (T!=NULL) cout << "this element in the tree there!" << endl;
  else if (k < T->key) T->Left = Del(T->Left, k);
       else if (k > T-> key) T->Right = Del(T->Right, k);
        else {P = T;
          if (T->Right!=NULL) T = T->Left; // случай 1
          else if (T->Left!=NULL) T = T->Right; // случай 1
               else // случай 2
                            { v = T->Left;
                              if (v->Right)
                              {
                  while (v->Right->Right) v = v->Right; 
                  T->key = v->Right->key;
                  P = v->Right; v->Right = v->Right->Left;
                              }
                              else
                              {
                               T->key = v->key;
                               P = v;
                               T->Left=T->Left->Left;
                              }
                }
          free(P);
         }
 return T;
}
        
 
void main()
{
    int dig, dig2;
    cout <<"Enter the numbers, for the end of any character other than numbers:\n";
    while ( cin >>dig ) TRoot=AddTree(TRoot, dig);
    cout <<endl;
    TreeShow(TRoot, lvl);
    cout <<"Enter number of items you want to delete, for the end of any character other than numbers:\n";
    while ( cin >>dig2 ) TRoot=Del(TRoot, dig2); 
    cout<<endl;
    lvl=0;
    TreeShow(TRoot, lvl);
    system("PAUSE");
}

@panicwassano · 26.03.2012, 09:02

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

@Duha666 · 26.03.2012, 09:18

Вообщем, дело в том, что вместо проверки на несуществования вершины в дереве вы делаете обратное и все валится.
Замените везде в удалении if (что-то != NULL) на if (что-то == NULL) и всё будет как надо

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
BSTree* Del(BSTree* T, int k)
{ BSTree *P, *v;
  if (T==NULL) cout << "this element in the tree there!" << endl; // если такого ключа нет, то ничего не делаем, а не наоборот
  else if (k < T->key) T->Left = Del(T->Left, k);
       else if (k > T-> key) T->Right = Del(T->Right, k);
            else {P = T;
                  if (T->Right==NULL) T = T->Left; // случай 1, подвешиваем левое поддерево, если нет правого
                  else if (T->Left==NULL) T = T->Right; // случай 1, подвешиваем правое поддерево, если нет левого
                       else // случай 2, оба есть. Ну тут все и было хорошо
                            { v = T->Left;
                              if (v->Right)
                              {
                              while (v->Right->Right) v = v->Right;
                              T->key = v->Right->key;
                              P = v->Right; v->Right = v->Right->Left;
                              }
                              else
                              {
                               T->key = v->key;
                               P = v;
                               T->Left=T->Left->Left;
                              }
                            }
                  free(P);
                 }
 return T;
}

@eddilou · 26.03.2012, 22:16 **[ТС]**

Duha666,
спасибо, но проблема не решилась, она открытой и осталась
теперь узнал что надо автоматически удалить все вершины...
без участия пользователя, так понимаю просто убрать вводимый ключ к
НО не могу понять почему игнориться ввод в майне ведь мне он нужен для того чтоб ввести номер уровня чтоб потом использовать обход и выдать пользователю результат о том сколько вершин на n уровне..
вот проблема то .. вроде в начале все норм не игнорится ввод а тут игнорится второй раз
panicwassano, проходил, хоть ставтье любые значения и условия он вообще не заходит в ввод т.е. не исп функцию ни сканф ни син во втоорой раз после построения дерева

Добавлено через 11 часов 30 минут

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
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <iostream>
#include <string.h>
#include <iomanip>
using namespace std;
 
struct BSTree   
  { 
    int key;
    BSTree *Left; 
    BSTree *Right; 
  };
BSTree *TRoot=NULL;
int lvl=0;
 
BSTree* AddTree(BSTree *t, int k) 
{
    if (t == NULL)
        { 
            t = new BSTree; 
            t->Left = NULL; 
            t->Right = NULL; 
            t->key = k;
        }
    else
        if(t->key==k) return t;
        else             
            {
                if (k > t->key ) t->Right=AddTree(t->Right, k);
                else t->Left=AddTree(t->Left, k);   
            }
    return t;
}
 
void TreeShow(BSTree *t, int lvl ) 
{
    int tab = 5;
    if (t == NULL) cout <<"Derevo pusto \n";
    else
        {
            if (t->Right != NULL) TreeShow(t->Right, lvl+1);
            cout <<setw(tab*lvl) <<t->key <<endl;
            if (t->Left != NULL) TreeShow(t->Left, lvl+1);
        }
}
 
void DEL_next(BSTree* T) 
{
    if(T!= NULL) 
        {
            DEL_next(T->Left);
            DEL_next(T->Right); 
            printf("BSTree %d - deleted\n",T->key);
            delete T;
            T=NULL;
        }
    
}
 
void DEL_BSTree() 
{
    if(TRoot!= NULL)
        {
            DEL_next(TRoot->Left);
            DEL_next(TRoot->Right);
            printf("BSTree %d - deleted\n",TRoot->key);
            TRoot->Left=NULL;
            TRoot->Right=NULL;
            delete TRoot;
            TRoot=NULL;
        } 
}
 
void main()
{
    int dig, p, Lv;
    cout<<"Enter the number of nodes of the tree of the future: ";
    cin>>p;
    cout <<"Enter the numbers, for the end of any character other than numbers:\n";
    for(int i=0; i<p; i++)
        {
            cin>>dig;
            TRoot=AddTree(TRoot, dig);
        }
    cout <<endl;
    TreeShow(TRoot, lvl);
    cout <<"Enter level: ";
    cin>>Lv;
    
    
    DEL_BSTree();
    if(TRoot==NULL) cout<<endl<<"Dynamic memory is freed"<<endl<<endl;
    system("PAUSE");
}

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

@Kuzia domovenok · 26.03.2012, 22:21

Ну у тебя же есть функция TreeShow(BSTree *t, int lvl ) Вот аналогично и выводи.

Только сделай условие, чтобы cout<<
вызывался только если lvl==n

@eddilou · 27.03.2012, 07:28 **[ТС]**

Сообщение от Kuzia domovenok

Ну у тебя же есть функция TreeShow(BSTree *t, int lvl ) Вот аналогично и выводи.

Только сделай условие, чтобы cout<<
вызывался только если lvl==n

Видите ли, в задании написано организовать БЕЗ рекурсии обход, а обход связан с нахождением узлов Н уровня и подсчет , а вывод дерева на экран как хочешь так и сделаешь т.е. можно через рекурсию

Добавлено через 9 часов 2 минуты
разве никто не может ничем помочь или подсказать??...

Новые блоги и статьи Все статьи Все блоги /
Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка SDL3 и Box2D из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»

@panicwassano 601 / 569 / 104 Регистрация: 07.11.2010 Сообщений: 2,004
	26.03.2012, 09:02
	пройдитесь там дебаггером и посмотрите почему не дают, каковы значения перменных на этом шаге 0

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,531 Записей в блоге: 1
	26.03.2012, 22:21
	Ну у тебя же есть функция TreeShow(BSTree *t, int lvl ) Вот аналогично и выводи. Только сделай условие, чтобы cout<< вызывался только если lvl==n 0