output problem

kakashi316 (156)
Im writing a program to print binary/bninary search trees. I can get the binary trees to print,but not the binary search trees.im going to try to give the most relevant code. but its alot.

main:
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
 
#include "BTree.h"
#include "BSTree.h"
#include<stdlib.h>
#include<iostream>
using namespace std;
int main()
{
      BTree<int> BT;
      BSTree<int>BST;
      
      int x;
      int i;
      for(i=1;i<=5; i++)
      {
              x=rand()%100;
              BT.Insert(x);
              BST.Insert(x);
      }
      cout<<"Random Binary Tree: "<<endl;
      cout<<"Inorder"<<endl;
      BT.InOrder(cout);
      cout<<endl;
       cout<<"Preorder"<<endl;
      BT.PreOrder(cout);
      cout<<endl;
      cout<<"Postorder"<<endl;
      BT.PostOrder(cout);
      cout<<endl;
      cout<<"Binary Search tree: "<<endl;
       cout<<"Inorder"<<endl;
      BST.InOrder(cout);
      cout<<endl;
       cout<<"Postorder"<<endl;
      BST.PostOrder(cout);
      cout<<endl;
       cout<<"Preorder"<<endl;
      BST.PreOrder(cout);
      cout<<endl;
      //x=46;
//      cout<<"Search: "<<x<<endl;
//      if(BST.Search(x))
//      {
//         cout<<"Found"<<endl;
//      }
//      else
//      {
//          cout<<"Not found"<<endl;
//       }

      
      //cout<<"Delete: "<<x<<endl;
      //BST.Delete(x);
      //BST.InOrder(cout);
    //  cout<<endl;
//      BST.PreOrder(cout);
//      cout<<endl;
//      
     char quit;
     cin>>quit;
     return 0;
}


Binary search implementation
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
 
#include "Node.h"
#include "BSTree.h"
#include "BTree.cpp"
#include<iostream>
#include<stdlib.h>
using namespace std;
template<class ItemType>
bool BSTree<ItemType>::R_Search(TreePtr t,ItemType x)
{
     if(t==NULL)
         return 0;
     else if(t->item==x)
          return 1;
     else if(x<t->item)
          return R_Search(t->Lt,x);
     else
             return R_Search(t->Rt,x);
}

template<class ItemType>
void BSTree<ItemType>::R_Insert(TreePtr &t,ItemType x, int lev,int bal)
{
     if(t==NULL)
                t= new NodeType<ItemType>(x,lev);
     else if(x<t->item)
          R_Insert(t->Lt,x,lev+1,bal);
         else
             R_Insert(t->Rt,x,lev+1,bal);
}
template<class ItemType>
bool BSTree<ItemType>::R_Delete(TreePtr &t,ItemType x)
{
     TreePtr delnode,parent,child;
     if(t==NULL)
      return 0;
     else if(x<t->item)
       return R_Delete(t->Lt,x);
     else if(x>t->item)
       return R_Delete(t->Rt,x);
     else
     {
         if((t->Lt==NULL)&&(t->Rt==NULL))
         {
            delete t;
            t=NULL;
         }
         else if(t->Lt==NULL)
         {
              delnode=t;
              t=t->Rt;
              delete delnode;
         }   
         else if(t->Rt==NULL)
         {
              delnode=t;
              t=t->Lt;
              delete delnode;
         } 
         else
         {
             parent=t;
             child=t->Rt;
             if(child->Lt==NULL)
             {
                parent->item=child->item;
                parent->Rt=child->Rt;
                delete child;
                return 0;
             }
             else
             {
                 while(child->Lt!=NULL)
                 {
                    parent=child;
                    child=child->Lt;
                    t->item=child->item;
                    parent->Lt=child->Lt;
                    delete child;
                    return 1;
                  }
             }
         }
     }
}
template<class ItemType>
BSTree<ItemType>::~BSTree()
{
    Tree=NULL;
}

BSTree<int>BST;


header:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
#ifndef BSTree_H
#define BSTree_H
#include "BTree.h"
#include<iostream>
#include<stdlib.h>
using namespace std;
template <class ItemType>
class BSTree: public BTree<ItemType>
{
      private:
               typedef NodeType<ItemType> * TreePtr;
               TreePtr Tree;
               void R_Insert(TreePtr &, ItemType x, int=0, int=0);
               bool R_Search(TreePtr, ItemType);
               bool R_Delete(TreePtr &,ItemType);
   public:
    BSTree(){Tree = NULL;};
    virtual void Insert(ItemType x){R_Insert(Tree, x);};
    bool Search(ItemType x){return R_Search(Tree, x);};
    bool Delete(ItemType x){return R_Delete(Tree, x);};
    ~BSTree();
};
#endif


binary tree implementation
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
 
#ifndef BTree_H
#define BTree_H

#include <fstream>
#include <stdlib.h>
//#include "Queue.cpp"
//#incldue "Stack.cpp
#include "Node.cpp"
#include<iostream>
using namespace std;

