trees

Introduction
Definition

Representation of Trees

Binary Trees

Binary Tree Traversal and Tree Iterators

Additional Binary Tree Operations

Threaded Binary Trees

Binary Search Trees

   Binary Search Tree (BST)

·     BST

Selection Trees.

Definition of Trees:

A tree is a data structure that is made of nodes and

pointers, much like a linked list. The difference

between them lies in how they are organized:

• The top node in the tree is called the root and all

other nodes branch off from this one.

4

• Every node in the tree can have some number of

children. Each child node can in turn be the parent

node to its children and so on.

• Child nodes can have links only from a single

parent.

• Any node higher up than the parent is called an

ancestor node.

• Nodes having no children are called leaves.

• Any node which is neither a root, nor a leaf is

called an interior node.

• The height of a tree is defined to be the length of

the longest path from the root to a leaf in that tree

( including the path to root)

• A common example of a tree structure is the binary

tree.

//Tree Traversal Techniques: using recursive functions
#include<iostream.h>
#include<conio.h>
#include<process.h>
struct tree_node
{
tree_node *left;
tree_node *right;
int data;
} ;
class bst
{
tree_node *root;
public:
bst()
{
root=NULL;
}
int isempty()
{
return(root==NULL);
}
void insert(int item);
void inordertrav();
void inorder(tree_node *);
void postordertrav();
void postorder(tree_node *);
void preordertrav();
void preorder(tree_node *);
};
void bst::insert(int item)
{
tree_node *p=new tree_node;
tree_node *parent;
p->data=item;
p->left=NULL;
p->right=NULL;
parent=NULL;
if(isempty())
root=p;
else
{
tree_node *ptr;
ptr=root;
while(ptr!=NULL)
{
parent=ptr;
if(item>ptr->data)
ptr=ptr->right;
else
ptr=ptr->left;
}
if(item<parent->data)
parent->left=p;
else
parent->right=p;
}
}
void bst::inordertrav()
{
inorder(root);
}
void bst::inorder(tree_node *ptr)
{
if(ptr!=NULL)
{
inorder(ptr->left);
cout<<" "<<ptr->data<<" ";
inorder(ptr->right);
}
}
void bst::postordertrav()
{
postorder(root);
}
void bst::postorder(tree_node *ptr)
{
if(ptr!=NULL)
{
postorder(ptr->left);
postorder(ptr->right);
cout<<" "<<ptr->data<<" ";
}
}
void bst::preordertrav()
{
preorder(root);
}
void bst::preorder(tree_node *ptr)
{
if(ptr!=NULL)
{
cout<<" "<<ptr->data<<" ";
preorder(ptr->left);
preorder(ptr->right);
}
}
void main()
{
bst b;
b.insert(52);
b.insert(25);
b.insert(50);
b.insert(15);
b.insert(40);
b.insert(45);
b.insert(20); cout<<"inorder"<<endl;
b.inordertrav();
cout<<endl<<"postorder"<<endl;
b.postordertrav();
cout<<endl<<"preorder"<<endl;
b.preordertrav();
getch();
}
//Tree Traversal Techniques: using non recursive functions

#include<stdio.h>                          // including headerfiles
#include<conio.h>
#include<stdlib.h>
struct tree                                        //creating structure
{
int data;                         //data field of node
struct tree *lchild,*rchild;               //left child & right child of node
};
struct tree *insert(struct tree *p,int n);     //function for insertion
void inorder(struct tree *p);                      //function for inorder traversal
void preorder(struct tree *p);                   // function for preorder traversal
void postorder(struct tree *p);                  // function for postorder traversal
void main()                      //main function
{
int x,y,i;                                  
struct tree *root;
clrscr();
root=NULL;
printf("Enter the no. of nodes in the tree\n");
scanf("%d",&x);
while(x-->0)
{
printf("Enter the data part of the node\n");
scanf("%d",&y);
root=traverse(root,y);
}
clrscr();
printf("\t\tEnter the traversal u want\n");
printf("1.Inorder.\n2.Preorder.\n3.Postorder.\n");
scanf("%d",&i);
switch(i)
{
case 1:
{
printf("The inorder traversal is \n");
inorder(root);                        //function calling
}
break;
case 2:
{
printf("The preorder traversal is\n");
preorder(root);                           //function calling
}
break;
case 3:
{
printf("The postorder traversal is\n");
postorder(root);                            // function calling
}
break;
}
getch();
}

//function definition for insertion
struct tree *traverse(struct tree *p,int n)            
{
static struct tree *temp1,*temp2;
if(p==NULL)
{
p=(struct tree *)malloc(sizeof(struct tree));
p->data=n;
p->lchild=p->rchild=NULL;
}
else
{
temp1=p;
while(temp1!=NULL)
{
temp2=temp1;
if(n<temp1->data)
temp1=temp1->lchild;
else
temp1=temp1->rchild;
}
if(temp2->data>n)
{
temp2->lchild=(struct tree *)malloc(sizeof(struct tree));
temp2=temp2->lchild;
temp2->data=n;
temp2->lchild=temp2->rchild=NULL;
}
else
{
temp2->rchild=(struct tree *)malloc(sizeof(struct tree));
temp2=temp2->rchild;
temp2->data=n;
temp2->lchild=temp2->rchild=NULL;
}
}
return p;
}
//function definition for inorder traversal

