Tried exploring a lot over the net, but could get any help, Everywhere its like adding a node to the Binary Search tree.
Question: Requesting for algorithm and code snippet for adding a node to the Binary tree. ( or point me to correct URL )
Assumption: As per my understanding, Binary Tree and Binary Search Tree is different? Correct me if I am wrong.
( request: if you are writing your code snippet please use proper variable name, that helps in understanding )
Eg: Binary Tree
5 7 3 x1 x2 x3
5
7 3
x1 x2 x3
Binary Search Tree 5 7 3 2 4 6
5
3 7
2 4 6
insert(int key, struct node **root)
{
if( NULL == *root )`
{
*root = (struct node*) malloc( sizeof( struct node ) );`
(*root)->data = key;
(*root)->left = NULL;
(*root)->right = NULL;
}
else if(key < (*root)->data)
{
insert( key, &(*root)->left );
}
else if(key > (*root)->data)
{
insert( key, &(*root)->right );
}
}
Whenever an element is to be inserted, first locate its proper location. Start searching from the root node, then if the data is less than the key value, search for the empty location in the left subtree and insert the data. Otherwise, search for the empty location in the right subtree and insert the data.
To insert into a tree we use the same node class created above and add a insert class to it. The insert class compares the value of the node to the parent node and decides to add it as a left node or a right node. Finally the PrintTree class is used to print the tree.
Inserting into a binary search treeThe actual insertion takes place when a null tree is encountered. The null tree is replaced by a leaf. If the value to be inserted is already in the tree, nothing is done.
The difference between a Binary Tree and a Binary Search Tree is that though they both have restrictions that each node can have at most 2 child nodes, a Binary Search Tree (BST) also must have its left child be of equal or lesser value and the its right child must be of greater or equal value. This is why it is called a "Search" tree because everything is ordered numerically and it has an O(logn) run time for searching.
Because there isn't the requirement of being a BST, a Binary Tree can be stored in a vector (array). As you insert into the vector you build the Binary Tree in level-order fashion. The code is below:
// typedef the node struct to NODE
// nodeVector similar to STL's vector class
insert(int key, NODE** nodeVector)
{
NODE *newNode = (NODE*) malloc( sizeof( NODE ) );
newNode->data = key;
newNode->left = NULL;
newNode->right = NULL;
// add newNode to end of vector
int size = nodeVector->size();
nodeVector->push_back(newNode);
// if newNode is not root node
if(nodeVector->size() > 1)
{
// set parent's child values
Node* parent = (size/2)-1; // take advantage of integer division instead of using floor()
if (parent->left == NULL)
{
parent->left = newNode;
}
else
{
parent->right = newNode;
}
}
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With