template <class ItemType>
class BTree
{
      typedef NodeType<ItemType> * TreePtr;
      TreePtr Tree;
      void R_InOrder(TreePtr, ostream &);
      void R_PreOrder(TreePtr, ostream &);
      void R_PostOrder(TreePtr, ostream &);
      int R_Height(TreePtr);
      int R_Count(TreePtr);
      void R_Clear(TreePtr &);
      void R_Insert(TreePtr &, ItemType x, int=0, int=0);
   public:
    BTree(){Tree=NULL;};
      void InOrder(ostream &output){R_InOrder(Tree, output);};
      void PreOrder(ostream &output){R_PreOrder(Tree, output);};
      void PostOrder(ostream &output){R_PostOrder(Tree, output);};
      //void BFS(ostream &output);
      //void DFS(TreePtr,ostream &output);
      int Height(){return R_Height(Tree);};
      int Count(){return R_count(Tree);};
      virtual void Insert(ItemType x){R_Insert(Tree, x);};
      void Clear(){R_Clear(Tree);};
      ~BTree(){R_Clear(Tree);};

};
#endif


I know its alot of code,but i could really use help on this.If anyone can help me i would appreciate it.I needed i can post the binary trr implementation in another post.
firedraco (6247)
What function/code segment exactly is the problem?
kakashi316 (156)
I believe my problem is with my BST implementation,either something to do with the insertion or the deconstructor. Im not entirely sure though.
kakashi316 (156)
im going to post my code for the binary tree implementation,since i think it will help.

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
 
#include "Node.h"
#include "BTree.h"
//#include "Queue.h"
//#include "Stack.h"
#include<iostream>
using namespace std;
template <class ItemType>
int BTree<ItemType>::R_Height(TreePtr t)
{
    if (t==NULL)
       return 0;
    int LTHT=R_Height(t->Lt);
    int RTHT=R_Height(t->Rt);
    if (LTHT>=RTHT)
    {
       return(LTHT+1);
    }
    else
        return(RTHT+1);
}
template <class ItemType>
int BTree<ItemType>::R_Count(TreePtr t)
{
    if (t==NULL)
       return 0;
    int LTCT=R_Count(t->Lt);
    int RTCT=R_Count(t->Rt);
    return (RTCT+LTCT+1);
}

template<class ItemType>
void BTree<ItemType>::R_Insert(TreePtr &t,ItemType x, int lev,int bal)
{
     bool GoLt;
     if(t==NULL)
     {
                t= new NodeType<ItemType>(x,lev);
                t->Lt=t->Rt=NULL;
     }
     else
     {
         GoLt=rand()%2;
         if(GoLt)
          R_Insert(t->Lt,x,lev+1,bal);
         else
             R_Insert(t->Rt,x,lev+1,bal);
     }
}
template<class ItemType>
void BTree<ItemType>::R_PreOrder(TreePtr t,ostream& output)
{
     if(t!=NULL)
     {
                output<<t->item<<"("<<t->level<<")";
                R_PreOrder(t->Lt,output);
                R_PreOrder(t->Rt,output);
     }
}
template<class ItemType>
void BTree<ItemType>::R_InOrder(TreePtr t,ostream& output)
{
     if(t!=NULL)
     {
                
                R_InOrder(t->Lt,output);
                output<<t->item<<"("<<t->level<<")";
                R_InOrder(t->Rt,output);
     }
}
template<class ItemType>
void BTree<ItemType>::R_PostOrder(TreePtr t,ostream & output)
{
     if(t!=NULL)
     {
                R_PostOrder(t->Lt,output);
                R_PostOrder(t->Rt,output);
                output<<t->item<<"("<<t->level<<")";
     }
}
//#define SIZE 20
//template<class ItemType>
//void BTree<ItemType>::BFS(ostream output)
//{
//     TreePtr T=Tree;
//     Queue<TreePtr,Size>q;
//     q.enqueue(t);
//     while(Q.IsEmpty())
//     {
//        q.dequeue(t);
//        output<<t->item<<"("<<t->level")";
//        if(T->Lt!=NULL) q.enqueue(t->Lt);
//        if(T->Rt!=NULL) q.enqueue(t->Rt);
//     }
//}

//template<class ItemType>
//void BTree<ItemType>::DFS(TreePtr t,ostream output)
//{
//     Stack<TreePtr>s;
//     s.push(Tree);
//     while(s.IsEmpty())
//     {
//        s.pop(t);
//        output<<t->item;
//        if(T->Rt!=NULL) s.push(t->Rt);
//        if(T->Lt!=NULL) s.push(t->Lt);
//     }
//}
template<class ItemType>
void BTree<ItemType>::R_Clear(TreePtr &t)
{
     if (t!=NULL)
     {
        R_Clear(t->Lt);
        R_Clear(t->Rt);
        delete t;
        t=NULL; 
     }
}
kakashi316 (156)
ok, i have a more specific question that does not involve alot of code

would the deconstructor that i have:

1
2
3
4
5
 
template<class ItemType>
BSTree<ItemType>::~BSTree()
{
    Tree=NULL;
}


would that be affecting my ability to insert especially if i have it also declared in the constructor?
Topic archived. No new replies allowed.