void inorder(struct tree *p)
{
if(p!=NULL)
{
inorder(p->lchild);
printf("%d ",p->data);
inorder(p->rchild);
}
}

//function definition for preorder traversal
void preorder(struct tree *p)
{
if(p!=NULL)
{
printf("%d ",p->data);
preorder(p->lchild);
preorder(p->rchild);
}
}

//function definition for postorder traversal
void postorder(struct tree *p)
{
if(p!=NULL)
{
postorder(p->lchild);
postorder(p->rchild);
printf("%d ",p->data);
}
}



/*example 2:*/

/*traversing of tree*/
#include<stdio.h>
#include<conio.h>
#include<process.h>
#include<iostream.h>
struct rec
{
long num;
struct rec *left;
struct rec *right;
};
struct rec *tree=NULL;

class createtree{
int count;
public: int select();
struct rec *insert(struct rec *,long);
void preorder(struct rec *);
void inorder(struct rec *);
void postorder(struct rec *);
createtree()
{
int count=1;
}
};

void main()
{
int choice;
createtree tr;
long digit;
clrscr();
do
{
  choice=tr.select();
  switch(choice)
     {
case 1: cout<<"Enter integer: To quit enter 0"<<endl;
cin>>digit;
while(digit!=0)
   {
tree=tr.insert(tree,digit);
cin>>digit;
   }continue;
case 2: cout<<"preorder traversing TREE";
tr.preorder(tree);continue;
case 3: cout<<"inorder traversing TREE";
tr.inorder(tree);continue;
case 4: cout<<"postorder traversing TREE";
tr.postorder(tree);continue;
case 5: cout<<"END";
exit(0);
}
}while(choice!=5);
}

int createtree::select()
{
int selection;
do
 {
cout<<endl<<"Enter 1: Insert a node in the BT";
cout<<endl<<"Enter 2: Display(preorder)the BT";
cout<<endl<<"Enter 3: Display(inorder)the BT";
cout<<endl<<"Enter 4: Display(postorder)the BT";
cout<<endl<<"Enter 5: END";
cout<<endl<<"Enter your choice ";
cin>>selection;
    if((selection<1)||(selection>5))
{
 cout<<"wrong choice:Try again";
 getch();
  }
  }while((selection<1)||(selection>5));
  return (selection);
}

struct rec * createtree::insert(struct rec *tree,long digit)
{
if(tree==NULL)
 {
tree=new(struct rec);
tree->left=tree->right=NULL;
tree->num=digit;
count++;
 }
else
if(count%2==0)
tree->left=insert(tree->left,digit);
else
tree->right=insert(tree->right,digit);
return(tree);
}

void createtree::preorder(struct rec *tree)
{
if(tree!=NULL)
 {
cout<<endl<<tree->num;
preorder(tree->left);
preorder(tree->right);
 }
}

void createtree::inorder(struct rec *tree)
{
if(tree!=NULL)
   {
inorder(tree->left);
cout<<endl<<tree->num;
inorder(tree->right);
   }
}

void createtree::postorder(struct rec *tree)
{
if(tree!=NULL)
 {
postorder(tree->left);
postorder(tree->right);
cout<<endl<<tree->num;
 }

}

The output of the above program is:-

Enter 1: Insert a node in the BT
Enter 2: Display(preorder)the BT
Enter 3: Display(inorder)the BT
Enter 4: Display(postorder)the BT
Enter 5: END
Enter your choice 1
Enter integer: To quit enter 0
82
77
90
346
35
0

Enter 1: Insert a node in the BT
Enter 2: Display(preorder)the BT
Enter 3: Display(inorder)the BT
Enter 4: Display(postorder)the BT
Enter 5: END
Enter your choice 2
preorder traversing TREE
82
77
346
90
35
Enter 1: Insert a node in the BT
Enter 2: Display(preorder)the BT
Enter 3: Display(inorder)the BT
Enter 4: Display(postorder)the BT
Enter 5: END
Enter your choice 3
inorder traversing TREE
346
77
82
90
35
Enter 1: Insert a node in the BT
Enter 2: Display(preorder)the BT
Enter 3: Display(inorder)the BT
Enter 4: Display(postorder)the BT
Enter 5: END
Enter your choice 4
postorder traversing TREE
346
77
35
90
82
Enter 1: Insert a node in the BT
Enter 2: Display(preorder)the BT
Enter 3: Display(inorder)the BT
Enter 4: Display(postorder)the BT
Enter 5: END
Enter your choice 5

You may like the following posts:

C language Tree