C++/Question

Advertisement


Question
A_O_A
     Sir tell me the Concept of Tree.Please explain with the help of an example.And also in what application we use the tree.

         Your,
         Imran Ahmad Mughal

Answer
Hello Imran.

A tree is a data structure, where in using one node, you can access one or more than one nodes.In a stack,each node is linked to only the next node.That is,if you are at a node 3,you can only go to node 4, and so on.In a tree,you can go to many nodes. A tree looks like an inverted garden tree, with root node at the top,and branches from that root note leading to other nodes.Each node further is linked to some more nodes.
Trees are used in gaming applications(so that the computer can decide its next move.The root node here is the start of the game, and each node is the possible moves it can make from a given situation).Trees can be used for huffman compression algorithms, for conversion of expressions from infix to postfix to prefix etc. These are only som of the uses.
Here is a program for a simple binary tree.A binary tree has certain rules:
1.Each node can have only two or less than two child nodes,a left node and a right node.for example, if node A is the root node,it is linked to nodes B(left node) and C(right node). B is again connected to D(left node) and E(right node). C is connected only to F.

2.Left node is smaller in value to the root node and right node is greater.Thus B<A and C>A. D<B and E>B. If F<E,we call F the left node otherwise the right node. Here is the program:

//**********************************************************//
//Program to create a binary tree and perform          inorder,preorder and postorder traversal.
//
//**********************************************************

# include<iostream.h>
# include<conio.h>
class node
{
private:
 int data;
 node*left;
 node*right;
public:
 int maketree();
 void inorder(node*);
 void preorder(node*);
 void postorder(node*);

};
node*root=NULL;
int node:: maketree()
{
 node*temp;
 int dat;
 node*ptr,*prev;
 cout<<"Enter node : ";
 cin>>dat;
 if(dat!=-1){
 temp=new node;
 temp->data=dat;
 temp->left=temp->right=NULL;

 if(root==NULL)
     root=temp;
 else
  {
  ptr=root;
  while(ptr!=NULL)
     {
      prev=ptr;
      if(dat<ptr->data)
    ptr=ptr->left;
      else
    ptr=ptr->right;
     }
 if(dat<prev->data)
    prev->left=temp;
 else
   prev->right=temp;
 }
}
return dat;
}

void node::inorder(node*ptr)
{
if(ptr!=NULL)
{
 inorder(ptr->left);
 cout<<ptr->data<<"  ";
 inorder(ptr->right);
}
}

void node::preorder(node*ptr)
{
if(ptr!=NULL)
{
 cout<<ptr->data<<"  ";
 preorder(ptr->left);
 preorder(ptr->right);
}
}
void node::postorder(node*ptr)
{
if(ptr!=NULL)
{
 postorder(ptr->left);
 postorder(ptr->right);
 cout<<ptr->data<<"  ";
}
}

void main()
{
clrscr();
node one;
node*rot;

cout<<"Enter -1 to terminate input: \n";
while(one.maketree()!=-1);
rot=root;
cout<<"\n\2INORDER TRAVERSAL\2  ";
one.inorder(rot);
cout<<"\n\2PREORDER TRAVERSAL\2  ";
one.preorder(rot);
cout<<"\n\2POSTORDER TRAVERSAL\2  ";
one.postorder(rot);
getch();
}

There are three kinds of traversals of a binary tree.
1.Inorder: visit left node,print the data and then visit right node.
2.Preorder:Print the data,visit left node,visit right node;
3.Postorder:visit left node,visit right node,print the data.

All these 3 methods use recursion.
Look at the program carefully.Do a dry run and you will understand how it works.

Bi
Samarth

C++

All Answers


Answers by Expert:


Ask Experts

Volunteer


Samarth Bartaria

Expertise

I can answer questions about pointers behaviour, their implementations and anamolous behaviour.Also, I speciallize in object oriented design and modelling,polymorphism in C++ and algorithm efficiency. Even questions related to database design,or simple basics about programming are welcome.

Experience

I have been using C++ for five years now for software development and scientific analyses.

Organizations
Currently, I am a student doing my computer engineering.

©2016 About.com. All rights reserved.