binary tree

hello there
i'm trying to implement a binary tree using this class:

class btree{
public:
int key;
btree *left;
btree *right;
btree(){left=NULL; right=NULL;}
void insert(int key);
};

void btree::insert(int key1){
if (this==NULL){
this=new btree();
this->key=key1;

}
else if(key1>this->key)
this->right.insert(key1);
else if(key1<this->key)
this->left.insert(key1);
}


the call:

int main(){
btree radice1;
radice1.insert(5);

return 0;
}

gives me the following error:

albero_binario1.cpp: In member function ‘void btree::insert(int)’:
albero_binario1.cpp:34:18: error: lvalue required as left operand of assignment
albero_binario1.cpp:39:15: error: request for member ‘insert’ in ‘((btree*)this)->btree::right’, which is of non-class type ‘btree*’
albero_binario1.cpp:41:14: error: request for member ‘insert’ in ‘((btree*)this)->btree::left’, which is of non-class type ‘btree*’

what can i do?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void btree::insert(int key1)
{
  if (this==NULL)  // Impossible.  The object whose method you call cannot be in address NULL
    {
      this=new btree();  // Error.  This exists.  Overwriting is not permitted
      this->key=key1;
    }
  else if(key1>this->key)
    {
      this->right.insert(key1);  // right is a pointer. Dereference with ->
      // You will still fail, because 0==right
      // EDIT: not really 0, but undefined.  An uninitialized pointer.
    }
  else if(key1<this->key)
    {
      this->left.insert(key1);  // left is a pointer.  Dereference with ->
      // You will still fail, because 0==left
    }
}

Consider this instead (and what does it require from class btree):
1
2
3
4
5
6
7
int main()
{
  btree * root = new btree(5);
  root->insert(42);
  delete root;
  return 0;
}

Remember the copy constructor, copy assignment, and destructor.
Last edited on
and you forgot to deal the "key==key1" situation if you didn't mean that way.
thanks a lot
but following the way you suggested me in the main,
how should i implement the function insert?
This is the part, where you have to think.

What is the state of the tree before insert is called?
When the insert() of a node on a tree is called, what possibilities there are?
What should the state of the tree be after the insertion has completed?
Consider having seperate data structures for the tree?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct btree {
	int data;
	btree *lr[2];//Nice way to handle symmetric cases
	btree (int info) {
		data = info;
		lr[0] = lr[1] = NULL;
	}
};

class binarySearchTree{

public:
	btree *root;
	binarySearchTree() :root(NULL) {}
	void insert(int);
};


This allows you to check if the root node is NULL or not. Then you can answer the question:

keskiverto wrote:
What is the state of the tree before insert is called?


Insert is then implemented as:

1
2
3
4
5
6
7
8
9
void binarySearchTree::insert(int info) {
	btree *temp = root;
	int dir;
	while ( temp != NULL ) {
		dir = temp->data < info;
		temp = temp->lr[dir];
	}
	temp = new btree(info);
}


Have a look here:
http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_bst1.aspx
Last edited on
ok nice
thanks
Topic archived. No new replies allowed.