C++

Forum

 
Binary Tree

CodeNovice01 (278)
The code isn't reading in my numbers from the infile. It reads two and stops. Can someone help me figure out whats going wrong??
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
 
  #include <iostream>
#include <fstream>
#include <iomanip>

using namespace std;

//Structure
struct TreeNode
{
    TreeNode *LeftChild;
    TreeNode *RightChild;
    int data;
};

//Global Variables
ofstream out("BinaryTree.out");
TreeNode *Root = nullptr;

//Prototypes
void Insert(int);
void Read();
void InOrder(TreeNode* current = Root);
void PreOrder(TreeNode*);
void PostOrder(TreeNode*);
int NodeCount(TreeNode*);
int Sum(TreeNode*);
double Average(TreeNode*);
void LeafCount(int&, TreeNode*);
void Deepest(int&,TreeNode*,int,int);
void NodeWithOneChild(int&,TreeNode*);
void Delete(TreeNode*,TreeNode*);
int DigitSum(int);
TreeNode *MinNode(TreeNode*);
void SearchNode(int,TreeNode*&,TreeNode*);

void Insert(int value)
{
    if(!Root)
    {
        Root = new TreeNode;
        Root->data = value;
        Root->RightChild = nullptr;
        Root->LeftChild = nullptr;
    }
    else
    {
        TreeNode *current = Root,
                 *previous = nullptr,
                 *temp = nullptr;
        for(;current;)
        {
            previous = current;
            if (value < current->data)
                current = current->RightChild;
            else
                current = current->LeftChild;
        }
        temp = new TreeNode;
        temp->data = value;
        temp->LeftChild = nullptr;
        temp->RightChild = nullptr;

        if(value < previous->data)
            previous->LeftChild = temp;
        else
            previous->RightChild = temp;
    }
}

void Read()
{
    ifstream inf("TreeRandNbrs.dat");
    if(!inf)
        cout << "Error Opening File";
    int num;
    while(inf>>num)
        Insert(num);
    inf.close();
}

void InOrder(TreeNode* current)
{
    if(!current)
        return;
    InOrder(current->LeftChild);
    out << current->data << " ";
    InOrder(current->RightChild);
}

void PreOrder(TreeNode* current)
{
    current = Root;
    if(!current)
        return;
    out << current ->data << " ";
    PreOrder(current ->LeftChild);
    PreOrder(current ->RightChild);
}

void PostOrder(TreeNode* current)
{
    current = Root;
    if(!current)
        return;
    PostOrder(current->LeftChild);
    PostOrder(current->RightChild);
    out << current->data << " ";
}

int NodeCount(TreeNode* current)
{
    current = Root;
    if(!current)
        return 0;
    return NodeCount(current->LeftChild) + NodeCount(current->RightChild) +1;
}

int Sum(TreeNode* current)
{
    current = Root;
    if(!current)
        return 0;
    return current->data + Sum(current->LeftChild) + Sum(current->RightChild);
}

double Average(TreeNode* current)
{
    current = Root;
    return (double)Sum(current)/NodeCount(current);
}

void LeafCount(int& leafs, TreeNode* current)
{
    current = Root;
    if(!current)
        return;
    if(!current->LeftChild && !current->RightChild)
        leafs++;
    LeafCount(leafs,current->LeftChild);
    LeafCount(leafs,current->RightChild);
}

void Deepest(int& deep, TreeNode* current, int lvl, int maxlvl)
{
    current = Root;
    lvl=0, maxlvl=0;
    if(!current)
        return;
    if(lvl > maxlvl)
    {
        deep = current->data;
        maxlvl = lvl;
    }
    Deepest(deep,current->LeftChild,lvl+1,maxlvl);
    Deepest(deep,current->LeftChild,lvl,maxlvl);
}

void NodeWithOneChild(int& cnt, TreeNode* current)
{
    current = Root;
    if(!current)
        return;
    if((current->LeftChild && !current->RightChild) || (!current->LeftChild && current->RightChild))
        cnt++;
    NodeWithOneChild(cnt, current->LeftChild);
    NodeWithOneChild(cnt, current->RightChild);
}

