Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 4.67
eddilou
3 / 3 / 1
Регистрация: 21.11.2010
Сообщений: 194
#1

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

26.03.2012, 01:53. Просмотров 3420. Ответов 5
Метки нет (Все метки)

всем привет, дано такое задание:
Напишите программу, которая формирует бинарное дерево поиска, выводит построенное дерево на экран и подсчитывает число вершин на 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");
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.03.2012, 01:53
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Вывести число вершин n-го уровня (Бинарное дерево поиска) (C++):

Исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру
Помогите, не могу понять!( Нужно исходное бинарное дерево превратить в...

Бинарное дерево поиска.Вывести слова с тремя гласными
Доброго времени суток. Помогите с задачей пожалуйста. Вот условие: В...

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

Бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой
Дано бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся...

Данные из массива структур Date передать в бинарное дерево поиска и вывести его при помощи обратного обхода
Доброго времени суток! Задание:Данные из массива структур Date передать в...

Бинарное дерево. Найти среднее арифметическое указанного уровня
Доброго времени суток. Необходимо найти среднее арифметическое указанного...

5
panicwassano
594 / 562 / 104
Регистрация: 07.11.2010
Сообщений: 2,004
26.03.2012, 09:02 #2
пройдитесь там дебаггером и посмотрите почему не дают, каковы значения перменных на этом шаге
0
Duha666
51 / 51 / 19
Регистрация: 10.03.2012
Сообщений: 138
26.03.2012, 09:18 #3
Вообщем, дело в том, что вместо проверки на несуществования вершины в дереве вы делаете обратное и все валится.
Замените везде в удалении 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;
}
0
eddilou
3 / 3 / 1
Регистрация: 21.11.2010
Сообщений: 194
26.03.2012, 22:16  [ТС] #4
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 уровне...
нашел там с помощью стека но не понял смысла реализации как можно использовать стек и обход в ширину чтоб узнать сколь элементов на н уровне.. подскажите оч надо плиз
заранее спс
0
Kuzia domovenok
2209 / 1978 / 441
Регистрация: 25.03.2012
Сообщений: 6,944
Записей в блоге: 1
26.03.2012, 22:21 #5
Ну у тебя же есть функция TreeShow(BSTree *t, int lvl ) Вот аналогично и выводи.

Только сделай условие, чтобы cout<<
вызывался только если lvl==n
0
eddilou
3 / 3 / 1
Регистрация: 21.11.2010
Сообщений: 194
27.03.2012, 07:28  [ТС] #6
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Ну у тебя же есть функция TreeShow(BSTree *t, int lvl ) Вот аналогично и выводи.

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

Добавлено через 9 часов 2 минуты
разве никто не может ничем помочь или подсказать??...
0
27.03.2012, 07:28
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.03.2012, 07:28
Привет! Вот еще темы с решениями:

Бинарное дерево поиска
#include &lt;iostream&gt; using namespace std; struct node { int key; ...

Бинарное дерево поиска C++
+Доброго времени суток! У меня есть задание:создать картотеку,в ней указать...

Бинарное дерево поиска
В текстовом файле содержится произвольный текст. Построить на его основе...

Бинарное дерево поиска
Давайте рассмотрим некоторый пример Допустим есть числа от 0 до 99 которые...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru