Binary Tree class Segmentation fault

reikendude (2)
I've been working on this program for a while now and finally got it to compile, but it gives me a segmentation fault. Can someone help me find out what's causing the segmentation fault?


binTree.h:
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
 
#ifndef BINTREE_H
#define BINTREE_H

#include "binTreeNode.h"

template <class T> class binTree
{
        public:
                binTree();              // default constructor

                bool empty() const;     // checks if tree is empty
                int size() const;       // returns number of nodes
                int height() const;     // returns height of the tree
                virtual void insert(const T&); // inserts a node in the shortes$

                void inOrder (void (*) (T&));   // inorder traversal of tree
                void preOrder (void (*) (T&));  // preorder traversal of tree
                void postOrder (void (*) (T&)); // postorder traversal of tree

        protected:
                binTreeNode <T>* root;          //root of tree

        private:
                int size(binTreeNode <T>*) const;       //private version of si$
                int height(binTreeNode <T>*) const;     //private version of he$
                void insert(binTreeNode <T>*&, const T&); //private version of $

                void inOrder(binTreeNode<T>*, void(*) (T&)); //private version $
                void preOrder(binTreeNode<T>*, void(*) (T&)); //private version$
                void postOrder(binTreeNode<T>*, void(*) (T&)); //private versio$
};

// Method Definitions

template <class T>
binTree<T>::binTree()
{
        root = NULL;
}

template <class T>
bool binTree<T>::empty() const
{
        if (!root)
        return true;
        else
        return false;
}

template <class T>
int binTree<T>::size() const
{
        return size(root);
}

template <class T>
int binTree<T>::height() const
{
        return height(root);
}

template <class T>
void binTree<T>::insert(const T& x)
{
        insert(root, x);
}

template <class T>
void binTree<T>::inOrder(void (*f) (T&))
{
        inOrder(root, f);
}


template <class T>
void binTree<T>::preOrder (void (*f) (T&))
{
        preOrder(root, f);
}

template <class T>
void binTree<T>::postOrder (void (*f) (T&))
{
        postOrder(root, f);
}

template <class T>
int binTree<T>::size(binTreeNode <T>* node) const
{
        if (node == NULL) return 0;
        else
                return size(node->left) + 1 + size(node->right);
}

template <class T>
int binTree<T>::height(binTreeNode <T>* node) const
{
        if (node == NULL || ((node->left == NULL) && (node->right == NULL)))
                return 0;

        int lefth = height(node->left);
        int righth = height(node->right);
        cout << "left: " << lefth << " right: " << righth << endl;
        if (lefth > righth)
  return lefth + 1;
        if (righth > lefth)
                return righth + 1;
        else
                return righth + 1;
}

template <class T>
void binTree<T>::insert(binTreeNode <T>*& node, const T& x)
{
        if (node == NULL)
        {
                binTreeNode<T>* newnode = new binTreeNode<T>(x);
                newnode->data = x;
                root = newnode;
                return;
        }
        binTreeNode <T>* ptr1 = node;
        binTreeNode <T>* ptr2 = node;
        int i = 0;
        while (ptr1 != NULL)
     {
                ptr2 = ptr1;
                if (height(ptr1->left) > height(ptr1->right))
                {
                        i = -1;
                        ptr1 = ptr1->right;
                        cout << "right" << endl;
                }
                if (height(ptr1->right) > height(ptr1->left))
                {
                        i = 1;
                        ptr1 = ptr1->left;
                        cout << "left" << endl;
                }
                else
                {
                        i = 1;
                        ptr1 = ptr1->left;
                        cout << "equal" << endl;
                }
        }
 binTreeNode<T>* newnode = new binTreeNode<T>(x);
        if (i == -1)
        ptr2->right = newnode;
        else
        ptr2->left = newnode;

        ptr1->data = x;
}

template <class T>
void binTree<T>::inOrder(binTreeNode<T>* node, void (*f)(T&))
{
        if (node == NULL)
                return;
        inOrder(node->left,f);
        f(node->data);
        inOrder(node->right,f);
}

template <class T>
void binTree<T>::preOrder(binTreeNode<T>* node, void(*f) (T&))
{
        if (node == NULL)
                return;
        f(node->data);
        preOrder(node->left, f);
        preOrder(node->right, f);
}

template <class T>
void binTree<T>::postOrder(binTreeNode<T>* node, void(*f) (T&))
{
        if (node == NULL)
                return;
        postOrder(node->left, f);
        postOrder(node->right, f);
        f(node->data);
}

#endif


binTreeNode.h:
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
 
#ifndef BINTREENODE_H
#define BINTREENODE_H
#include "/home/onyuksel/courses/340/common/340.h"

template <class T> class binTree;

template <class T> class binTreeNode
{
        friend class binTree<T>;

        public:
                //default constructor
                binTreeNode (const T&);
        private:
                T data;                                 //data value in node
                binTreeNode <T> *left, *right;          //links to other nodes
};

template <class T>
binTreeNode<T>::binTreeNode(const T& d)
{
        data = d;
        left = NULL;
        right = NULL;
}

#endif


If you need the driver program I can provide it as well.


Last edited on
Azagaros (410)
Segmentation faults are because a pointer goes invalid.

and why are these void pointers?
1
2
3
4
 

                void inOrder (void (*) (T&));   // inorder traversal of tree
                void preOrder (void (*) (T&));  // preorder traversal of tree
                void postOrder (void (*) (T&)); // postorder traversal of tree


They should be the template type pointers.

the type would only correspond to the data element of the Node class. Not the pointers in the tree which would be the node class.
Last edited on
reikendude (2)
Those are not void pointers, they are pointers to void functions. I know that part is not wrong because that came straight off of the assignment sheet. Also, the segmentation fault doesn't happen when I take out the else code at line 140 and make the if before that an else, but then I get the wrong output.

If I remove this:
1
2
3
4
5
6
7
 
                else
                {
                        i = 1;
                        ptr1 = ptr1->left;
                        cout << "equal" << endl;
                }
        }

and make the if before an else, it works, but with output errors.
Topic archived. No new replies allowed.