C++

Forum

 
Print and Insert Binary Search Tree

RaineShadow (8)
When I try to print out the tree it doesn't. I don't know if it's the insert function or the print function and I've been messing around with it for a good two hours trying to figure out what could be the problem. Could someone look over the code and help? That'd be awesome.

mybst.h 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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
 
//***************************************************************************
//                              mybyst.h                                    *
//                          by Dr. Stockwell                                *
//                           Giselle Colon                                  *
//                       Programming II MW 4:15                             *
//                        Due October 17, 2012                              *
//                            Assingment 4                                  *
//***************************************************************************

#ifndef MY_BINARY_SEARCH_TREE
#define MY_BINARY_SEARCH_TREE
#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;

template <class T>
struct BinaryNode{
   T data;
   BinaryNode<T> *left, *right;
   BinaryNode(){
        left = right = 0;
   }
   BinaryNode(const T& value): data(value){
        left = right = 0;
   }
};

template <class T>
class BST{
protected:
   BinaryNode<T> *root;
public:
   explicit BST(){root=0;}
   BinaryNode<T> *getroot(){return root;}
   virtual ~BST(){nuke(root);}
   bool is_empty(){return root==0;}
   int height(){return height(root);}
   int height(BinaryNode<T> *p){
        if(p){
           int h1 = height(p->left);
           int h2 = height(p->right);
           return h1 > h2 ? 1+h1: 1+h2;
        }
        else
           return 0;
   }
   void nuke(){nuke(root);}
   void nuke(BinaryNode<T> * & t){
        if(t){
           nuke(t->left);
           nuke(t->right);
           delete t;
        }
        t=0;
   }
   int size(){return size(root);}
   int size(BinaryNode<T> *t){
        if(t)
           return 1 + size(t->left) + size(t->right);
        else
           return 0;
   }
   BinaryNode<T> *find(T item){return find(item, root);}
   BinaryNode<T> *find(T item, BinaryNode<T> *t){
        if(!t) return 0;
        if(t->data == item)
           return t;
        else
           if(item < t->data)
                return find(item, t->left);
           else
                return find(item, t->right);
   }
   void print_tree(){print_tree(root);}
   void print_tree(BinaryNode<T> *p){
        static int ct = 0;
        for(int i=0; i<13; i++){
           cout << "[" << p+i << "]" << endl;
        }
        if(p){
           print_tree(p->left);
           cout << fixed << setw(10) << p->data;
           if(++ct % 7 == 0) cout << endl;
           print_tree(p->right);
        }
   }
   BinaryNode<T> *findmin(BinaryNode<T> *t){
        if(t)
           if(t->left)
                return findmin(t->left);
           else
                return t;
        else
           return 0;
   }
   BinaryNode<T> *removemin(BinaryNode<T> *t){
        if(t)
           if(t->left)
                return findmin(t->left);
           else
                return t;
        else
           return 0;
   }
   void remove(const T& item){remove(item, root);}
   void remove(const T& item, BinaryNode<T> * & t){
//      BinaryNode<T> *p;
        if(!t){
           cout << "\nError, cannot delete item, not found.\n";
           return;
        }
        if(item < t->data)
           remove(item, t->left);
        else
//         if(t->data < item)
                remove(item, t->right);
//         else{
                // t points to item to be deleted
//              if(t->left != 0 && t->right != 0){ // node has 2 children
//                 p = removemin(t->data);
//                 delete p;
//              }
//              else{ // 1 child or none
//                 p=t;
//                 t=t->right ? t->right : t->left;
//                 delete p;
//              }
//         }
   }
   void dump_array(T x[], BinaryNode<T> *p){
        static int j = 0;
        if(p){
           dump_array(x, p->left);
           x[j++] = p->data;
           dump_array(x, p->right);
        }
   }
   void dump_array(T x[]){
        dump_array(x, root);
   }
   void insert(const T& item){insert(item, root);}
   void insert(const T& item, BinaryNode<T> * & t){
        if(!t){
           t= new BinaryNode<T>(item);
        }
        else{
           if(item < t->data){
                insert(item, t->left);
           }
           else{
                if(item > t->data){
                   insert(item, t->right);
                }
                else{
                   // duplicate, do not insert it
                   if(item == t->data){
                        cout << "\nDuplicate item not inserted...\n";
                   }
                   else{
                        cout << "There was a problem." << endl;
                   }
                }
           }
        }
   }
};
#endif