void Delete(TreeNode* current, TreeNode* previous)
{
    current = Root;
    previous = nullptr;
    if(!current)
        return;
    Delete(current->LeftChild,current);
    Delete(current->RightChild,current);
    if(DigitSum(current->data)<9)
    {
        if(!current->LeftChild && !current->RightChild)
        {
            if(current != Root)
            {
                if(previous->LeftChild == current)
                    previous->LeftChild = nullptr;
                else
                    previous->RightChild = nullptr;
            }
            else
                Root = nullptr;
            delete current;
        }
        if ((!current->LeftChild && current->RightChild) || (current->LeftChild && !current->RightChild))
        {
            TreeNode* child;
            if(current->LeftChild)
                child = current->LeftChild;
            else
                child = current->RightChild;
            if(current != Root)
            {
                if (current == previous->LeftChild)
                    previous->LeftChild = child;
                else
                    previous->RightChild = child;
            }
            else
                Root = child;
            delete current;
        }
        if(current->LeftChild && current->RightChild)
        {
            TreeNode* Next = MinNode(current->RightChild);
            Delete(current->LeftChild,current);
            current->data = Next->data;
        }
    }
}

int DigitSum(int value)
{
    if(value<10)
        return value;
    return(value%10) + DigitSum(value/10);
}

TreeNode* MinNode(TreeNode* current)
{
    if(!current->LeftChild)
        return current;
    return MinNode(current->LeftChild);
}

void SearchNode(int num, TreeNode*& goal, TreeNode* current)
{
    current = Root;
    if(!current)
        return;
    if(current->data == num)
        goal = current;
    SearchNode(num,goal,current->LeftChild);
    SearchNode(num,goal,current->RightChild);

}
int main()
{
    Read();
    out << fixed << setprecision(2) << "InOrder: \n";
    InOrder();
    return 0;

}

Data File
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
 
141
117
134
500
369
524
328
208
512
264
405
345
431
277
161
395
342
427
136
541
304
402
253
392
332
421
366
468
195
147
226
471
388
169
212
299
485
544
453
511
372
283
223
391
218
447
294
362
457
337
359
273
179
428
266
435
240
142
506
140
492
464
248
546
505
529
170
150
256
151
193
498
379
123
334
254
406
116
276
531
308
394
139
426
173
237
488
382
441
433
165
239
508
130
127
156
436
171
495
474
272
520
327
373
247
412
236
340
261
286
355
374
452
450
350
224
380
157
107
187
257
403
133
459
408
238
222
296
530
313
100
291
410
159
274
387
245
102
491
336
320
196
271
448
349
418
284
281
153
138


kbw (9488)
You need to swap lines 54 and 56, the comparison is the wrong way around.

That aside, it's not obvious that the Build/Insert is broken without actually running it. Have you tried running it in a debugger? Surely every must have access to one by now.
CodeNovice01 (278)
kbw, i'm not familiar with a debugger. I use codeblocks.

Thank you for finding that bug. It works properly now.

I do have one other request. How would I make the output print 10 numbers per line? I've tried using
1
2
 
if(current->data % 10 == 0)
out << endl;

inside the Inorder function. I assume I will need one of the mod statements in each order function.
dutch (2548)
Try something like this:

1
2
3
4
5
6
7
8
9
10
 
void InOrder(TreeNode* current, int cnt = 1)
{
    if(!current)
        return;
    InOrder(current->LeftChild, cnt);
    out << current->data << ' ';
    if(cnt % 10 == 0)
        out << '\n';
    InOrder(current->RightChild, cnt + 1);
}

CodeNovice01 (278)
Thank you Dutch, I will try this as soon as I get home from work later this evening.

