C plus plus program to insert an element using binary tree?

Answer 1

The algorithm for inserting into a binary tree is fairly straightforward. Start by passing the element to the root node of the tree. If there is no root, the new element becomes the root and you're done. Whenever a node receives a new element, it compares the element's value with its own value. If the new element is lower in value, pass the element to the left node otherwise pass it to the right node. If there is no node in that position, the new element becomes that node. In this way, the node's themselves decide where new elements are placed.

In order to achieve this you need a node that encapsulates some data. Typically the data is a template parameter but for the sake of simplicity let us assume the data is an unsigned integer. We'll also need pointers to the left and right nodes. We'll use the default constructor to initialise the data and pointers. we'll also need an insertion method. Thus our node class looks like this:

class node

{

private:

node* left;

node* right;

unsigned data;

public:

node(unsigned value): left(NULL), right(NULL), data(value) {}

void insert(unsigned value);

};

The insert method will be implemented as follows:

void node::insert(unsigned value)

{

if (value<data)

{

if (left) left->insert(value); else left = new node(value);

}

else

{

if (right) right->insert(value); else right = new node(value);

}

}

That's all there is to it. All you need now is a pointer to the root which will initially be NULL. When you come to insert a value and the root is NULL, create a new node and assign it to the root pointer, otherwise call root->insert(value); and let the tree sort itself out.