four.cpp

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
 
//***************************************************************************
//                           Giselle Colon                                  *
//                       Programming II MW 4:15                             *
//                        Due October 17,2012                               *
//                            Assignment 4                                  *
//***************************************************************************

// Basic binary search tree manipulation
// Insert, traverse, delete
#include <iostream>
#include "mybst.h"
using namespace std;

int main(){
   int a = 0;
   int count = 0;
   int b[]={58,12,80,75,204,4,18,13,14,15,28,31,40};

   cout << "Hello this is the program for binary search tree manipulation"
        << endl;

   BST<int>bst;
   bst.insert(58);
   bst.insert(12);
   bst.insert(80);
   bst.insert(75);
   bst.insert(204);
   bst.insert(4);
   bst.insert(18);
   bst.insert(13);
   bst.insert(14);
   bst.insert(15);
   bst.insert(28);
   bst.insert(31);
   bst.insert(40);

   BST<int>rmv;

   BST<bool>empty;

   BST<int>find;

   BST<int>print;

   print.print_tree();

//   for(int i=0; i<13; i++){
//      if(empty.is_empty()==1){
//         int c = b[i];
//         rmv.remove(c);
//         cout << c << endl;
//         cout << i << "*********************" << endl;
//      }
//      else
//         break;
//   }

   return 0;
}
AbstractionAnon (6954)
You've created 5 BST instances (bst, rmv, empty, find, print). The only instance that has any data is bst. when you call print_tree(), you're calling it using the print instance which is empty.

Try this:
 
 
bst.print_tree();

RaineShadow (8)
There is still a problem with the remove function. But that is definitely helpful and print_tree() did work.

mybst.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
 
   void remove(const T& item){remove(item, root);}
   void remove(const T& item, BinaryNode<T> * & t){
        BinaryNode<T> *p;
        if(!t){
           cout << "\nError, cannot delete item, not found.\n";
           return;
        }
        if(item < t->data)
           remove(item, t->left);
        else
           if(t->data < item)
                remove(item, t->right);
           else{
                // t points to item to be deleted
                if(t->left != 0 && t->right != 0){ // node has 2 children
                   p = removemin(t->data);
                   delete p;
                }
                else{ // 1 child or none
                   p=t;
                   t=t->right ? t->right : t->left;
                   delete p;
                }
           }
   }


four.cpp

This is where I call it.

 
 
   bst.remove(12);


The error that comes up is:

In file included from four.cpp:11:
mybst.h: In member function âvoid BST<T>::remove(const T&, BinaryNode<T>*&) [with T = int]â:
mybst.h:103: instantiated from âvoid BST<T>::remove(const T&) [with T = int]â
four.cpp:38: instantiated from here
mybst.h:118: error: invalid conversion from âintâ to âBinaryNode<int>*â
mybst.h:118: error: initializing argument 1 of âBinaryNode<T>* BST<T>::removemin(BinaryNode<T>*) [with T = int]â

Line 103 in .h is line 1
Line 118 in .h is line 16
RaineShadow (8)
And the removemin function I edited it from the one above.

1
2
3
4
5
6
7
8
9
 
   BinaryNode<T> *removemin(BinaryNode<T> *t){
        if(t)
           if(t < t->right)
                return removemin(t->right);
           else
                return t;
        else
           return 0;
   }
RaineShadow (8)
After some editing there is something wrong with the calling of removemin. Here is what it's supposed to do.

it first finds the minimum node in the subtree to the right, then uses remove to delete that node
Topic archived. No new replies allowed.