What is happening here

[nin234]

I am trying to create a Binary Search Tree in the code below. I am
posting this question more from a C++ point of view rather than Binary
search tree techniques.
This is is the output of running the program
../a.out
6
5
7
4
8
0
top->k 6
h->k 6

Basically it is only inserting the top or the root of the tree. When I
turn on the debugger gdb. I am able to see the creation of node to
insert 5 in the recursive function insertR. But top->l is still a null
variable. Why is this due to? Is it something to do with static nature
of top


#include <iostream>

//Build a binary tree from user input and print out the tree by
//different traversal techniques and also provide a search function
//
template <class Key> class BST
{
Key k;
BST *l, *r;
static BST *top;
void insertR(Key& , BST *);
void printR (BST *);
public:
void insert (Key& k);
void print ();
BST (Key k) : k (k) {l=0; r = 0;}
BST () {l=0; r=0; k=0;}
};

template <class Key> BST<Key> *BST<Key>::top = 0;

template <class Key> void BST<Key>::insert (Key& k)
{
if (top == 0)
{
top = new BST (k);
return;
}
insertR (k, top);
}
template <class Key> void BST<Key>:rint ()
{
if (top == 0)
return;
std::cout << "top->k " << top->k << std::endl;
printR (top);
std::cout << std::endl;
}
template <class Key> void BST<Key>:rintR (BST *h)
{
if (h == 0)
return;
std::cout << "h->k " << h->k << std::endl;
printR (h->l);
printR (h->r);
}
template <class Key> void BST<Key>::insertR (Key& kl, BST *h)
{
if (h == 0)
{
h = new BST (kl);
return;
}
if (kl < h->k)
insertR (kl, h->l);
if (kl > h->k)
insertR (kl, h->r);
}
int main ()
{
BST<int> tst;
int k;
do {
std::cin >> k;
tst.insert (k);
}
while (k > 0);
tst.print();
}

 

[Dietmar Kuehl]

I am trying to create a Binary Search Tree in the code below.

"Trying" is indeed the best description...

template <class Key> class BST
{
Key k;
BST *l, *r;
static BST *top;
void insertR(Key& , BST *);
void printR (BST *);
public:
void insert (Key& k);
void print ();
BST (Key k) : k (k) {l=0; r = 0;}
BST () {l=0; r=0; k=0;}
};

This is a pretty lame binary tree: you can only have one instance
per key type. This is almost certainly not what anybody wants! You
should split your tree into two types:
- The tree type itself which serves as an interface to the actual
representation and essentially holds the root.
- A node type which represents an individual node of the tree. This
type will be private detail to the tree type and probably use only
public members (the tree would still be the only entity which can
access it).

template <class Key> void BST<Key>::insertR (Key& kl, BST *h)

The obvious problems lies in the declaration of the second parameter:
you pass the pointer by value, i.e. changing 'h' only modifies the
local copy. But...

{
if (h == 0)
{
h = new BST (kl);

.... judging from this line I would claim that you want to pass change
its global value. Thus, you should pass a reference to the pointer.

 

[Donovan Rebbechi]

I am trying to create a Binary Search Tree in the code below. I am
posting this question more from a C++ point of view rather than Binary
search tree techniques.
This is is the output of running the program
./a.out
6
5
7
4
8
0
top->k 6
h->k 6

Basically it is only inserting the top or the root of the tree. When I
turn on the debugger gdb. I am able to see the creation of node to
insert 5 in the recursive function insertR. But top->l is still a null
variable. Why is this due to? Is it something to do with static nature
of top


#include <iostream>

//Build a binary tree from user input and print out the tree by
//different traversal techniques and also provide a search function
//
template <class Key> class BST
{
Key k;

Do you need this variable ?

BST *l, *r;
static BST *top;

Shouldn't be static

void insertR(Key& , BST *);

Do you use member data for this function ? If not, should be declared static.

void printR (BST *);
public:
void insert (Key& k);
void print ();
BST (Key k) : k (k) {l=0; r = 0;}
BST () {l=0; r=0; k=0;}
};

template <class Key> BST<Key> *BST<Key>::top = 0;

template <class Key> void BST<Key>::insert (Key& k)
{
if (top == 0)
{
top = new BST (k);
return;
}
insertR (k, top);
}
template <class Key> void BST<Key>:rint ()
{
if (top == 0)
return;
std::cout << "top->k " << top->k << std::endl;
printR (top);
std::cout << std::endl;
}
template <class Key> void BST<Key>:rintR (BST *h)
{
if (h == 0)
return;
std::cout << "h->k " << h->k << std::endl;
printR (h->l);
printR (h->r);
}
template <class Key> void BST<Key>::insertR (Key& kl, BST *h)
{
if (h == 0)
{
h = new BST (kl);

This doesn't do what you think it does.

It
(1) allocates a new tree object, and
(2) assigns the address of that object to the variable h.

but that doesn't help you much, because when you ...

return;

from the function, the caller does not know about the value that you assigned
to h in the insertR function.

I think you'd need something like

insertR ( Key& kl, BST** h)
{
*h = new BST(kl); // when I call insertR ( k,&(h->l)),h->l == new BST(kl)

or pass by reference.


Cheers,

 

[Howard]

I am trying to create a Binary Search Tree in the code below. I am

I'm adding some comments in addition to what others have given already...

template <class Key> class BST
{
Key k;

You have a member named k here. But look at your functions below.. You pass
a parameter k there, also. Not a good practice. Do you know which k your
functions are referring to?

BST *l, *r;
static BST *top;
void insertR(Key& , BST *);
void printR (BST *);
public:
void insert (Key& k);
void print ();
BST (Key k) : k (k) {l=0; r = 0;}
BST () {l=0; r=0; k=0;}
};

template <class Key> BST<Key> *BST<Key>::top = 0;

template <class Key> void BST<Key>::insert (Key& k)
{
if (top == 0)
{
top = new BST (k);

Which k is getting inserted here: the parameter, or the member?

return;
}
insertR (k, top);
}

Blank lines here would help reading this (as would indentatiion, but that
could just be my newsreader)

template <class Key> void BST<Key>:rint ()

int main ()
{
BST<int> tst;
int k;
do {
std::cin >> k;
tst.insert (k);

You're calling the insert function, passing it an int. But aren't your
functions declaring the k parameter as type Key? Which is it?

}
while (k > 0);
tst.print();
}

-Howard