Is it possible to add nodes into a binary tree in order of increasing value, level by level?
For example:
1
2 3
4 56 7
BinaryTree Question
Author
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.
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)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); }
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:
The simplest way is to build any binary tree ignoring the order. Then apply heap sort.
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: indexnode->parent: index/2node->left: 2*indexnode->right: 2*index+1The simplest way is to build any binary tree ignoring the order. Then apply heap sort.
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.
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);This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
