C++

Forum

 
Thread Bad Access Code Binary Tree

JesusFreak43 (20)
Hello, I am currently working on this project for my CS class and I am trying to find the number of binary tree nodes that are single parents. So I put some code into a traversal function to find this out, and it worked once and I was able to spit out 6 for the number of single parent nodes. However, now I keep getting this error message
Thread 1: EXC_BAD_ACCESS (code=1, address=0xe00000009)

It shows up next to my code root->lLink = nullptr; and if I take that away it shows up next to my code root->rLink=nullptr; :

template<class elemType>
binaryTreeType<elemType>::binaryTreeType() {
root->lLink = nullptr; //ERROR MSG HERE
root->rLink = nullptr;


}


It also shows up next to my inherited class.

template <class elemType>
class bSearchTreeType : public binaryTreeType<elemType> //ERROR MSG HERE
{...


I know I am kind of new to all of this, but anyone who could possibly help would be greatly appreciated. Thank you so much.

I've tried running it and every time I get this error message. 

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
 
 

```

    /*
    //
    //STACK CLASS WAS HERE... DIDN'T INPUT IT DUE TO SAVING SPACE
    //
    */



    template <class elemType>
    struct nodeType
    {
    elemType info;
    nodeType<elemType> *lLink;
    nodeType<elemType> *rLink;
    
    };

    template <class elemType>
    class binaryTreeType {
    public:
    
    void nonRecursiveInTraversal();
    void insert(const elemType& insertItem);
    static int singleParentCount;
    
    binaryTreeType();

    
    
    protected:
    nodeType<elemType> *root;
    
    
    
    };
    template<class elemType>
    binaryTreeType<elemType>::binaryTreeType() {
    root->lLink = nullptr;
    root->rLink = nullptr;
    
    
    }

    template<class elemType>
    int binaryTreeType<elemType>::singleParentCount = 0;


    template <class elemType>
    void binaryTreeType<elemType> :: nonRecursiveInTraversal()
    {
    stackType<nodeType<elemType>*> stack;
    nodeType<elemType> *current;
    current = root;
    
    while ((current != nullptr) || (!stack.isEmptyStack())){
        
        
        
        if (current != nullptr)
        {
            stack.push(current);
            
            if( (current->rLink == nullptr && current->lLink != nullptr)     || (current->rLink != nullptr  && current->lLink == nullptr) ){
                singleParentCount += 1;
            }
            current = current->lLink;
            
        }
        else
        {
           
            current = stack.top();
            stack.pop();
            cout << current->info << " ";
            current = current->rLink;
           
            
        }
        cout << endl;
        
    }
    
    }








    template <class elemType>
    class bSearchTreeType : public binaryTreeType<elemType>
    {
    public:

    void insert(const elemType& insertItem);
    bool search(const elemType& searchItem);
    //bSearchTreeType();


    
    };
    /*
    template<class elemType>
    bSearchTreeType<elemType>::bSearchTreeType() : binaryTreeType<elemType>  () {

    
    }

    */
    template <class elemType>
    void bSearchTreeType<elemType>::insert (const elemType& insertItem)
    {
    nodeType<elemType> *current;
    nodeType<elemType> *trailCurrent;
    nodeType<elemType> *newNode;
    
    newNode = new nodeType<elemType>;
    newNode->info = insertItem;
    newNode->lLink = nullptr;
    newNode->rLink = nullptr;
    
    if (this->root == nullptr)
    {
        this->root = newNode;
    }
    else
    {
        current = this->root;
        
    while (current != nullptr)
    //START WHILE
    {
            trailCurrent = current;
        
        if(current->info == insertItem)
        {
            
            cout << "The item to be inserted is already in the tree --         duplicates are not allowed." << endl;
            
            return;
        }
        else if(current->info > insertItem){
            current = current-> lLink;
        }
        else {
            current = current->rLink;
        }
    } //END WHILE
            
        if (trailCurrent->info > insertItem)
            trailCurrent->lLink = newNode;
        else
        trailCurrent->rLink = newNode;
    } // END ELSE
    } // END INSERT




    //MAIN FUNCTION
    //
    //

    int main() {
   
    
    
    bSearchTreeType<int> hello;
    hello.insert(4);
    hello.insert(9);
    hello.insert(12);
    hello.insert(1);
    hello.insert(8);
    hello.insert(40);
    hello.insert(41);
    hello.insert(30);
    hello.insert(7);
    hello.insert(90);
    hello.insert(50);
    hello.insert(43);
    hello.insert(6);
   
    
    hello.nonRecursiveInTraversal();
    
    cout << endl << endl << endl;
        cout << "The amount of single parents in this binary search tree     is:";
    cout << hello.singleParentCount;
    
    
   
    
    
    return 0;
    }
Duthomhas (13206)
It is because you have either a dangling pointer or you are dereferencing a null pointer.

Good luck!
salem c (3700)
1. Your indentation needs work.

2. Omitting the stackType presumes that you know that isn't the problem, and also renders us unable to easily replicate the problem.
If you want the most chance of useful help, we need to be able to copy/paste/run.
Any paraphrasing, guessing, omissions just add barriers to that.

At least you could have used std::stack in the meantime to remove one possible area of uncertainty, and made it easier for us to help.


3. My first run under valgrind showed lots of errors, even for just a single insert.
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
 
$ g++ -g -std=c++11 foo.cpp
$ valgrind ./a.out 
==5489== Memcheck, a memory error detector
==5489== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==5489== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
==5489== Command: ./a.out
==5489== 
==5489== Use of uninitialised value of size 8
==5489==    at 0x4009CD: binaryTreeType<int>::binaryTreeType() (foo.cpp:35)
==5489==    by 0x4009B9: bSearchTreeType<int>::bSearchTreeType() (foo.cpp:66)
==5489==    by 0x400918: main (foo.cpp:124)
==5489== 
==5489== Use of uninitialised value of size 8
==5489==    at 0x4009DC: binaryTreeType<int>::binaryTreeType() (foo.cpp:36)
==5489==    by 0x4009B9: bSearchTreeType<int>::bSearchTreeType() (foo.cpp:66)
==5489==    by 0x400918: main (foo.cpp:124)
==5489== 
==5489== Conditional jump or move depends on uninitialised value(s)
==5489==    at 0x400A40: bSearchTreeType<int>::insert(int const&) (foo.cpp:93)
==5489==    by 0x400932: main (foo.cpp:125)
==5489== 
==5489== Conditional jump or move depends on uninitialised value(s)
==5489==    at 0x400A62: bSearchTreeType<int>::insert(int const&) (foo.cpp:97)
==5489==    by 0x400932: main (foo.cpp:125)
==5489== 
==5489== Use of uninitialised value of size 8
==5489==    at 0x400A70: bSearchTreeType<int>::insert(int const&) (foo.cpp:101)
==5489==    by 0x400932: main (foo.cpp:125)
==5489== 
==5489== Use of uninitialised value of size 8
==5489==    at 0x400A9E: bSearchTreeType<int>::insert(int const&) (foo.cpp:104)
==5489==    by 0x400932: main (foo.cpp:125)
==5489== 
==5489== Use of uninitialised value of size 8
==5489==    at 0x400ABC: bSearchTreeType<int>::insert(int const&) (foo.cpp:107)
==5489==    by 0x400932: main (foo.cpp:125)
==5489== 
==5489== Use of uninitialised value of size 8
==5489==    at 0x400ACA: bSearchTreeType<int>::insert(int const&) (foo.cpp:111)
==5489==    by 0x400932: main (foo.cpp:125)
==5489== 
==5489== Use of uninitialised value of size 8
==5489==    at 0x400AEC: bSearchTreeType<int>::insert(int const&) (foo.cpp:114)
==5489==    by 0x400932: main (foo.cpp:125)
==5489== 
==5489== 
==5489== HEAP SUMMARY:
==5489==     in use at exit: 72,728 bytes in 2 blocks
==5489==   total heap usage: 2 allocs, 0 frees, 72,728 bytes allocated
==5489== 
==5489== LEAK SUMMARY:
==5489==    definitely lost: 0 bytes in 0 blocks
==5489==    indirectly lost: 0 bytes in 0 blocks
==5489==      possibly lost: 0 bytes in 0 blocks
==5489==    still reachable: 72,728 bytes in 2 blocks
==5489==         suppressed: 0 bytes in 0 blocks
==5489== Rerun with --leak-check=full to see details of leaked memory
==5489== 
==5489== For counts of detected and suppressed errors, rerun with: -v
==5489== Use --track-origins=yes to see where uninitialised values come from
==5489== ERROR SUMMARY: 9 errors from 9 contexts (suppressed: 0 from 0)


4. So I included one constructor you missed, and fixed the other to not dereference garbage.
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
 
#include <iostream>
#include <stack>

//STACK CLASS WAS HERE... DIDN'T INPUT IT DUE TO SAVING SPACE
#define stackType stack

using namespace std;

template < class elemType > struct nodeType {
   elemType info;
   nodeType < elemType > *lLink;
   nodeType < elemType > *rLink;
   nodeType() {
       //!! Added
       lLink = nullptr;
       rLink = nullptr;
   }
};

template < class elemType > class binaryTreeType {
public:
  void nonRecursiveInTraversal();
  void insert(const elemType & insertItem);
  static int singleParentCount;
  binaryTreeType();

protected:
  nodeType < elemType > *root;
};

template < class elemType > binaryTreeType < elemType >::binaryTreeType()
{
  root = nullptr;
//!! Wrong, you just created a binaryTreeType, how can root point to anything
//  root->lLink = nullptr;
//  root->rLink = nullptr;
}

template < class elemType > int binaryTreeType < elemType >::singleParentCount = 0;


template < class elemType > void binaryTreeType < elemType >::nonRecursiveInTraversal()
{
  stackType < nodeType < elemType > *>stack;
  nodeType < elemType > *current;
  current = root;

  while ((current != nullptr) || (!stack.empty())) {
    if (current != nullptr) {
      stack.push(current);
      if ((current->rLink == nullptr && current->lLink != nullptr) ||
          (current->rLink != nullptr && current->lLink == nullptr)) {
        singleParentCount += 1;
      }
      current = current->lLink;
    } else {
      current = stack.top();
      stack.pop();
      cout << current->info << " ";
      current = current->rLink;
    }
    cout << endl;
  }
}

template < class elemType > class bSearchTreeType:public binaryTreeType < elemType > {
public:
  void insert(const elemType & insertItem);
  bool search(const elemType & searchItem);
};

template < class elemType > void bSearchTreeType < elemType >::insert(const elemType & insertItem)
{
  nodeType < elemType > *current;
  nodeType < elemType > *trailCurrent;
  nodeType < elemType > *newNode;

  newNode = new nodeType < elemType >;
  newNode->info = insertItem;
  newNode->lLink = nullptr;
  newNode->rLink = nullptr;

  if (this->root == nullptr) {
    this->root = newNode;
  } else {
    current = this->root;
    while (current != nullptr) {
      trailCurrent = current;
      if (current->info == insertItem) {
        cout << "The item to be inserted is already in the tree --         duplicates are not allowed." << endl;
        return;
      } else if (current->info > insertItem) {
        current = current->lLink;
      } else {
        current = current->rLink;
      }
    }

    if (trailCurrent->info > insertItem)
      trailCurrent->lLink = newNode;
    else
      trailCurrent->rLink = newNode;
  }
}

int main()
{
  bSearchTreeType < int >hello;
  hello.insert(4);
  hello.insert(9);
  hello.insert(12);
  hello.insert(1);
  hello.insert(8);
  hello.insert(40);
  hello.insert(41);
  hello.insert(30);
  hello.insert(7);
  hello.insert(90);
  hello.insert(50);
  hello.insert(43);
  hello.insert(6);

  hello.nonRecursiveInTraversal();

  cout << endl << endl << endl;
  cout << "The amount of single parents in this binary search tree     is:";
  cout << hello.singleParentCount;
  cout << endl;

  return 0;
}

This is now silent in valgrind, and prints 6 as the answer.
Topic archived. No new replies allowed.