Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 4.67
eddilou
3 / 3 / 0
Регистрация: 21.11.2010
Сообщений: 194
#1

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

26.03.2012, 01:53. Просмотров 3062. Ответов 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++):

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

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

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

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

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

Бинарное дерево поиска - C++
Решил написать бинарное дерево поиска, но что-то пошло не так, дерево не выводиться не понимаю почему. Вот весь код: #include...

5
panicwassano
592 / 560 / 20
Регистрация: 07.11.2010
Сообщений: 2,004
26.03.2012, 09:02 #2
пройдитесь там дебаггером и посмотрите почему не дают, каковы значения перменных на этом шаге
0
Duha666
51 / 51 / 5
Регистрация: 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 / 0
Регистрация: 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
1892 / 1747 / 119
Регистрация: 25.03.2012
Сообщений: 5,936
Записей в блоге: 1
26.03.2012, 22:21 #5
Ну у тебя же есть функция TreeShow(BSTree *t, int lvl ) Вот аналогично и выводи.

Только сделай условие, чтобы cout<<
вызывался только если lvl==n
0
eddilou
3 / 3 / 0
Регистрация: 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
Привет! Вот еще темы с ответами:

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

Бинарное дерево поиска - C++
Помогите пожалуйста.. Нужна программа &quot;бинарные деревья поиска&quot;.. и если можно объяснение.. спасибо заранее...

Бинарное дерево поиска - C++
Дали такую задачу: Дан набор попарно не равных целых чисел, по ним строится бинарное дерево поиска. Нужно осуществить обход дерева и...

Бинарное дерево поиска - C++
Давайте рассмотрим некоторый пример Допустим есть числа от 0 до 99 которые добавляются в бинарное дерево Элементы в бинарное дерево...


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

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

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