Last edited on
CodeNovice01 (278)
I'm not sure what is wrong with my delete function. It deletes a few numbers but not all that it's suppose.
I also changed it up from the OP, I thought this would be simplier.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
TreeNode* Delete(TreeNode* current)
{
    if(current == nullptr)
            return nullptr;
    if(current->LeftChild == nullptr && current->RightChild == nullptr)
    {
        if(DigitSum(current->data)<9)
        {
            delete(current);
            return nullptr;
        }
    }

    current->LeftChild = Delete(current->LeftChild);
    current->RightChild= Delete(current->RightChild);

    return current;
}
CodeNovice01 (278)
Dutch, I tried what you sugguested in two different ways, first as you proposed and then I just took count out of the parameters and just into the function itself. But it never endl, all the numbers are all on one line.
dutch (2548)
Try this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
const int ElementsPerLine = 10;

void InOrder_impl( TreeNode* current, int& cnt )
{
    if( !current ) return;
    InOrder_impl(current->LeftChild, cnt );
    std::cout << current->data << ' ';
    if( ++cnt % ElementsPerLine == 0 ) std::cout << '\n';
    InOrder_impl( current->RightChild, cnt );
}

void InOrder( TreeNode* current )
{
    int cnt = 0;
    InOrder_impl( current, cnt );
    if( cnt % ElementsPerLine != 0 ) std::cout << '\n';
}

Last edited on
CodeNovice01 (278)
I'm not sure if this is working on your end. But I'm having no luck. Lets scrap this idea. It was just something i wanted to add for my printing so it wouldn't run across the page.

What about the delete function, what am I doing wrong? A friend suggested i delete line 5 along with the associated braces and they said that worked on their end, but I get an error.
CodeNovice01 (278)
I was playing around with the debugger. Added a breakpoint to the inorder function. I replaced the counter into the recursive function call for the rightchild, with cnt+1, like Dutch had originally suggested.

The debug/watch window will run through the function and bump count once it reaches the last line in the function. But sometimes the count will decrement or not even reach 10 and will start a new line.
dutch (2548)
I'm not sure if this is working on your end. But I'm having no luck.

The first one was off the top of my head and was totally wrong.

The second one is obviously correct if you understand what it's doing.
You'd have to post your actual code for me to see what you're doing wrong.
CodeNovice01 (278)
Here's the full code. It also produces a stack overflow error when it returns. I know its something wrong with the delete, but it should still run either way.

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>
#include <fstream>
#include <iomanip>

using namespace std;

//Structure
struct TreeNode
{
    TreeNode *LeftChild;
    TreeNode *RightChild;
    int data;
};

//Global Variables
ofstream out("BinaryTree.out");
TreeNode *Root = nullptr;

//Prototypes
void Insert(int);
void Read();
void InOrder(TreeNode* current = Root, int cnt=0);
void PreOrder(TreeNode* current = Root);
void PostOrder(TreeNode* current = Root);
int NodeCount(TreeNode* current = Root);
int Sum(TreeNode* current = Root);
double Average(TreeNode* current = Root);
void LeafCount(int&, TreeNode* current = Root);
void Deepest(int&,TreeNode* current = Root,int lvl=0,int maxlvl=0);
void NodeWithOneChild(int&,TreeNode* current = Root);
TreeNode* Delete(TreeNode* current = Root);
int DigitSum(int);
TreeNode* MinNode(TreeNode*);
void SearchNode(int, TreeNode*&, TreeNode* current = Root);

void Insert(int value)
{
    if(!Root)
    {
        Root = new TreeNode;
        Root->data = value;
        Root->RightChild = nullptr;
        Root->LeftChild = nullptr;
    }
    else
    {
        TreeNode *current = Root,
                 *previous = nullptr,
                 *temp = nullptr;
        while(current)
        {
            previous = current;
            if (value < current->data)
                current = current->LeftChild;
            else
                current = current->RightChild;
        }
        temp = new TreeNode;
        temp->data = value;
        temp->LeftChild = nullptr;
        temp->RightChild = nullptr;

        if(value < previous->data)
            previous->LeftChild = temp;
        else
            previous->RightChild = temp;
    }
}

