C++

Forum

 
Binary Tree Program not acting as it should...

Pages: 12
Merriak (61)
All solved for thanks for the assist! :D
Last edited on
Merriak (61)
Still unable to find the issue. I've sketched it out and everything seems fine. Hmm, unless something is wrong with my post-increment function but I do not think so...
TheIdeasMan (6781)
Have you used the debugger? It is by far the easiest way to find runtime errors.
Merriak (61)
Yeah, problem is the program does compile and run file just not how to should. Is there a way for the debugger to check a program that compiles and runs fine?

I have ruled out that it's not my insert functions that are causing the issue as I added several comments throughout them to see how they're inserting elements and they are in the correct order.

I'm thinking it may actually be my post-increment function in the Set_iterator class that's causing the issue, but I don't know what it could be. It all seems right to me?
Last edited on
Catfish3 (666)
Have you used the debugger?

Have you?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
template <class T>
void Set<T>::insert(const T & newElement)
{
    Node<T> x;
    
    if(root != NULL)
        x.insert(newElement, root);
    else
    {
        root=new Node<T>;
        root->value=newElement;
        root->leftChild=NULL;
        root->rightChild=NULL;
    }
}


Shouldn't the bolded line be something like:

root->insert(newElement, root);

Also, I hope you're aware that in C++, each new must have its corresponding delete.

Maybe your program is correct, but I can't tell. What I see is that you have new operations in your Node class, but no corresponding delete operations.
Last edited on
TheIdeasMan (6781)
Is there a way for the debugger to check a program that compiles and runs fine?


The compiler is not the debugger.

A debugger is a separate program that allows one to check values of variables & step through the code 1 line at a time. You can have breakpoints and set up a watch list of variables. This way you can see where your variables go wrong & deduce the problem.

It should be easy if you have an IDE, a bit more tricky if using a debugger like gdb from the command line. There is an article about how to do that at the top left of this screen. There is also the gdb man page, and a search on Google.

HTH
Merriak (61)
@Catfish
I think that, that line does the same thing either way though yours does look cleaner and don't know why I hadn't thought of it.

On the topic of deletes, I thought the destructor I have written is automatically called when necessary? Or would I have to specify it in the code?

@TIM
I was using gdb, not the compiler itself. Though since the program ran fine gdb was just telling me the program ran normally. Not sure what else I could do with it? I have looked into all the commands, but they all address programs that are mainly crashing it seems.
Catfish3 (666)
Sorry! I completely missed the destructor.

I could try to write a simplified BinaryTree for you, which you can then improve as your own, and transform into a template class.

Otherwise I'll admit I'm useless, because I can't keep up with your code.
TheIdeasMan (6781)
Merriak wrote:
Not sure what else I could do with it? I have looked into all the commands, but they all address programs that are mainly crashing it seems.


TheIdeasMan wrote:
..... that allows one to check values of variables & step through the code 1 line at a time. You can have breakpoints and set up a watch list of variables. This way you can see where your variables go wrong & deduce the problem.




@Catfish

I made my comment because initially it sounded as though the OP wasn't aware of the difference between the two. It seems he does know what the debugger is, but hasn't yet learnt what can be done with it. I'll leave it to you to help him.

Have you used the debugger?

Have you?


Did you mean me, or Merriak?

I think you mean me, - I certainly have used various debuggers over the years. I haven't used gdb a lot, but I have a reasonable idea how it works.

Some of the GUI ones vary quite a bit. The one in KDevelop is a fairly basic GUI to gdb, in that one can type in gdb commands and the results are shown. So that seems almost the same as using gdb from the shell, which is fine.

On QtCreator,it is a lot easier because it shows the values of all your variables as you step through the code. One can drill down into composite variables such as a vector of structs, to see what all the values are. One can do on the fly expressions as well, just like gdb.

HTH
Merriak (61)
I could try to write a simplified BinaryTree for you, which you can then improve as your own, and transform into a template class.


That'd be awesome too! As I am really interested in understanding the concepts more.

I didn't really think anyone could keep up with my own code as it's quite a bit, but thought I would see if anyone could spot anything with a quick glance. Second opinions help a ton.

@TIM
Yeah I haven't really learned how to use a debugger, just have read up on em and trying to teach myself though it is proving difficult. I do want to learn how to more effectively place breakpoints.
Last edited on
ne555 (10692)
You never set the `parent' in the insertion
Merriak (61)
You never set the `parent' in the insertion


Do I need to? o.O
ne555 (10692)
You use it in the `operator++'
Last edited on
Catfish3 (666)
Uhh, if ne555's solution works I'll be chickening out.
Merriak (61)
Hmm either that's not it or I am just trying the wrong method.

Was going with something like:

newNode->parent = this;
ne555 (10692)
Your `Node::insert()' makes no use of the state, you should fix that.
As you've got it now
newNode->rightChild->parent = newNode; if you create a right child
newNode->leftChild->parent = newNode; if you create a left child

Also, ¿why don't just use the constructor?
Merriak (61)
If I try that though, it produces a segmentation fault.

I guess you mean that the newNode->rightChild->leftChild = NULL and others like it are extraneous?
Last edited on
ne555 (10692)
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
 
