Insert an item into a binary tree

Question

I tried a lot to sort through the network, but could get any help. Everywhere it looks like adding a node to the binary search tree.

Question: querying the algorithm and code snippet to add node to the binary tree . (or give me the correct URL)

Assumption: In my understanding, is the binary tree and the binary search tree different? Correct me if I am wrong.

(query: if you are writing a piece of code, use the correct variable name, which helps in understanding)

For example: Binary Tree

5 7 3 x 1 x 2 x 3

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 ); } } 

Answer 1

The difference between the binary tree and the binary search tree is that, although they both have limitations that each node can have no more than 2 child nodes, the binary search tree (BST) must also have its left child equal to or less than, and its the right child should have greater or equal value. This is why it is called the Search tree, because everything is numerically ordered and it has an O (logn) runtime to search.

Since there is no requirement to be BST, the binary tree can be stored in a vector (array). When you insert into a vector, you are building a binary tree in level order. Code below:

 // typedef the node struct to NODE // nodeVector similar to STL 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 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; } } } 

Answer 2

The queue data structure can be used to insert an element into the binary tree, since the order of the nodes in the binary tree is not supported, so we will insert the node as soon as we find zero. Using Queue, we will move through the binary tree, bypassing the order.

 struct Treenode* temp; Q = CreateQueue(); EnQueue(Q,root); while(!IsEmptyQueue(Q)) { temp = DeQueue(Q); if(temp->left) EnQueue(Q,temp->left); else { temp->left=newNode; DeleteQueue(Q); return; } if(temp->right) EnQueue(Q,temp->right); else { temp->right=newNode; DeleteQueue(Q); return; } } 

Answer 3

Since I cannot comment, I am writing this.
The above answer for the binary tree insert function is incorrect.
Suppose that for 0, 1, 2, 3, 4, 5 are passed sequentially to insert functions,
its generation tree for example

  0 / 1 \ 2 / 3 \ 4 / 5`<br/> 

of which the bypass order will be 1 3 5 4 2 0
while the answer should be

  0 / \ 1 2 / \ / 3 4 5 

of which the round trip will be 3 1 4 0 5 2.

Answer 4

Since I also encounter the same problem, I came up with the following solution over the network: -

You can use the queue to store the current node, where we want to place the new node, as well as bypassing the level, and then insert the level of nodes by level.

The following link may help you: -

http://www.geeksforgeeks.org/linked-complete-binary-tree-its-creation/

Answer 5

I am posting this as an answer because I do not have the necessary reputation to post a comment. With the exception of the donut, everyone else misunderstood the tree as a binary search tree or a complete binary tree. The question is simple. The answer of the binary tree and Bagelboy looks correct.