Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > What is happening here

Reply
Thread Tools

What is happening here

 
 
nin234@yahoo.com
Guest
Posts: n/a
 
      02-21-2005
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();
}

 
Reply With Quote
 
 
 
 
Dietmar Kuehl
Guest
Posts: n/a
 
      02-21-2005
(E-Mail Removed) wrote:
> 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.
--
<(E-Mail Removed)> <http://www.dietmar-kuehl.de/>
<http://www.contendix.com> - Software Development & Consulting

 
Reply With Quote
 
 
 
 
Donovan Rebbechi
Guest
Posts: n/a
 
      02-21-2005
On 2005-02-21, http://www.velocityreviews.com/forums/(E-Mail Removed) <(E-Mail Removed)> wrote:
> 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,
--
Donovan Rebbechi
http://pegasus.rutgers.edu/~elflord/
 
Reply With Quote
 
Howard
Guest
Posts: n/a
 
      02-22-2005

<(E-Mail Removed)> wrote in message
news:(E-Mail Removed) oups.com...
>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



 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Basics of VHDL. Whats happening here? vikramtheone VHDL 1 06-01-2009 08:56 PM
whats happening here parag_paul@hotmail.com C Programming 4 03-25-2008 12:41 PM
what happening here :) sarath MCDST 9 11-26-2005 10:25 PM
What's happening here? Scottie Computer Support 9 05-19-2004 03:11 PM
what is happening here? dan miller (moderator, s.p.d) Python 3 04-08-2004 11:11 AM



Advertisments