A Question About inserting node in a regular Binary Tree

Hi All,

I was trying to edit a code so that it could insert nodes into a binary tree. Every time the user inserts, there will prompt a line asking to insert to the left child or the right child. Could anyone show me what's wrong with my code(you can see to the insert func)? It doesn't yield the correct result.

Thanks in advance.

#include<iostream>
//#include<stdio>
// #include<stdlib>
using std::cin;
using std::cout;
using std::endl;
struct node
{
int data;
node *left;
node *right;
};

node *tree=NULL;
node *insert(node *tree,int ele);

void preorder(node *tree);
void inorder(node *tree);
void postorder(node *tree);
int count=1;

int main()
{
//clrscr();
int ch,ele;
do
{
//clrscr();
cout<<"\n\t\a\a1----INSERT A NODE IN A BINARY TREE.\a\a";
cout<<"\n\t\a\a2----PRE-ORDER TRAVERSAL.\a\a";
cout<<"\n\t\a\a3----IN-ORDER TRAVERSAL.\a\a";
cout<<"\n\t\a\a4----POST-ORDER TRAVERSAL.\a\a";
cout<<"\n\t\a\a5----EXIT.\a\a";
cout<<"\n\t\a\aENTER CHOICE::\a\a";
cin>>ch;
switch(ch)
{
case 1:
cout<<"\n\t\a\aENTER THE ELEMENT::\a\a";
cin>>ele;
tree=insert(tree,ele);
break;

case 2:
cout<<"\n\t\a\a****PRE-ORDER TRAVERSAL OF A TREE****\a\a";
preorder(tree);
break;

case 3:
cout<<"\n\t\a\a****IN-ORDER TRAVERSAL OF A TREE****\a\a";
inorder(tree);
break;

case 4:
cout<<"\n\t\a\a****POST-ORDER TRAVERSAL OF A TREE****\a\a";
postorder(tree);
break;

case 5:
break;
}
}while(ch!=5);
return 0;
}

node *insert(node *tree,int ele)
{
char ch;
if(tree==NULL)
{
tree=new node;
tree->left=NULL;
tree->right=NULL;
tree->data=ele;
count++;

}
else{
cout<<"Insert to Left or Right?"<<endl;
cin>>ch;
if(ch=='L'||'l')
tree->left=insert(tree->left,ele);
if(ch=='R'||'r')
tree->right=insert(tree->right,ele);
}
return(tree);
}

void preorder(node *tree)
{
if(tree!=NULL)
{
cout<<tree->data;
preorder(tree->left);
preorder(tree->right);
//cin.get();
}
}

void inorder(node *tree)
{
if(tree!=NULL)
{
inorder(tree->left);
cout<<tree->data;
inorder(tree->right);
//cin.get();
}
}

void postorder(node *tree)
{
if(tree!=NULL)
{
postorder(tree->left);
postorder(tree->right);
cout<<tree->data;
//cin.get();
}
}

Re: A Question About inserting node in a regular Binary Tree

In the Insert function change the conditional expression to

if (ch == 'L' || ch == 'l')
and
if (ch == 'R' || ch == 'r')

Re: A Question About inserting node in a regular Binary Tree

You better put your code between [ c o d e ] [ / c o d e] tags (no spaces) so that you don't loose indentation.

Code:

#include<iostream> //#include<stdio> // #include<stdlib> using std::cin; using std::cout; using std::endl; struct node { int data; node *left; node *right; }; node *tree=NULL; node *insert(node *tree,int ele); void preorder(node *tree); void inorder(node *tree); void postorder(node *tree); int count=1; int main() { //clrscr(); int ch,ele; do { //clrscr(); cout<<"\n\t\a\a1----INSERT A NODE IN A BINARY TREE.\a\a"; cout<<"\n\t\a\a2----PRE-ORDER TRAVERSAL.\a\a"; cout<<"\n\t\a\a3----IN-ORDER TRAVERSAL.\a\a"; cout<<"\n\t\a\a4----POST-ORDER TRAVERSAL.\a\a"; cout<<"\n\t\a\a5----EXIT.\a\a"; cout<<"\n\t\a\aENTER CHOICE::\a\a"; cin>>ch; switch(ch) { case 1: cout<<"\n\t\a\aENTER THE ELEMENT::\a\a"; cin>>ele; tree=insert(tree,ele); break; case 2: cout<<"\n\t\a\a****PRE-ORDER TRAVERSAL OF A TREE****\a\a"; preorder(tree); break; case 3: cout<<"\n\t\a\a****IN-ORDER TRAVERSAL OF A TREE****\a\a"; inorder(tree); break; case 4: cout<<"\n\t\a\a****POST-ORDER TRAVERSAL OF A TREE****\a\a"; postorder(tree); break; case 5: break; } }while(ch!=5); return 0; } node *insert(node *tree,int ele) { char ch; if(tree==NULL) { tree=new node; tree->left=NULL; tree->right=NULL; tree->data=ele; count++; } else{ cout<<"Insert to Left or Right?"<<endl; cin>>ch; if(ch=='L'|| ch=='l') tree->left=insert(tree->left,ele); if(ch=='R'|| ch=='r') tree->right=insert(tree->right,ele); } return(tree); } void preorder(node *tree) { if(tree!=NULL) { cout<<tree->data; preorder(tree->left); preorder(tree->right); //cin.get(); } } void inorder(node *tree) { if(tree!=NULL) { inorder(tree->left); cout<<tree->data; inorder(tree->right); //cin.get(); } } void postorder(node *tree) { if(tree!=NULL) { postorder(tree->left); postorder(tree->right); cout<<tree->data; //cin.get(); } }

I wouldn't ask the user in the insert function whether to go left or right. Instead, I would check the input value whether it is greater or less than the value of the current node and then go down accordingly.

You also should avoid statements like

Code:

tree=insert(tree,ele);

cause that could destroy the (only) root pointer you have in your main function. You are lucky that your insert function doesn't change the tree argument so that the statement doesn't any harm and even helps you to initialize the tree pointer at first call.

The correct way with your current tree implementation would be

Code:

Node * pNode = insert(tree, ele); if (tree == NULL) tree = pNode;

Though that may look a little clumsy, it avoids to make assumptions on a function 'insert' where the 'normal' return would be the new Node inserted and not the Node passed as argument.

A probably better approach is to change the argument type of the tree argument to Node*&. That way the tree was 'returned' correctly when it was initialized and used for input only for the normal case where the tree already exists.

The code in the main would change to:

Code:

insert(tree, ele);

All the problems with passing Nodes to the public interface of your tree you could avoid by adding a Tree class which holds the root pointer as a private member:

Code:

class Tree { Node * root; node * insert(node *& tree,int ele); void preorder(node * tree); void inorder(node * tree); void postorder(node * tree); public: Tree() : root(NULL) {} void insert(int ele); void preorder(); void inorder(); void postorder(); };

In main you only create an empty Tree and call the public functions while those were calling the private functions using the private root pointer.

Re: A Question About inserting node in a regular Binary Tree

Thanks a lot itsmeandnobodyelse, you are of great help!