void Read()
{
    ifstream inf("TreeRandNbrs.dat");
    if(!inf)
        cout << "Error Opening File";

    int num;
    while(inf>>num)
        Insert(num);


    inf.close();
}

void InOrder(TreeNode* current, int cnt)
{
    if(current==nullptr)
        return;

    InOrder(current->LeftChild,cnt);
    cout << current->data << " ";
    if(++cnt%10==0)
        cout<<endl;
    InOrder(current->RightChild,cnt);
}

void test(TreeNode* current)
{
    int cnt=0;
    InOrder(current, cnt);
    if(cnt%10!=0)
        cout << endl;
}

void PreOrder(TreeNode* current)
{
    if(!current)
        return;

    cout << current ->data << " ";
    PreOrder(current ->LeftChild);
    PreOrder(current ->RightChild);
    if(current->data%10==0)
        cout<<endl;
}

void PostOrder(TreeNode* current)
{
    if(!current)
        return;
    PostOrder(current->LeftChild);
    PostOrder(current->RightChild);
    cout << current->data << " ";
    if(current->data%10==0)
        cout<<endl;
}

int NodeCount(TreeNode* current)
{
    if(!current)
        return 0;
    return NodeCount(current->LeftChild) + NodeCount(current->RightChild) +1;
}

int Sum(TreeNode* current)
{
    if(!current)
        return 0;
    return current->data + Sum(current->LeftChild) + Sum(current->RightChild);
}

double Average(TreeNode* current)
{
    return (double)Sum(current)/NodeCount(current);
}

void LeafCount(int& leafs, TreeNode* current)
{
    if(!current)
        return;
    if(!current->LeftChild && !current->RightChild)
        leafs++;
    LeafCount(leafs,current->LeftChild);
    LeafCount(leafs,current->RightChild);
}

void Deepest(int& deep, TreeNode* current, int lvl, int maxlvl)
{
    if(!current)
        return;
    if(lvl > maxlvl)
    {
        deep = current->data;
        maxlvl = lvl;
    }
    Deepest(deep,current->LeftChild,lvl++,maxlvl);
    Deepest(deep,current->LeftChild,lvl,maxlvl);
}

void NodeWithOneChild(int& cnt, TreeNode* current)
{
    if(!current)
        return;
    if((current->LeftChild && !current->RightChild) || (!current->LeftChild && current->RightChild))
        cnt++;
    NodeWithOneChild(cnt, current->LeftChild);
    NodeWithOneChild(cnt, current->RightChild);
}

TreeNode* Delete(TreeNode* current)
{
    if(current == nullptr)
            return nullptr;

        if(DigitSum(current->data)<9)
        {
            delete(current);
            return nullptr;
        }
    current->LeftChild = Delete(current->LeftChild);
    current->RightChild= Delete(current->RightChild);

    return current;
}

int DigitSum(int value)
{
    if(value==0)
        return 0;
    return(value%10 + DigitSum(value/10));
}

