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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 5.00
каддафи
4 / 4 / 1
Регистрация: 02.10.2012
Сообщений: 127
#1

Поиск листьев в дереве - C++

22.04.2014, 14:51. Просмотров 1444. Ответов 27
Метки нет (Все метки)

Подскажите пожалуйста. Хочу изменить функцию вывода элементов дерева, так чтобы выводились те элементы которые не имееют детей. Не пойму как сюда вставить условие, на проверку пустого значения элементов.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Tree::PrintTreeVn(TreeNode *t, int level)  
{
     
    if (t!=NULL)
    {
        PrintTree(t->right, level+1);
       
        IndentBlanks(6*level);
        cout << t->data << endl;
        PrintTree(t->left, level+1);
        
        
    }
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.04.2014, 14:51
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Поиск листьев в дереве (C++):

Ошибка в считывание листьев в дереве - C++
Написал программу для считывания листьев в дереве, но в строке 56 ошибка: invalid conversion from 'Tree' to 'int' #include &lt;iostream&gt; ...

Количество листьев в бинарном дереве - C++
Задача: Найти количество листьев в дереве. Собственно ввод и вывод дерева есть: #include &lt;iostream.h&gt; #include &lt;iomanip.h&gt; ...

Найти сумму листьев в бинарном дереве поиска - C++
Дано бинарное дерево поиска(ключи-целые числа).Найти сумму листьев. Вот мой код.Но он не работает.Скажите почему и исправьте.Спасибо ...

Как в бинарном дереве у всех листьев вычесть введенное число? - C++
вот кусок int main(void) { /* Первоначально дерево пусто*/ sNode *root = NULL; int s, n; cout&lt;&lt;&quot;Vvedite kolichestvo...

Поиск в Бинарном Дереве! - C++
Задано бинарное дерево. Определить, есть ли в этом дереве хотя бы два одинаковых элемента. Вывести на экран все одинаковые элементы в...

Поиск в двоичном дереве - C++
Добрый день. Нужно построить англо-русский словарь как двоичное дерево. Каждая компонента содержит английское слово, соответствующее ему...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
zss
Модератор
Эксперт С++
6382 / 5947 / 1927
Регистрация: 18.12.2011
Сообщений: 15,264
Завершенные тесты: 1
22.04.2014, 16:50 #2
Только те, которые не имеют детей:
C++
1
if (t!=NULL &&  (t.right()==NULL && t.left()==NULL))
1
каддафи
4 / 4 / 1
Регистрация: 02.10.2012
Сообщений: 127
23.04.2014, 12:54  [ТС] #3
Это мое условие
C++
1
 if (t!=NULL)
заменить на ваше?

Добавлено через 16 часов 22 минуты
не работает ваш вариант, ошибка компиляции на t.right. Если делаю t ->right компилируется, но не работает как надо.
0
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 1
23.04.2014, 13:06 #4
каддафи, его вариант работать не будет. Даже не пытайся. Неужели не видишь, что у него отсутствует рекурсивный вызов функции для потомков узла?

Добавлено через 32 секунды
замени
if (t!=NULL && (t.right()==NULL && t.left()==NULL))
на
if (t!=NULL)

Добавлено через 1 минуту
C++
1
2
3
4
5
6
7
8
9
10
11
void Tree::PrintTreeVn(TreeNode *t, int level)  
{     
    if (t!=NULL)
    {
        PrintTree(t->right, level+1);
       
        IndentBlanks(6*level);
        if (t.right()==NULL && t.left()==NULL) cout << t->data << endl;
        PrintTree(t->left, level+1);        
    }
}
0
каддафи
4 / 4 / 1
Регистрация: 02.10.2012
Сообщений: 127
23.04.2014, 13:17  [ТС] #5
Не компилируется так. Ошибка `right' is not a type .

Добавлено через 4 минуты
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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
#include <iostream>
using namespace std;
 
//////////////////////////////////////////////////////////////
class TreeNode
{
public:
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int item, TreeNode *l = NULL, TreeNode *r = NULL);
};
 
TreeNode::TreeNode(int item, TreeNode *l, TreeNode *r)
{
    data = item;
    left = l;
    right = r;
}
//////////////////////////////////////////////////////////////
 
class Tree
{
public:
    Tree();
    ~Tree(void);
    TreeNode *FindNode(int, TreeNode *&);
    void Insert(int);
    void Delete(int);
    void DeleteTree(TreeNode *);
    void PrintTree(TreeNode *, int);
    void PrintTreeVn(TreeNode *, int);
    void Inorder(TreeNode *);
    TreeNode* GetTreeNode(int item, TreeNode *l = NULL, TreeNode *r = NULL);
    void FreeTreeNode(TreeNode *p);
    
    int size;
    TreeNode *root;
    TreeNode *current;
};
 
 
Tree::Tree()
{
    root = NULL;
    size = 0;
}
 
 
Tree::~Tree()
{
    DeleteTree(root);
}
 
TreeNode* Tree::GetTreeNode(int item, TreeNode *l, TreeNode *r)
{
    TreeNode *p;
    p = new TreeNode(item, l, r);
    return p;
}
 
 
void Tree::FreeTreeNode(TreeNode *p)
{
    delete p;
}
 
void Tree::DeleteTree(TreeNode *t)
{
    if (t!=NULL)
    {
        DeleteTree(t->left);
        DeleteTree(t->right);
        FreeTreeNode(t);
    }       
}
 
 
void IndentBlanks(int num)
{
    for(int i=0; i<num; i++)
       cout << " ";
}    
 
 
void Tree::PrintTree(TreeNode *t, int level)
{
    if (t!=NULL)
    {
        PrintTree(t->right, level+1);
        IndentBlanks(6*level);
        
        cout << t->data << endl;
        
        PrintTree(t->left, level+1);
        
    }
}     
//////////////////////////////////////////////// Poisk i vivod listjev
void Tree::PrintTreeVn(TreeNode *t, int level)  
{
     
   if (t!=NULL )
  
    {
         
        PrintTree(t->right, level+1);
        IndentBlanks(6*level);
     cout << t->data ;
        PrintTree(t->left, level+1);
        
        
    }
}     
/////////////////////////////////////////////////////////////
void Tree::Inorder(TreeNode *t)
{
    if (t!=NULL)
    {
        Inorder(t->left);
        cout << t->data << " ";
        Inorder(t->right);
    }
}    
 
 
TreeNode* Tree::FindNode(int item, TreeNode *&parent)
{
    TreeNode *t = root;
    parent = NULL;
    while(t!=NULL)
    {
        if (item == t->data)
            break;
        else
        {
            parent = t;
            if (item < t->data)
                t = t->left;
            else
                t = t->right;
        }
    }
    return t;
}              
 
 
void Tree::Insert(int item)
{
    TreeNode *t = root, *parent = NULL, *newNode;
    newNode = GetTreeNode(item, NULL, NULL);
    
    while(t!=NULL)
    {
        parent = t;
        if (item < t->data)
            t = t->left;
        else
            t = t->right;
    }
    
    if (parent == NULL)
        root = newNode;
    else if (item < parent->data)
        parent->left = newNode;
    else
        parent->right = newNode;
        
    current = newNode;
    size++;
}    
   
        
void Tree::Delete(int item)
{
    TreeNode *DNodePtr; //raditajs uz dzesamo mezglu
    TreeNode *PNodePtr; //raditajs uz dzesama mezgla prieksteci
    TreeNode *RNodePtr; //raditajs uz mezglu kas aizvieto dzeesamo
 
    //mekleejam elementu kas jaadzees, un taa prieksteci
    if((DNodePtr = FindNode(item, PNodePtr)) == NULL) 
        return;
 
    //ja viens peectecis
    if(DNodePtr->right == NULL)
        RNodePtr = DNodePtr->left;
    else if(DNodePtr->left == NULL)
        RNodePtr = DNodePtr->right;
        
    //ja divi peecteci    
    else
    {
        TreeNode *PofRNodePtr = DNodePtr; //raditajs uz RNodePtr prieksteci
        RNodePtr = DNodePtr->left; //izveelamies kreisa zara 1. elementu, jo tas kas aizvieto ir mazaak par dzeesamo
        
        while(RNodePtr->right != NULL) //kreisaa pusee ejam liidz galam pa labi, saglabajot RNodePtr un PofRNodePtr vertiibas
        {
            PofRNodePtr = RNodePtr;
            RNodePtr = RNodePtr->right;
        }
 
        if(PofRNodePtr == DNodePtr) //kreisaa pusee 1. elementam nav peectecu labaa pusee (Situaacija C1)
        {
            RNodePtr->right = DNodePtr->right; //pievienojam dzeesama elementa labo apakskoku sim elementam
        }
        else //kreisaa pusee 1. elementam ir peecteci labaa pusee (Situaacija C2)
        //atrasto elementu jaanem araa, jaasavieno iznemta elementa zaru ar pamatkoku
        {
            RNodePtr->right = DNodePtr->right;
            PofRNodePtr->right = NULL;
            RNodePtr->left = DNodePtr->left;
        }
    }
 
    if(PNodePtr == NULL)
    {
        RNodePtr->left = root->left;
        RNodePtr->right = root->right;
        root = RNodePtr;
    }    
    //jaapievieno RNodePtr mezglu pie PNodePtr mezgla no pareizaas puses
    else if(DNodePtr->data < PNodePtr->data)
        PNodePtr->left = RNodePtr;
    else
        PNodePtr->right = RNodePtr;
 
    FreeTreeNode(DNodePtr); //dzeesam elementu
    size--;
}     
//////////////////////////////////////////////////////////////
 
 
 
 
int main()
{
  Tree tree;
  tree.Insert(5);
  tree.Insert(7);
  tree.Insert(2);
  tree.Insert(8);
  tree.Insert(15);
  tree.Insert(3);
  tree.Insert(1);
  tree.Insert(4);
  tree.Insert(7);
  
  
 tree.Inorder(tree.root);
  cout << endl << endl;
  
  tree.PrintTree(tree.root, 0);
  cout<< "************Vivod vneshnih vershin*****************"<<endl;
  tree.PrintTreeVn(tree.root,0);
  
 // tree.Delete(50);
 // cout << endl << endl;
 // tree.PrintTree(tree.root, 0);
  
  system("PAUSE");  
  return 0;
}
0
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 1
23.04.2014, 13:17 #6
а нафига ты скобки после right поставил? Их не было изначально!!!
0
каддафи
4 / 4 / 1
Регистрация: 02.10.2012
Сообщений: 127
23.04.2014, 13:24  [ТС] #7
я не ставил. Это указатели. ZSS мне предложил их поставить, но там ошибка компиляции. Вы тоже предложили свой вариант со скобками.
0
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 1
23.04.2014, 13:28 #8
Цитата Сообщение от каддафи Посмотреть сообщение
Вы тоже предложили свой вариант со скобками.
я исправил условие в варианте zss не я эти скобки поставил, не гоните на меня
0
каддафи
4 / 4 / 1
Регистрация: 02.10.2012
Сообщений: 127
23.04.2014, 13:33  [ТС] #9
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Код C++
1
2
3
4
5
6
7
8
9
10
11
void Tree::PrintTreeVn(TreeNode *t, int level) *
{ * *
* * if (t!=NULL)
* * {
* * * * PrintTree(t->right, level+1);
IndentBlanks(6*level);
* * * * if (t.right()==NULL && t.left()==NULL) cout << t->data << endl;
* * * * PrintTree(t->left, level+1); * * * *
* * }
}
Вот цитирую ваш вариант, там тоже со скобками. Да и фиг с этими скобками. Вернулись все равно к первому сообщению.
0
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 1
23.04.2014, 13:43 #10
я взял твой вариант
Цитата Сообщение от каддафи Посмотреть сообщение
void Tree::PrintTreeVn(TreeNode *t, int level) {
if (t!=NULL) {
PrintTree(t->right, level+1);
IndentBlanks(6*level);
cout << t->data << endl;
PrintTree(t->left, level+1);
}
}
Затем взял условие zss со скобками
Цитата Сообщение от zss Посмотреть сообщение
if (t!=NULL && (t.right()==NULL && t.left()==NULL))
И дал на их основе верный ответ, просто скопировав строчку zss в нужное место!
Никаких скобок я не добавлял! Я ГОВОРЮ НЕ БЫЛО!!! ПОЧЕМУ ВЫ МНЕ НЕ ВЕРИТЕ! ПОЧЕМУ ВЫ НЕ ОТВЕЧАЕТЕ НА МОЙ ОТВЕТ КОНКРЕТНООО!!!
0
каддафи
4 / 4 / 1
Регистрация: 02.10.2012
Сообщений: 127
23.04.2014, 13:57  [ТС] #11
Я отвечаю, но не знаю почему не отвечается. Нажимаю на эту кнопку.
[]http://i6.pixs.ru/storage/7/9/9/putjpg_8858428_11813799.jpg[/]
В вашем варианте t.right() тоже скобки. Это не работает, не компилируется.
0
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 1
23.04.2014, 14:02 #12
ну так убери скобки!
0
каддафи
4 / 4 / 1
Регистрация: 02.10.2012
Сообщений: 127
23.04.2014, 14:12  [ТС] #13
Kuzia domovenok,
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void Tree::PrintTreeVn(TreeNode *t, int level)  
{
     
   if (t!=NULL )
  
    {
         
        PrintTree(t->right, level+1);
    
        IndentBlanks(6*level);
        
      if (t.right==NULL && t.left==NULL) cout << t->data;
    
        PrintTree(t->left, level+1);
        
        
    }
}
Так? Ошибка компиляции.
0
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 1
23.04.2014, 14:17 #14
Цитата Сообщение от каддафи Посмотреть сообщение
if (t.right==NULL && t.left==NULL) cout << t->data;
а почему ты оператор "точка" применяешь к указателям??? Ты хоть текст ошибки читаешь? Там наверняка об этом сказано! Или же ты просто действуешь как "программа не работает - иду на форум"???
C++
1
if (t->right==NULL && t->left==NULL) cout << t->data;
0
каддафи
4 / 4 / 1
Регистрация: 02.10.2012
Сообщений: 127
23.04.2014, 14:19  [ТС] #15
Kuzia domovenok, Я об этом уже писал, что это указатели. И не знаю почему мне zss со скобками сказал писать. Я пробовал и со стрелками. Все равно Результат такой же. Выводится все дерево, только без корня.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.04.2014, 14:19
Привет! Вот еще темы с ответами:

Поиск в красно-черном дереве - C++
Доброе утро! Изучая, Стандарт выполняю задание - создайте шаблон ассоциативного контейнера. В общем он будет предельно прост, лишь с...

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

Поиск дубликатов в бинарном дереве - C++
Требуется создать функцию поиска дубликатов ИНФОРМАЦИОННОЙ ЧАСТИ, НЕ КЛЮЧА в бинарном дереве. Ничего похожего в гугле и здесь на...

Поиск одинаковых элементов в бинарном дереве - C++
Нужно вывести на экран все повторяющиеся элементы в бинарном дереве. # include &lt;iostream&gt; # include &lt;conio.h&gt; using namespace...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
23.04.2014, 14:19
Ответ Создать тему
Опции темы

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