Sign in to follow this  
Edzio

how to insert into binary tree and preserve subtrees

Recommended Posts

I am trying to insert a new node into a binary tree while retaining any subtree below the insertion point. The following code inserts a new node at the current cursor but any subtree is overwritten. Any help would be great...
template <class Item>
       void expression<Item>::insert_right(const char op, const Item& entry)
	{
		exp_tree_node<Item>* temp_ptr;
		if(root_ptr == NULL)
		{
			root_ptr = new exp_tree_node<Item>(op, NULL, NULL);
			root_ptr->set_right(new exp_tree_node<Item>(entry) );
			precursor = root_ptr;
			cursor = root_ptr;
		}
		else
		{
			if(cursor->right() == NULL && cursor->left() == NULL)
			{
				cursor->set_right(new exp_tree_node<Item>(op, NULL, NULL) );
				cursor->set_op(op);
				cursor->set_right(new exp_tree_node<Item>(entry) );
			}
			else
			{
				cursor->set_right(new exp_tree_node<Item>(entry) );
			}
			
		}
		
	}

thanks for any tips on how to do this :)

Share this post


Link to post
Share on other sites
You need to save whatever is currently on the right subnode. So you can do something like:


exp_tree_node temp = cursor->right;
cursor->set_right();

if temp > than cursor->right
cursor->right->set_right(temp);

else
cursor->right->set_left(temp);


However, if you're using a binary search tree, then you shouldn't run into this problem. You should just traverse the tree based on the value of the node your're inserting, and you will always end up at a null node (that is if the values are distinct).

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this