template <class T>
void Node<T>::insert(int newElement)
{
	if(newElement < value) {
		if(leftChild != NULL)
			leftChild->insert(newElement);
		else
			leftChild = new Node<T>(newElement, this, NULL, NULL);
	}
	else {
		if(rightChild != NULL)
			rightChild->insert(newElement);
		else
			rightChild = new Node<T>(newElement, this, NULL, NULL);
	}
}

template <class T>
void Set<T>::insert(const T & newElement)
{
	if(root != NULL)
		root->insert(newElement);
	else
		root= new Node<T>(newElement, NULL, NULL, NULL);
}
Merriak (61)
Ahhhhh yes, I completely forgot about using the constructor like that. Would have saved a lot of effort.

That did indeed fix the problem! Thanks for the assistance everyone! And for bearing with me... on top of being a newbie it is also 4 am and I am dead tired.
Catfish3 (666)
Well I tried my best, but I messed up node removal. And who knows what else.

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
 
#include <cstddef>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <ostream>

class BinarySearchTree
{
    struct Node
    {
        int data;
        Node *parent;
        Node *left_child;
        Node *right_child;

        explicit Node(int data, Node *parent = NULL):
            data(data),
            parent(parent),
            left_child(NULL),
            right_child(NULL)
        {
        }

        ~Node()
        {
            delete left_child;
            delete right_child;
        }
    };

public:

    BinarySearchTree():
        root(NULL),
        sz(0)
    {
        std::srand(std::time(NULL));
    }

    ~BinarySearchTree()
    {
        delete root;
    }

    bool empty() const
    {
        return sz == 0;
    }

    std::size_t size() const
    {
        return sz;
    }

    void insert(int nd) // nd = Node Data
    {
        if (root != NULL)
        {
            Node *temp = root;

            while (true)
                if (nd < temp->data)
                {
                    if (temp->left_child == NULL)
                    {
                        temp->left_child = new Node(nd, temp);
                        break;
                    }
                    else
                        temp = temp->left_child;
                }
                else
                if (nd > temp->data)
                {
                    if (temp->right_child == NULL)
                    {
                        temp->right_child = new Node(nd, temp);
                        break;
                    }
                    else
                        temp = temp->right_child;
                }
                else // nd == temp->data
                    return; // nothing to insert
        }
        else
            root = new Node(nd);

        ++sz;
    }

    void remove(int nd) // nd = Node Data
    {
        if (root == NULL)
            return;

        Node *target = root;
        bool found_nd = false;

        while (true)
            if (nd < target->data)
            {
                if (target->left_child != NULL)
                    target = target->left_child;
                else
                    break;
            }
            else
            if (nd > target->data)
            {
                if (target->right_child != NULL)
                    target = target->right_child;
                else
                    break;
            }
            else // nd == target->data
            {
                found_nd = true;
                break;
            }

        // target wasn't found, nothing to remove
        if (!found_nd)
            return;

        kill_node(target);
        --sz;
    }

    void display(std::ostream &os = std::clog) const
    {
        os << "BinarySearchTree @ " << this << ", size: " << sz << '\n';
        recursive_display_on(os, root);
    }

    void recursive_display_on(std::ostream &os, const Node *n) const
    {
        if (n == NULL)
            return;

        recursive_display_on(os, n->left_child);
        os << n->data << ' ';
        recursive_display_on(os, n->right_child);
    }

private:

    void kill_node(Node *target)
    {
        // according to Wikipedia, we must now deal with three cases:
        // (1) no children
        // (2) one child
        // (3) two children

        // case (1)
        if (target->left_child == NULL && target->right_child == NULL)
        {
            if (target->parent == NULL) // this can only be the root node
            {
                delete root;
                root = NULL;
            }
            else
            // determine if `target' is a left child, or a right child
            if (target->parent->data < target->data)
                target->parent->right_child = NULL;
            else
                target->parent->left_child = NULL;

            delete target;
        }
        else
        // case (2)
        if (target->left_child == NULL && target->right_child != NULL)
        {
            target->data = target->right_child->data;
            delete target->right_child;
            target->right_child = NULL;
        }
        else
        if (target->left_child != NULL && target->right_child == NULL)
        {
            target->data = target->left_child->data;
            delete target->left_child;
            target->left_child = NULL;
        }
        else
        // case (3)
        {
            // according to Wikipedia, we shouldn't be "consistent" in choosing
            // between in-order predecessor and in-order successor

            if (std::rand() % 2 == 0) // go for predecessor
            {
                Node *p = target->left_child;

                while (p->right_child != NULL)
                    p = p->right_child;

                target->data = p->data;
                kill_node(p);
            }
            else // go for successor
            {
                Node *s = target->right_child;

                while (s->left_child != NULL)
                    s = s->left_child;

                target->data = s->data;
                kill_node(s);
            }
        }
    }

    Node *root;
    std::size_t sz;
};

int main()
{
    BinarySearchTree bst;

//    bst.remove(27);
    bst.insert(-1);
    bst.insert(-5);
    bst.insert(90);
    bst.insert(0);
    bst.insert(-90);
    bst.insert(25);
    bst.insert(2);
    bst.insert(2);
    bst.insert(2);
    bst.insert(23);
    bst.insert(24);
//    bst.remove(-90);
//    bst.remove(-1);
//    bst.remove(-90);
//    bst.remove(25);
    bst.insert(-3);

    bst.display();
}
Pages: 12