void SearchNode(int num, TreeNode*& goal, TreeNode* current)
{
    if(!current)
        return;
    if(current->data == num)
        goal = current;
    SearchNode(num,goal,current->LeftChild);
    SearchNode(num,goal,current->RightChild);

}
int main()
{
    Read();

    cout << "INORDER: \n";
    InOrder();

    cout << "\nPREORDER: \n";
    PreOrder();

    cout << "\nPOSTORDER: \n";
    PostOrder();

    cout << "\n\nNumber of Nodes: " << NodeCount()
        << "\nSum of Infile: " << Sum()
        << "\nAverage of Infile: " << Average();

    int leafs=0;
    LeafCount(leafs);
    cout << "\nNumber of Leafs: " << leafs;

    int deep=0;
    Deepest(deep);
    cout << "\nDeepest Node: " << deep;

    int child=0;
    NodeWithOneChild(child);
    cout << "\nNodes with ONE Child: " << child;

    TreeNode* Goal = Root;
    cout << "\nSubtree of Node 313 INORDER: ";
    SearchNode(313, Goal);
    InOrder(Goal);

    TreeNode* Goal2 = Root;
    cout << "Subtree of Node 286 POSTORDER: ";
    SearchNode(286, Goal2);
    PostOrder(Goal2);

    cout << "\nNodes to the LEFT: "
        << NodeCount(Root->LeftChild)
        << "\nNodes to the RIGHT: "
        << NodeCount(Root->RightChild);

    Delete();

    cout << "\nINORDER after Delete: \n";
    InOrder();

    out.close();
    return 0;


Process returned -1073741571 (0xC00000FD)
Last edited on
dutch (2548)
Well, right away for the printing:

 
 
void InOrder(TreeNode* current, int cnt)

That doesn't match my code. cnt should be a reference. That way it retains it's value independently of the stack frame (it exists on the wrapper's stack frame).

I'll look at the delete problem....
CodeNovice01 (278)
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
263
264
 
#include <iostream>
#include <fstream>
#include <iomanip>

using namespace std;

//Structure
struct TreeNode
{
    TreeNode *LeftChild;
    TreeNode *RightChild;
    int data;
};

//Global Variables
ofstream out("BinaryTree.out");
TreeNode *Root = nullptr;

//Prototypes
void Insert(int);
void Read();
void InOrder(int&,TreeNode* current = Root);
void PreOrder(TreeNode* current = Root);
void PostOrder(TreeNode* current = Root);
int NodeCount(TreeNode* current = Root);
int Sum(TreeNode* current = Root);
double Average(TreeNode* current = Root);
void LeafCount(int&, TreeNode* current = Root);
void Deepest(int&,TreeNode* current = Root,int lvl=0,int maxlvl=0);
void NodeWithOneChild(int&,TreeNode* current = Root);
TreeNode* Delete(TreeNode* current = Root);
int DigitSum(int);
TreeNode* MinNode(TreeNode*);
void SearchNode(int, TreeNode*&, TreeNode* current = Root);

void Insert(int value)
{
    if(!Root)
    {
        Root = new TreeNode;
        Root->data = value;
        Root->RightChild = nullptr;
        Root->LeftChild = nullptr;
    }
    else
    {
        TreeNode *current = Root,
                 *previous = nullptr,
                 *temp = nullptr;
        while(current)
        {
            previous = current;
            if (value < current->data)
                current = current->LeftChild;
            else
                current = current->RightChild;
        }
        temp = new TreeNode;
        temp->data = value;
        temp->LeftChild = nullptr;
        temp->RightChild = nullptr;

        if(value < previous->data)
            previous->LeftChild = temp;
        else
            previous->RightChild = temp;
    }
}

void Read()
{
    ifstream inf("TreeRandNbrs.dat");
    if(!inf)
        cout << "Error Opening File";

    int num;
    while(inf>>num)
        Insert(num);


    inf.close();
}

void InOrder( int& cnt,TreeNode* current)
{
    if(current==nullptr)
        return;

    InOrder(cnt,current->LeftChild);
    cout << current->data << " ";
    if(++cnt%10==0)
        cout<<endl;
    InOrder(cnt,current->RightChild);
}

void test(TreeNode* current)
{
    int cnt=0;
    InOrder(cnt,current);
    if(cnt%10!=0)
        cout << endl;
}

void PreOrder(TreeNode* current)
{
    if(!current)
        return;

    cout << current ->data << " ";
    PreOrder(current ->LeftChild);
    PreOrder(current ->RightChild);
    if(current->data%10==0)
        cout<<endl;
}

void PostOrder(TreeNode* current)
{
    if(!current)
        return;
    PostOrder(current->LeftChild);
    PostOrder(current->RightChild);
    cout << current->data << " ";
    if(current->data%10==0)
        cout<<endl;
}

int NodeCount(TreeNode* current)
{
    if(!current)
        return 0;
    return NodeCount(current->LeftChild) + NodeCount(current->RightChild) +1;
}

int Sum(TreeNode* current)
{
    if(!current)
        return 0;
    return current->data + Sum(current->LeftChild) + Sum(current->RightChild);
}

double Average(TreeNode* current)
{
    return (double)Sum(current)/NodeCount(current);
}

void LeafCount(int& leafs, TreeNode* current)
{
    if(!current)
        return;
    if(!current->LeftChild && !current->RightChild)
        leafs++;
    LeafCount(leafs,current->LeftChild);
    LeafCount(leafs,current->RightChild);
}

void Deepest(int& deep, TreeNode* current, int lvl, int maxlvl)
{
    if(!current)
        return;
    if(lvl > maxlvl)
    {
        deep = current->data;
        maxlvl = lvl;
    }
    Deepest(deep,current->LeftChild,lvl++,maxlvl);
    Deepest(deep,current->LeftChild,lvl,maxlvl);
}

void NodeWithOneChild(int& cnt, TreeNode* current)
{
    if(!current)
        return;
    if((current->LeftChild && !current->RightChild) || (!current->LeftChild && current->RightChild))
        cnt++;
    NodeWithOneChild(cnt, current->LeftChild);
    NodeWithOneChild(cnt, current->RightChild);
}

TreeNode* Delete(TreeNode* current)
{
    if(!current)
        return NULL;
  //  if(current->LeftChild == nullptr && current->RightChild == nullptr)
    if(DigitSum(current->data)<9)
    {
        delete(current);
        return nullptr;
    }
    current->LeftChild = Delete(current->LeftChild);
    current->RightChild= Delete(current->RightChild);

    return current;
}

int DigitSum(int value)
{
    if(value==0)
        return 0;
    return(value%10 + DigitSum(value/10));
}

void SearchNode(int num, TreeNode*& goal, TreeNode* current)
{
    if(!current)
        return;
    if(current->data == num)
        goal = current;
    SearchNode(num,goal,current->LeftChild);
    SearchNode(num,goal,current->RightChild);

}
int main()
{
    Read();
int cnt;
    cout << "INORDER: \n";
    InOrder(cnt);

    cout << "\nPREORDER: \n";
    PreOrder();

    cout << "\nPOSTORDER: \n";
    PostOrder();

    cout << "\n\nNumber of Nodes: " << NodeCount()
        << "\nSum of Infile: " << Sum()
        << "\nAverage of Infile: " << Average();

    int leafs=0;
    LeafCount(leafs);
    cout << "\nNumber of Leafs: " << leafs;

    int deep=0;
    Deepest(deep);
    cout << "\nDeepest Node: " << deep;

    int child=0;
    NodeWithOneChild(child);
    cout << "\nNodes with ONE Child: " << child;

    TreeNode* Goal = Root;
    cout << "\nSubtree of Node 313 INORDER: ";
    SearchNode(313, Goal);
    InOrder(cnt,Goal);

    TreeNode* Goal2 = Root;
    cout << "Subtree of Node 286 POSTORDER: ";
    SearchNode(286, Goal2);
    PostOrder(Goal2);

    cout << "\nNodes to the LEFT: "
        << NodeCount(Root->LeftChild)
        << "\nNodes to the RIGHT: "
        << NodeCount(Root->RightChild);

    Delete();

    cout << "\nINORDER after Delete: \n";
    InOrder(cnt);

    out.close();
    return 0;

}


I've made some major headway with your suggestion. It does print 10 per-line, but after the first line. Here's the Inorder print out.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
INORDER:
100 102 107 116
117 123 127 130 133 134 136 138 139 140
141 142 147 150 151 153 156 157 159 161
165 169 170 171 173 179 187 193 195 196
208 212 218 222 223 224 226 236 237 238
239 240 245 247 248 253 254 256 257 261
264 266 271 272 273 274 276 277 281 283
284 286 291 294 296 299 304 308 313 320
327 328 332 334 336 337 340 342 345 349
350 355 359 362 366 369 372 373 374 379
380 382 387 388 391 392 394 395 402 403
405 406 408 410 412 418 421 426 427 428
431 433 435 436 441 447 448 450 452 453
457 459 464 468 471 474 485 488 491 492
495 498 500 505 506 508 511 512 520 524
529 530 531 541 544 546

I had to swap the parameters around, otherwise it kept giving me an error.
Last edited on
dutch (2548)
So is your delete working now?

As for the first line not printing 10 items, you need to reset cnt to 0 every time you call InOrder. Really, you should use a wrapper function like I did. It's common to use a wrapper to initialize special storage for a recursive function. That way you don't have to declare this otherwise meaningless variable (and remember to initialize it to zero) just to use this function. A wrapper is in order here.
CodeNovice01 (278)
Delete is still unfunctional.

I used the "wrapper" function called "test" in my program. The format stayed the same.
dutch (2548)
The format stayed the same.

If you mean it didn't print correctly, then you did something wrong.

What exactly is the "Delete" function supposed to do?
Is it supposed to remove the only the first node that satisfies the predicate or all such nodes?
CodeNovice01 (278)
The delete is suppose to remove any number with a digit sum less than 9. For example if the number is 123 = 6 so delete it.
dutch (2548)
I assume when you mean "any", you mean all such numbers. Okay.

To think about the problem of deleting an arbitrary node from the middle of a binary tree, consider the following tree. Write it down on paper with lines for pointers and think about how the lines need to be redrawn to remove node number 8.

                4
         2                8
      1     3        6         10
                   5   7     9   11

Last edited on
CodeNovice01 (278)
I've come up with this, with a little help from the internet.
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
 
TreeNode* Delete(TreeNode* current, TreeNode* previous)
{
    if (!current)
		return nullptr;

	//Traverse the Tree
	Delete(current -> LeftChild, current);
	Delete(current -> RightChild, current);

	// Go through and delete nodes on the way out.
	if (DigitSum(current->data) < 9)
	{
		// If node is a leaf.
		if (!current->LeftChild && !current ->RightChild)
		{
			// Setting parent node to NULL.
			if (current != Root)
			{
				if (previous->LeftChild == current)
					previous->LeftChild = nullptr;
				else
					previous->RightChild = nullptr;
			}

			// Setting root to NULL.
			else
				Root = nullptr;
			delete current;
		}

		// If node has just one child.
		if ((!current->LeftChild && current->RightChild) || (current->LeftChild && !current->RightChild))
		{
			// Finding child node.
			TreeNode *child;
			if (current->LeftChild)
				child = current->LeftChild;
			else
				child = current->RightChild;

			// Linking parent node to child node.
			if (current != Root)
			{
				if (current == previous->LeftChild)
					previous->LeftChild = child;
				else
					previous->RightChild = child;
			}

			// Set root to child node.
			else
				Root = child;
			delete current;
		}

		// If node has two children.
		if (current->LeftChild && current->RightChild)
		{
			TreeNode*successor = MinNode(current->RightChild);
			Delete(current->LeftChild, current);
			current->data = successor ->data;
		}
	}
}

TreeNode *MinNode(TreeNode *current)
{
	if (!current->LeftChild)
		return current;
	return MinNode(current->LeftChild);
}


The only issue is that the output has a few duplicates in it. The input file doesn't repeat any numbers.

OUTPUT
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
INORDER after Delete:
117 127 136 136 138 139 147 147 153
156 157 159 165 165 169 171 173 179 187
193 195 196 208 218 226 236 237 238 239
245 245 247 248 253 254 256 257 261 264
266 271 272 273 274 276 277 281 283 284
286 291 294 296 299 308 308 327 328 334
336 337 342 345 349 355 359 362 366 369
372 373 374 379 380 382 387 388 391 392
394 395 405 406 408 418 418 426 426 427
428 433 433 435 436 441 447 448 450 452
453 457 459 464 468 471 474 485 488 491
492 495 498 505 505 506 508 524 529 531
541 544 546


I have two different .cpp files for this code, one was just a test while the other was the original.

My test file runs perfectly with the new delete function added to it. While the original doesn't return 0. But each file has the same exact code. One returns 0(test) and the original returns -1073741571 (0xC00000FD).
Last edited on
Topic archived. No new replies allowed.