Sign in to follow this  

BinaryTree Question

This topic is 2635 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am using a basic binary tree and am adding node values in order 1,2,3... I can get the first 3 values in the right place but the rest just keep adding to the left sub trees.

void Insert(Node *&nodePtr, Node *&newNode)
if(nodePtr == NULL)
nodePtr = newNode;
else
{
if(nodePtr->left == NULL)
Insert(nodePtr->left,newNode);
else
if(nodePtr->right == NULL)
Insert(nodePtr->right,newNode);
else
Insert(nodePtr->left,newNode);
}




I also tried using parent nodes but that is getting to complicated to follow. Is there a better solution using a binary tree?

void Insert(Node *&nodePtr, Node *&newNode, Node *&parentNode)
{
if(nodePtr == NULL)
{
nodePtr = newNode;
nodePtr->parent = parentNode;
}
else
{
if(nodePtr->left == NULL)
Insert(nodePtr->left,newNode,nodePtr);
else
if(nodePtr->right == NULL)
Insert(nodePtr->right,newNode,nodePtr);
else
Insert(nodePtr->left,newNode,nodePtr);
}


Share this post


Link to post
Share on other sites
There is quite some theory behind it. This type of tree is called a heap. This alone is not enough.

To get items sorted by level one needs to sort a heap - aka Heap Sort.

The only complication is that heap sort prefers to work on arrays. To implement those over this type of nodes, the tree traversal needs to be adjusted. The following are equivalent:
node:   index
node->parent: index/2
node->left: 2*index
node->right: 2*index+1


The simplest way is to build any binary tree ignoring the order. Then apply heap sort.

Share this post


Link to post
Share on other sites
One of the interesting properties of a binary tree filled with consecutive numbers like that is that the binary representation of the values tell you how to get to the node that contains the value. Take the number 4; it's binary representation is 100. It likes on the third level because it's most significant bit is in the third position. In order to get to its node you take two left paths because the representation is 00. The number 5's representation is 101. It too is on the third level and to get to it's node you go left then right. 0 for the left and 1 for the right. The number 6's representation is 110. To get to it you go right then left. 7 is 111 so you go right twice.

Share this post


Link to post
Share on other sites
Well, for strictly consecutive it's also possible to be a bit clever:

Node * add(int curr, int max) {
if (curr > max) return NULL;
Node * n = new Node();
n->value = curr;
n->left = add(2*curr, max);
n->right = add(2*curr+1, max);
return n;
};

Node * root = add(1, 7);

Share this post


Link to post
Share on other sites

This topic is 2635 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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