You cannot copy content of this page.

Tag Archive Tree

Trees



Trees

Definitions:

Binary Tree:  A binary tree is either empty or it consists of a node called the root together with two binary trees called the left subtree and the right subtree of the root.

Node:  Each element of a binary tree is called a node of a tree.

Father:  If A is the root of the binary tree and B is the root of its left or right subtree, then A is said to be the father of B and B is said to be the left or right son of A.

Child:  A node is a child node if it originates from a parent node.

Leaf:  A node that has no sons is called a leaf.  A leaf node is also called external node.

Internal Node:  The nodes, which have child nodes are called internal or interior nodes.

External Path Length:  The external path length of a binary tree is the sum of all the levels of all the external nodes of its extension.

Internal Path Length:  The internal path length of a binary tree is the sum of all the levels of all the internal nodes of its extension.

Ancestor:  Node n1 is an ancestor of node n2, if n1 is either the father of n2 or the father of some ancestor of n2.

Descendant:  Node n2 is a descendant of n1, if n2 is the left or right son or exists at any other lower level than n1.

Left Descendant:  A node n2 is a left descendant of node n1 if n2 is either the left son of n1 or a descendant of the left son of n1.

Right Descendant:  A node n2 is a right descendant of node n1 if n2 is either the right son of n1 or a descendant of the right son of n1.



Strictly Binary Tree:  If every non-leaf node in a binary tree has non-empty left and right subtrees, the tree is termed as Strictly binary tree.  A Strictly binary tree with n leaves always contains (2n-1) nodes.

Level of a node:

The root of the tree has level 0 and the level of any other node in the tree is one more than the level of its father.  Example: In the following tree, the level of G is 3, of D is 2 and of root, A is 0.

Depth of  a Tree:

The depth of a binary tree is the maximum level of any leaf in the tree.  This equals the length of the longest path from the root to any leaf.  Thus the depth of the above binary tree is 3.

Complete Binary Tree:

A Complete binary tree of depth d is the Strictly binary tree of all of whose leaves are at level d (eg. if depth is 2), the complete binary tree is:

NOTE:

1.  If a binary tree contains M nodes at level l, it contains at most 2m nodes at level l+1.

Example:  Let at level 1, number of nodes, m=2, then at level l+1 i.e. 1+1=2, nodes=2m=2*2=4.

2.  Since a binary tree can contain atmost one node at level 0 (the root), it can contain atmost one node 2L nodes at level L i.e. if level l is 3, then number of nodes = 2L =2 3 =8.  Thus at the most 8 nodes can be kept at level 3 in a CBT.

3.  A complete binary tree of depth d is the binary tree of depth d, that contains exactly 2L nodes at each level L, between 0 and d.

Let depth, d=2, L=2 {0,1,2}; nodes = {20,21,22} i.e. {1,2,4}.





Almost Complete Binary Tree:

A Binary tree of depth d is an almost complete binary tree, if:

  1. Any node nd at level less than (d-1) has two sons.
  2. For any node nd in the tree, with a right descendant at level d, nd must have a left descendant/son and every left descendant of nd is either a leaf at level d or has two sons.

(Numbering of nodes is done from left to right for the same level).

In the above example, depth =2

1.  node B at level 2-1 = 1 has 2 sons.

2.  At level 1, B has a right as well as a left descendant and C does not have left or right son.  Thus it is an example of an almost complete binary tree.

 

An almost complete strictly binary tree with n leaves has (2n-1) nodes as does any other strictly binary tree with n leaves.

An almost complete binary tree with n leaves that is not strictly binary has 2n nodes.
Binary Search Tree: 

A binary search tree is a binary tree that is either empty or in which each node contains a key that satisfies the conditions:

1.  All keys (if any) in the left subtree of the root precede the key in the root.

2.  The key in the root precedes all keys (if any) in its right subtree.

3.  The left and right subtrees of the root are again search trees.

 

Orchards, Trees and Binary Trees:

Tree:  It is any set of points (called vertices) and any set of pairs of distinct vertices (called edges or branches) such that-

(1) There is a sequence of edges (a path) from any vertex to any other; and

(2) There are no circuits, that is, no paths starting from a vertex and returning to the same vertex.

Such trees may be termed as Free Trees.  But the trees that we study are almost always tied up by having one particular vertex singled out as the root and for emphasis we call such a tree as a Rooted Tree. 

A rooted tree can be drawn in our usual way by picking it up by its root and shaking it so that all the branches and other vertices hand downward with the leaves at the bottom.  But there is no way to order nodes.

An Ordered Tree may be defined to be a rooted tree in which the children of each vertex are assigned an order.

2-Trees are rooted trees with the property that every vertex has either 0 or 2 children.

Forests and Orchards:  A forest is an arbitrary set of trees, where trees are sorted trees.  An orchard set of ordered trees is called forest or orchard.

We can build a rooted or an ordered tree by starting with a forest or an orchard attaching a new vertex at the top and adding branches from the new vertex (which will the the root) to the roots of all trees in the forest or the orchard.

Conversion of General Trees to a Binary Tree: 

To convert a general tree in to a binary tree, begin from root and join the nodes in left to right order for the same level that originate from the same root.  Remove all other links except left links and reconstruct the tree that will be a binary tree as follows:

Example:

Note: Arrow indicator shows the links to created for childs of same nodes at same level from left to right.  A hyphen (-) indicates the links to be deleted.

The binary tree for the above general tree is drawn below:

Conversion of an Orchard/Forest to Binary Tree:

Follow the same rule as applicable for conversion of a general tree to a binary tree.  The second general tree becomes the right child of the root of the first tree and so on.  The resultant tree is binary tree equivalent of a given forest or orchard.

 



Binary Tree Traversals:

Preorder (also known as Depth-first order)

  • Visit the root.
  • Traverse the left subtree in preorder.
  • Traverse the right subtree in preorder.

Inorder (or Symmetric order)

  • Traverse the left subtree in inorder.
  • Visit the root.
  • Traverse the right subtree in inorder.

Postorder (or End order)

  • Traverse the left subtree in postorder.
  • Traverse the right subtree in postorder.
  • Visit the root.

Expression Tree: 

An expression tree is build up from the simple operands and operators of an arithmetical or logical expression by placing the simple operands as the leaves of a binary tree and the operators as the interior nodes.  For each binary operator, the left subtree contains all the simple operands and operators in the left operand of the left operand of the given operator and the right subtree contains everything in the right operand.

For a unary operator, one subtree will be empty.

 



Polish Notations: Traversal of expression trees results in polish forms of expressions-

1. Traversal of an expression tree in preorder yields the prefix form of the expression, in which every operator is written before its operands.

2.  Inorder traversal gives the infix form.

3.  Postorder traversal gives the postfix form, in which all operators appear after their operands.

 

Tree Sort:  Inorder traversal of a tree yields sorted output, if it is a Binary Search Tree.  We may simple take the items to be sorted, build them into a binary search tree and use inorder traversal to put them in order.


Tags,

Threaded Binary Trees

Threaded Binary Trees

Threaded Binary Trees are an improvement over Binary Search Trees that uses stack for iterative traversal.  If a strategy is introduced such that the leaf node of a binary search tree points to its inorder predecessor or its successor, then direct links (called threads) are obtained to traverse a tree without using stack, which basically stores and retrieves the address of nodes in LIFO manner.  If the left pointer of the leaf node points to its inorder predecessor, then such a threaded tree is called Left-In-Threaded Binary Tree.  If the right pointer of the leaf node points to its inorder successor, then such a threaded tree is referred to as Right-In-Threaded Binary Tree. However, if both the links, left as well as right are available, then the threaded tree is called In-Threaded Binary Tree.

Threads are links or pointers that points to some node as per the sequence in inorder traversal (predecessor or successor).  It is required to differentiate a link from that of a thread, we may assume to integers lflag and rflag, which may take the value of 1 or 0.  If the value of lflag is 1 then it refers that the node contains a left thread, otherwise it is a link to the left subtree.  Moreover, leftmost pointer in an In-Threaded Binary Tree always points to NULL since no inorder  predecessor for the leftmost node is available.  This thread is referred to as dangling left thread.  Similar is the case with rightmost node, for which no inorder successor is available, and the thread so formed is called dangling right thread.

Function for Inorder Traversal of an In-Threaded Binary Tree: 

The basic advantage of Threaded Tree is that its inorder traversal does not require the use of stack.  Inorder traversal requires visiting the leftmost node, and then using right threads for the purpose of traversal.  The ‘C’ function for inorder traversal is given below:

/*Traverse in Inorder*/
void traverseInorder(tbt *root)
{tbt *temp=root;
while(temp->left)
temp=temp->left;
while(temp!=NULL)
{printf(“%dt”,temp->info);
if(temp->rflag==0)
{temp=temp->right;
while(temp->lflag==0)
temp=temp->left;
}
else
{temp=temp->right;
}
}
}

Function to insert a new node in In-Threaded Tree: 

Insertion of a new node in a Threaded tree is quite similar to that of insertion in a Binary Search Tree with the only difference that at each insertion step, the inorder predecessor and inorder successor of the new node must be set accordingly and the root of newnode must be set to bear a subtree rather than a thread.  The ‘C’ function to insert a new node in a Threaded Binary Tree is given below:

/*Insert a newnode in the threaded tree*/
tbt *insert(tbt *root,tbt *newnode)
{
tbt *p,*temp=root;
if(root==NULL)
{root=newnode;
return root;
}
while(temp!=NULL)
{
if(newnode->info<temp->info)
{
if(temp->left)
{if(temp->lflag==1)
{
newnode->left=temp->left;
newnode->right=temp;
temp->left=newnode;
temp->lflag=0;
break;
}
else
temp=temp->left;
}
else
{newnode->left=temp->left;
temp->left=newnode;
temp->lflag=0;
newnode->right=temp;
break;
}
}
else
{if(temp->right)
{if(temp->rflag==1)
{newnode->right=temp->right;
newnode->left=temp;
temp->right=newnode;
temp->rflag=0;
newnode->rflag=1;
break;
}
else
{temp=temp->right;
}
}
else
{
p=temp->right;
temp->right=newnode;
temp->rflag=0;
newnode->right=p;
newnode->left=temp;
break;
}
}
}
return root;
}

Function to find the Inorder Predecessor of a given node in an In-Threaded Binary Tree:  

Searching and returning inorder predecessor requires comparing each node with the value whose predecessor is required.  If the value is not found in the tree, error is reported.  If the value is found, then a temp pointer is placed on the left of this node and shifted until it points the rightmost node.  The value of the rightmost node is returned.  The ‘C’ function for returning Inorder predecessor of a given node is as follows:

/*Function that returns inorder predecessor*/
int inorderPredecessor(tbt *root,tbt *node)
{
int num;
tbt *p,*temp=root;
while(temp!=NULL)
{
if(node->info<temp->info)
{
if(temp->lflag==0)
temp=temp->left;
else /*move from left to right*/
temp=temp->right;
}
else if(node->info>temp->info)
{if(temp->rflag==0)
temp=temp->right;
else
{printf(“nGiven node does not exist.”);
return -1;
}
}
else/*if value is found*/
{if(temp->lflag==0)
{p=temp->left;
while(p->rflag!=1)
p=p->right;
num=p->info;/*predecssor*/
break;
}
else
{if(temp->left==NULL)
{num=0;
break;
}
else
{num=temp->left->info;
break;
}
}
}
}
return num;
}

Function to find the Inorder Successor of a given node in an In-Threaded Binary Tree: 

Searching and returning inorder successor requires comparing each node with the value whose successor is required.  If the value is not found in the tree, error is reported.  If the value is found, then a temp pointer is placed on the right of this node and shifted until it points the leftmost node.  The value of the leftmost node is returned.  The ‘C’ function for returning Inorder Successor of a given node is as follows:

/*Function that returns Inorder successor*/
int inorderSuccessor(tbt *root,tbt *node)
{int num;
tbt *p,*temp=root;
while(temp!=NULL)
{
if(node->info<temp->info)
{if(temp->lflag==0)
temp=temp->left;
else
temp=temp->right;
}
else if(node->info>temp->info)
{
if(temp->rflag==0)
temp=temp->right;
else
{printf(“nGiven node does not exist.”);
return -1;
}
}
else/*node->info==temp->info*/
{
if(temp->rflag==0)
{
p=temp->right;
while(p->lflag!=1)
p=p->left;
num=p->info;/*successor*/
break;
}
else
{
if(temp->right==NULL)
{num=0;
break;
}
else
{num=temp->right->info;
break;
}
}
}
}
return num;
}

Function to traverse a Left-In-Threaded Tree in Descending Order: 

Traversal of a Left In Threaded Tree result in a descending order of elements.  If the inorder traversal gives the result in Ascending order, then traversal using left threads may be performed such that the result is achieved in descending order.  The ‘C’ function for the same is as follows:

void traverseDescending(TBT *root)
{
TBT *p,*temp=root;
p=root;
while(temp!=NULL)
{while(p!=NULL)
{temp=p;
p=p->right;
}
printf(“%dt”,temp->info);
if((temp->lflag==1) && (temp->left==NULL))
return;
if(temp->lflag==1)
temp=temp->left;
else
p=temp->left;
}
}

 

Tags, ,

Program to implement In-Threaded Binary Tree

In-Threaded-Binary Tree

Program to implement In-Threaded Binary Tree:

/*In-threaded Binary Tree*/
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

typedef struct threadedbinarytree
{
int info;
struct threadedbinarytree *left,*right;
int lflag,rflag;
}tbt;

tbt *create();
tbt *makenode(int);
tbt *insert(tbt *,tbt *);
int inorderSuccessor(tbt *,tbt *);
int inorderPredecessor(tbt *,tbt *);
void traverseInorder(tbt *);

/*Allocate memory*/
tbt *create()
{
tbt *temp=(tbt *)malloc(sizeof(tbt));
if(temp==NULL)
{printf(“nMemory Allocation Error!”);
exit(1);
}
return temp;
}

/*Make a new node*/
tbt *makenode(int x)
{
tbt *temp=create();
temp->info=x;
temp->left=NULL;
temp->right=NULL;
temp->lflag=1; /*default is thread*/
temp->rflag=1;/*default is thread*/
return temp;
}

/*Insert a newnode in the threaded tree*/
tbt *insert(tbt *root,tbt *newnode)
{
tbt *p,*temp=root;
if(root==NULL)
{root=newnode;
return root;
}
while(temp!=NULL)
{
if(newnode->info<temp->info)
{
if(temp->left)
{if(temp->lflag==1)
{
newnode->left=temp->left;
newnode->right=temp;
temp->left=newnode;
temp->lflag=0;
break;
}
else
temp=temp->left;
}
else
{newnode->left=temp->left;
temp->left=newnode;
temp->lflag=0;
newnode->right=temp;
break;
}
}
else
{if(temp->right)
{if(temp->rflag==1)
{newnode->right=temp->right;
newnode->left=temp;
temp->right=newnode;
temp->rflag=0;
newnode->rflag=1;
break;
}
else
{temp=temp->right;
}
}
else
{
p=temp->right;
temp->right=newnode;
temp->rflag=0;
newnode->right=p;
newnode->left=temp;
break;
}
}
}
return root;
}

/*Function that returns Inorder successor*/
int inorderSuccessor(tbt *root,tbt *node)
{int num;
tbt *p,*temp=root;
while(temp!=NULL)
{
if(node->info<temp->info)
{if(temp->lflag==0)
temp=temp->left;
else
temp=temp->right;
}
else if(node->info>temp->info)
{
if(temp->rflag==0)
temp=temp->right;
else
{printf(“nGiven node does not exist.”);
return -1;
}
}
else/*node->info==temp->info*/
{
if(temp->rflag==0)
{
p=temp->right;
while(p->lflag!=1)
p=p->left;
num=p->info;/*successor*/
break;
}
else
{
if(temp->right==NULL)
{num=0;
break;
}
else
{num=temp->right->info;
break;
}
}
}
}
return num;
}

/*Function that returns inorder predecessor*/
int inorderPredecessor(tbt *root,tbt *node)
{
int num;
tbt *p,*temp=root;
while(temp!=NULL)
{
if(node->info<temp->info)
{
if(temp->lflag==0)
temp=temp->left;
else /*move from left to right*/
temp=temp->right;
}
else if(node->info>temp->info)
{if(temp->rflag==0)
temp=temp->right;
else
{printf(“nGiven node does not exist.”);
return -1;
}
}
else/*if value is found*/
{if(temp->lflag==0)
{p=temp->left;
while(p->rflag!=1)
p=p->right;
num=p->info;/*predecssor*/
break;
}
else
{if(temp->left==NULL)
{num=0;
break;
}
else
{num=temp->left->info;
break;
}
}
}
}
return num;
}

/*Traverse in Inorder*/
void traverseInorder(tbt *root)
{tbt *temp=root;
while(temp->left)
temp=temp->left;
while(temp!=NULL)
{printf(“%dt”,temp->info);
if(temp->rflag==0)
{temp=temp->right;
while(temp->lflag==0)
temp=temp->left;
}
else
{temp=temp->right;
}
}
}

void main()
{
int x,ch,num;
tbt *node, *root=NULL;
while(1)
{
clrscr();
printf(“nMenu-In Threaded Binary Tree”);
printf(“n1. Insert”);
printf(“n2. Inorder Traversal”);
printf(“n3. Return Inorder Predecessor”);
printf(“n4. Return Inorder Successor”);
printf(“n5. Exit”);
printf(“nnEnter your choice(1 to 5)?”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
printf(“nEnter the number?”);
scanf(“%d”,&x);
node=makenode(x);
root=insert(root,node);
break;
case 2:
traverseInorder(root);
break;
case 3:
printf(“nEnter the node whose predecessor is required?”);
scanf(“%d”,&num);
node=makenode(num);
x=inorderPredecessor(root,node);
if(x!=-1)
printf(“nInorder predecessor of %d is %d”,node->info,x);
else
printf(“nWrong node entered.”);
break;
case 4:
printf(“nEnter the node whose successor is required?”);
scanf(“%d”,&num);
node=makenode(num);
x=inorderSuccessor(root,node);
if(x!=-1)
printf(“nInorder successor of %d is %d”,node->info,x);
else
printf(“nWrong node entered.”);
break;
case 5:
exit(0);
default:
printf(“nInvalid Choice…!”);
}
getch();
}
}

Tags, ,

Program to implement Right-In-Threaded Binary Tree

Right-In-Threaded Binary Tree

Program to implement Right-In-Threaded Binary Tree:

/*Right In Threaded Binary Tree*/

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

typedef struct threadedbinarytree
{int info;
struct threadedbinarytree *left,*right;
int rlink;
}TBT;

TBT *create();
TBT *makenode(int);
TBT *insert(TBT *,TBT *);
/*inorder or symmetric order*/
void inorder(TBT *);
/*Depth first order*/
void preorder(TBT *);

TBT *create()
{
TBT *temp=(TBT *)malloc(sizeof(TBT));
if(temp==NULL)
{printf(“Memory Allocation Error!”);
exit(1);
}
return temp;
}

TBT *makenode(int x)
{TBT *temp=create();
temp->info=x;
temp->left=NULL;
temp->right=NULL;
temp->rlink=1;/*1 for thread,0 for link*/
return temp;
}

TBT *insert(TBT *root,TBT *newnode)
{
TBT *p,*temp=root;
if(root==NULL)
{root=newnode;
return root;
}
while(temp!=NULL)
{
if(newnode->info<temp->info)
{if(temp->left)
temp=temp->left;
else
{temp->left=newnode;
newnode->left=NULL;
newnode->right=temp;
newnode->rlink=1; /*set during making node*/
break;
}
}
else
{if(temp->right)
{if(temp->rlink==1)
{
newnode->right=temp->right;
temp->right=newnode;
temp->rlink=0;
newnode->rlink=1;/*set during making node*/
break;
}
else
temp=temp->right;
}
else
{p=temp->right;
temp->right=newnode;
temp->rlink=0;
newnode->left=NULL;
newnode->right=p;
newnode->rlink=1;
break;
}
}
}
return root;
}

void preorder(TBT *root)
{TBT *p,*temp=root;
p=root;
while(temp!=NULL)
{while(p!=NULL)
{temp=p;
printf(“%dt”,p->info);
p=p->left;
}
if((temp->rlink==1)&&(temp->right==NULL))
return;
if(temp->rlink==1)
temp=temp->right->right;
else
temp=temp->right;
p=temp;
}
}

void inorder(TBT *root)
{TBT *p,*temp=root;
p=root;
while(temp!=NULL)
{while(p!=NULL)
{temp=p;
p=p->left;
}
printf(“%dt”,temp->info);
if((temp->rlink==1) && (temp->right==NULL))
return;
if(temp->rlink==1)
temp=temp->right;
else
p=temp->right;
}
}

void main()
{
int x,ch;
TBT *node,*root=NULL;
while(1)
{
clrscr();
printf(“nMenu- Right-in-Threaded Binary Tree”);
printf(“nn1. Insert”);
printf(“n2. Traverse inorder”);
printf(“n3. Traverse preorder”);
printf(“n4. Exit”);
printf(“nnEnter your choice?”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
printf(“Enter number to insert?”);
scanf(“%d”,&x);
node=makenode(x);
root=insert(root,node);
break;
case 2:
inorder(root);
break;
case 3:
preorder(root);
break;
case 4:
exit(0);
default:
printf(“nChoice is invalid.”);
}
getch();
}
}

Tags, ,

Program to implement Left-In-Threaded Binary Tree

Left-In-Threaded Binary Tree

Program to implement Left-In-Threaded Binary Tree:

/*Left In Threaded Binary Tree*/

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

typedef struct threadedbinarytree
{int info;
struct threadedbinarytree *left,*right;
int lflag;
}TBT;

TBT *create();
TBT *makenode(int);
TBT *insert(TBT *,TBT *);
void traverseDescending(TBT *);

TBT *create()
{
TBT *temp=(TBT *)malloc(sizeof(TBT));
if(temp==NULL)
{printf(“Memory Allocation Error!”);
exit(1);
}
return temp;
}

TBT *makenode(int x)
{TBT *temp=create();
temp->info=x;
temp->left=NULL;
temp->right=NULL;
temp->lflag=1;/*1 for thread,0 for link*/
return temp;
}

TBT *insert(TBT *root,TBT *newnode)
{
TBT *p,*temp=root;
if(root==NULL)
{root=newnode;
return root;
}
while(temp!=NULL)
{
if(newnode->info<temp->info)
{if(temp->left)
{
if(temp->lflag==1)
{
newnode->left=temp->left;
temp->left=newnode;
temp->lflag=0;
break;
}
else
temp=temp->left;
}
else
{temp->left=newnode;
temp->lflag=0;
break;
}
}
else
{if(temp->right)
temp=temp->right;
else
{
temp->right=newnode;
newnode->left=temp;
newnode->lflag=1;
break;
}
}
}
return root;
}

void traverseDescending(TBT *root)
{
TBT *p,*temp=root;
p=root;
while(temp!=NULL)
{while(p!=NULL)
{temp=p;
p=p->right;
}
printf(“%dt”,temp->info);
if((temp->lflag==1) && (temp->left==NULL))
return;
if(temp->lflag==1)
temp=temp->left;
else
p=temp->left;
}
}

void main()
{
int x,ch;
TBT *node,*root=NULL;
while(1)
{
clrscr();
printf(“nMenu- Right-in-Threaded Binary Tree”);
printf(“nn1. Insert”);
printf(“n2. Traverse Descending Order”);
printf(“n3. Exit”);
printf(“nnEnter your choice?”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
printf(“Enter number to insert?”);
scanf(“%d”,&x);
node=makenode(x);
root=insert(root,node);
break;
case 2:
traverseDescending(root);
break;
case 3:
exit(0);
default:
printf(“nChoice is invalid.”);
}
getch();
}
}

Tags, ,

Program to implement various operations on a Binary Search Tree

Binary Search Tree:

Program to implement various operations on Binary Search Tree:

/*Binary Search Tree*/

#include <stdio.h>
#include <alloc.h>
#include <conio.h>
#include <stdlib.h>

#define MAX 10

/* -OPERATIONS-
(i) Creation of a Binary Search Tree
(ii) Traversal
a) Preorder – Recursive/Iterative
b) Inorder – Recursive/Iterative
c) Postorder – Recursive/Iterative
d) Level by Level
(iii) Insertion
a) Recursive
b) Iterative
(iv) Deletion
a) Recursive
b) Iterative
(v) Searching
a) Recursive
b) Iterative
(vi) Finding Height
(vii) Finding number of nodes
{internal, external, total}
(viii) Finding number of leaves (external nodes)
(ix) Determining mirror image
(x) Creating clone
(xi) Sorting (Inorder traversal – Recursive)
(xii) Disposing
(xiii) Finding smallest – Recursive/Iterative
(xiv) Finding largest – Recursive/Iterative
*/

typedef struct binarysearchtree
{int info;
struct binarysearchtree *left;
struct binarysearchtree *right;
}BST;

/*Allocates the memory*/
BST *create();
/*Makes a new node*/
BST *makenode(int);
/*Inserts a new node in a BST using recursive definition*/
BST *insert(BST *,BST *);
/*Iteratively inserts a newnode in a BST*/
BST *iterativeinsert(BST *,BST *);
/*Traverses BST in preorder by recursive definition*/
void preorder(BST *);
/*Traverses BST in preorder by iterative definition*/
void iterativepreorder(BST *);
/*Traverses BST in inorder by recursive definition*/
void inorder(BST *);
/*Traverses BST in inorder using iterative definition*/
void iterativeinorder(BST *);
/*Traverses BST in postorder using recursive definition*/
void postorder(BST *);
/*Traverses BST in postorder using iterative definition*/
void iterativepostorder(BST *);
/*Searches a given element in BST recursively*/
void searchTree(BST *,int);
/*Searches a given element in BST iteratively*/
void iterativeSearchTree(BST *,int);
/*Returns largest from BST using recursive definition*/
int largest(BST *);
/*Returns largest value using iterative definition*/
int largestiterative(BST *);
/*Returns smallest value using recursive definition*/
int smallest(BST *);
/*Returns smallest value using iterative definition*/
int smallestiterative(BST *);
/*Generates mirror image of BST*/
void mirror(BST *);
/*Generates a duplicate copy of BST*/
void clone(BST *);
/*Returns total nodes of BST*/
int totalnodes(BST *);
/*Returns external nodes (leaf nodes) of BST*/
int external(BST *);
/*Returns internal nodes (interior nodes) of a BST*/
int internal(BST *);
/*Returns height of a BST*/
int heightTree(BST *);
/*Deletes a node from BST using recursive definition*/
BST *deletenode(BST *,int);
/*Deletes a node from BST using iterative definition*/
BST *deletenodeiterative(BST *,int);
/*Deletes BST completely using recursive definition*/
BST *dispose(BST *);
/*Delete BST completely using iterative definition*/
BST *iterativedispose(BST *);
/*Traverses BST level by level using recursive definition*/
void levelbyleveltraversal(BST *);
/*Traverses BST level by level using iterative definition*/
void iterativeleveltraversal(BST *);

/*Allocates the memory*/
BST *create()
{
BST *temp=(BST *) malloc(sizeof(BST));
if(temp==NULL)
{printf(“Memory Allocation Error.”);
exit(1);
}
return temp;
}

/*Makes a new node*/
BST *makenode(int x)
{BST *temp=create();
temp->info=x;
temp->left=NULL;
temp->right=NULL;
return temp;
}

/*Inserts a new node in a BST using recursive definition*/
BST *insert(BST *root,BST *num)
{if(root==NULL)
{root=num;
return root;
}
if(num->info < root->info)
root->left=insert(root->left,num);
else if(num->info > root->info)
root->right=insert(root->right,num);
else
printf(“nDuplicate Value…!”);
return root;
}

/*Iteratively inserts a newnode in a BST*/
BST *iterativeinsert(BST *root,BST *newnode)
{BST *p=root;
if(root==NULL)
{root=newnode;
return root;
}
while(p!=NULL)
{
if(newnode->info<p->info)
{if(p->left)
p=p->left;
else
{p->left=newnode;
break;
}
}
else if(newnode->info>p->info)
{if(p->right)
p=p->right;
else
{p->right=newnode;
break;
}
}
else
{printf(“nDuplicate key found…!”);
break;
}
}
return root;
}

/*Traverses BST in preorder by recursive definition*/
void preorder(BST *root)
{
if(root)
{printf(“%dt”,root->info);
preorder(root->left);
preorder(root->right);
}
}

/*Creating clone of a given tree*/
BST *newroot=NULL; /*global definition of root of new tree*/
void clone(BST *root)
{
BST *temp;
if(root)
{printf(“nMaking node %d”,root->info);
temp=makenode(root->info);
newroot=insert(newroot,temp);
clone(root->left);
clone(root->right);
}
}

/*Traverses BST in inorder by recursive definition*/
void inorder(BST *root)
{
if(root)
{inorder(root->left);
printf(“%dt”,root->info);
inorder(root->right);
}
}

/*Traverses BST in postorder using recursive definition*/
void postorder(BST *root)
{
if(root)
{postorder(root->left);
postorder(root->right);
printf(“%dt”,root->info);
}
}

/*Queue definition for Breadth first traversal*/

typedef struct queue
{int front,rear;
BST *arr[MAX];
}queue;

void enqueue(queue *q,BST *node)
{if(q->rear==MAX-1)
{printf(“nQueue Overflow…!”);
return;
}
q->arr[++q->rear]=node;
}

BST *dequeue(queue *q)
{if(q->rear==-1)
{printf(“nQueue underflow.”);
return NULL;
}
return(q->arr[q->front++]);
}

int empty(queue *q)
{return (q->front>q->rear);
}

void levelbyleveltraversal(BST *root)
{
queue q;
q.front=0;
q.rear=-1;
if(root!=NULL)
{enqueue(&q,root);
while(!empty(&q))
{
root=dequeue(&q);
printf(“%dt”,root->info);
if(root->left!=NULL)
enqueue(&q,root->left);
if(root->right!=NULL)
enqueue(&q,root->right);
}
}
}
/*Global stack declaration used for iterative traversals*/
typedef struct stack
{int top;
BST *items[MAX];
}stk;

/*Checks whether the stack is empty or not*/
int empty(stk *s)
{return(s->top==-1);
}

/*Push a node of BST into the stack*/
void push(stk *s, BST *t)
{if(s->top==MAX-1)
{printf(“nStack Overflow…!”);
return;
}
s->items[++(s->top)]=t;
}

/*Pops/returns a node of BST from the top of the stack*/
BST *pop(stk *s)
{if(s->top==-1)
{printf(“nStack Underflow…!”);
return NULL;
}
return(s->items[(s->top)–]);
}

/*Iterative Preorder Traversal*/
void iterativepreorder(BST *root)
{stk s;
BST *p=root;
s.top=-1;
do
{
while(p!=NULL)
{printf(“%dt”,p->info);
push(&s,p);
p=p->left;
}
if(!empty(&s))
{p=pop(&s);
p=p->right;
}
}while(!empty(&s) || p!=NULL);
}

/*Iterative Inorder Traversal*/
void iterativeinorder(BST *root)
{stk s;
BST *p=root;
s.top=-1;
do
{while(p!=NULL)
{push(&s,p);
p=p->left;
}
if(!empty(&s))
{p=pop(&s);
printf(“%dt”,p->info);
p=p->right;
}
}while(!empty(&s) || p!=NULL);
}

/*Global stack declarations used for
postorder iterative traversals*/

struct pstack
{BST *tree;
int visitedleft,visitedright;
}pstk[MAX];

/*Global declaration of top*/
int top=-1;

void ppush(struct pstack pstk[],BST *t,int VL,int VR)
{if(top==MAX-1)
{printf(“nStack Overflow…!”);
return;
}
top++;
pstk[top].tree = t;
pstk[top].visitedleft=VL;
pstk[top].visitedright=VR;
}

/*Pop the topmost element from the stack*/
struct pstack *ppop(struct pstack *pstk)
{struct pstack *temp;
if(top==-1)
{printf(“nStack Underflow…!”);
return NULL;
}
temp=&pstk[top];
top–;
return temp;
}

/*Checks & returns the value of top*/
int pempty()
{return(top==-1);
}

/*Iterative Postorder Traversal*/
void iterativepostorder(BST *root)
{
struct pstack *temp;
BST *p=root;
while(1)
{while(p!=NULL)
{ppush(pstk,p,1,0);
p=p->left;
}
if(pempty())
return;
temp=ppop(pstk);
if(temp->visitedleft==1 && temp->visitedright==1)
printf(“%dt”,temp->tree->info);
else
{ppush(pstk,temp->tree,temp->visitedleft,1);
p=temp->tree->right;
}
}
}

/*Searching a given node in a BST using recursive definition*/
void searchTree(BST *root,int num)
{if(root==NULL)
{printf(“Number not found…!”);
return;
}
if(num<root->info)
searchTree(root->left,num);
else if(num>root->info)
searchTree(root->right,num);
else
{printf(“nNumber is found…!”);
return;
}
}

/*Searching a given node in a BST using Iterative definition*/
void iterativeSearchTree(BST *root,int num)
{BST *p=root;
if(root==NULL)
{printf(“nNumber not found…!”);
return;
}
while(p!=NULL)
{if(num<root->info)
{if(root->left)
root=root->left;
else
{printf(“nNumber not found…!”);
return;
}
}
else if(num>root->info)
{if(root->right)
root=root->right;
else
{printf(“nNumber not found…!”);
return;
}
}
else
{printf(“nNumber found…!”);
return;
}
}
return;
}

/*Return largest value from BST.
Iterative Definition*/
int largest(BST *root)
{BST *p=root;
if(root==NULL)
return -1;
while(p->right!=NULL)
p=p->right;
return(p->info);
}

/*Return smallest value from BST.
Iterative Definition*/
int smallest(BST *root)
{BST *p=root;
if(root==NULL)
return -1;
while(p->left!=NULL)
p=p->left;
return(p->info);
}

/*Return largest value from BST using recursive definition*/
int largestiterative(BST *root)
{if(root==NULL)
return -1;
if(root->right==NULL)
return(root->info);
else
return largestiterative(root->right);
}

/*Return smallest value from BST using recursive definition*/
int smallestiterative(BST *root)
{if(root==NULL)
return -1;
if(root->left==NULL)
return(root->info);
else
return smallestiterative(root->left);
}

/*Generating mirror image*/
void mirror(BST *root)
{BST *temp;
if(root)
{mirror(root->left);
mirror(root->right);
temp=root->left;
root->left=root->right;
root->right=temp;
}
}

/*Return total nodes of a BST*/
int totalnodes(BST *root)
{if(root==NULL)
return 0;
else
return(totalnodes(root->left)+totalnodes(root->right)+1);
}

/*Return external/leaf nodes of a BST*/
int external(BST *root)
{if(root==NULL)
return 0;
else if(root->left==NULL && root->right==NULL)
return 1;
else
return(external(root->left)+external(root->right));
}

/*Return internal/interior nodes of a BST*/
int internal(BST *root)
{if((root==NULL) || ((root->left==NULL)&&(root->right==NULL)))
return 0;
else
return(internal(root->left)+internal(root->right)+1);
}

/*Return height of a tree – recursive definition*/
void heightTree(BST *root,int *height)
{int leftsubtree,rightsubtree;
if(root==NULL)
{*height=0;
}
else
{heightTree(root->left,&leftsubtree);
heightTree(root->right,&rightsubtree);
if(leftsubtree>rightsubtree)
*height=leftsubtree + 1;
else
*height=rightsubtree + 1;
}
}

/*Returns degree of a given node*/
int degree(BST *root)
{if(root->left==NULL && root->right==NULL)
return 0;
else if(root->left!=NULL && root->right!=NULL)
return 2;
else
return 1;
}

/*Deletion of a node from BST using recursive definition*/
BST *deletenode(BST *root,int val)
{BST *temp;
if(root==NULL)
return root;
if(val<root->info)
root->left=deletenode(root->left,val);
else if(val>root->info)
root->right=deletenode(root->right,val);
else /*if only one node exists*/
{if(degree(root)==0)
{free(root);
return NULL;
}
/*if node contains one child either left or right*/
if(degree(root)==1)
{
if(root->right)
{temp=root->right;
free(root);
return temp;
}
else
{temp=root->left;
free(root);
return temp;
}
}
/*If node to be deleted contains both
left as well as right child*/
if(degree(root)==2)
{temp=root->right;
while(temp->left!=NULL)
temp=temp->left;
temp->left=root->left;
temp=root->right;
free(root);
return temp;
}
}
return root;
}

/*Deletion of a node from BST using iterative definition*/
BST *deletenodeiterative(BST *root,int val)
{
BST *cur,*prev,*temp;
if(root==NULL)
return root;
cur=root;
prev=NULL;
while(cur!=NULL && cur->info!=val)
{prev=cur;
if(val<cur->info)
cur=cur->left;
else
cur=cur->right;
}
if(cur==NULL)
return root;
if(degree(cur)==0)
{
if(prev) /*not a root node*/
{
if(prev->left==cur)
prev->left=NULL;
else
prev->right=NULL;
free(cur);
}
else
{free(cur);
return NULL;
}
}
else if(degree(cur)==1)
{if(cur->left)
{
if(prev)
{
if(prev->left==cur)
prev->left=cur->left;
else
prev->right=cur->left;
free(cur);
}
else{
prev=cur->left;
free(cur);
return(prev);
}
}
else
{
if(prev)
{
if(prev->left==cur)
prev->left=cur->right;
else
prev->right=cur->right;
free(cur);
}
else
{
prev=cur->right;
free(cur);
return (prev);
}
}
}
else if(degree(cur)==2)
{if(prev->left==cur)/*case I*/
/*then traverse left of right child*/
{temp=cur->right;
while(temp->left!=NULL)
temp=temp->left;
temp->left=cur->left;
prev->left=cur->right;
free(cur);
}
else/*case II*/
/*traverse left of right child*/
{temp=cur->right;
while(temp->left!=NULL)
temp=temp->left;
temp->left=cur->left;
if(prev!=NULL)
prev->right=cur->right;
temp=cur->right;
free(cur);
return temp;
}
}
return root;
}

/*function to dispose the BST*/
BST *dispose(BST *root)
{BST *left,*right;
if(root!=NULL)
{left=root->left;
right=root->right;
free(root);
root=dispose(left);
root=dispose(right);
}
return root;
}

void main()
{
int ch,x,flag=0;
BST *newnode,*root=NULL;
while(1)
{clrscr();flag=0;
printf(“nMenu-Binary Search Tree Operations”);
printf(“nn1. Recursive”);
printf(“n2. Non-Recursive”);
printf(“n3. Exit”);
printf(“nnEnter your choice?”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
do
{
clrscr();
printf(“nnRecursive Menu”);
printf(“nn1. Insertion”);
printf(“n2. Inorder traversal”);
printf(“n3. Preorder traversal”);
printf(“n4. Postorder traversal”);
printf(“n5. Deletion”);
printf(“n6. Search node”);
printf(“n7. Find height”);
printf(“n8. Find total nodes”);
printf(“n9. Find leaf nodes”);
printf(“n10. Find interior nodes”);
printf(“n11. Generate mirror image”);
printf(“n12. Generate clone”);
printf(“n13. Display sorted order”);
printf(“n14. Dispose tree”);
printf(“n15. Find largest node”);
printf(“n16. Find smallest node”);
printf(“n17. Return”);

printf(“nEnter your choice?”);
scanf(“%d”,&ch);
switch(ch)
{
case 1: printf(“nEnter the number?”);
scanf(“%d”,&x);
newnode=makenode(x);
root=insert(root,newnode);
break;
case 2: inorder(root);
break;
case 3: preorder(root);
break;
case 4: postorder(root);
break;
case 5: printf(“nEnter the node to delete?”);
scanf(“%d”,&x);
root=deletenode(root,x);
break;
case 6: printf(“nEnter the number to search?”);
scanf(“%d”,&x);
searchTree(root,x);
break;
case 7: heightTree(root,&x);
printf(“nHeight = %d”,x);
break;
case 8: x=totalnodes(root);
printf(“nTotal nodes = %d”,x);
break;
case 9:x=external(root);
printf(“nLeaf nodes = %d”,x);
break;
case 10:x=internal(root);
printf(“nInterior Nodes = %d”,x);
break;
case 11:mirror(root);
break;
case 12:clone(root);
printf(“nDisplaying original BST-inorder”);
inorder(root);
printf(“nDisplaying its clone-inorder”);
inorder(newroot);
break;
case 13:printf(“nTree elements in sorted order:”);
inorder(root);
break;
case 14:printf(“nDisposing the tree…!”);
root=dispose(root);
break;
case 15:x=largest(root);
printf(“nLargest value = %d”,x);
break;
case 16:x=smallest(root);
printf(“nSmallest value = %d”,x);
break;
case 17:flag=1;break;
default:printf(“nInvalid choice…!”);
}
getch();
}while(flag!=1);
break;
case 2:
do
{clrscr();
printf(“nnNon-Recursive/Iterative Menu”);
printf(“n1. Insertion”);
printf(“n2. Inorder traversal”);
printf(“n3. Preorder traversal”);
printf(“n4. Postorder traversal”);
printf(“n5. Level by level/BFS traversal”);
printf(“n6. Deletion”);
printf(“n7. Search node”);
printf(“n8. Find largest node”);
printf(“n9. Find smallest node”);
printf(“n10. Return”);
printf(“nEnter your choice?”);
scanf(“%d”,&ch);
switch(ch)
{case 1: printf(“nEnter the number?”);
scanf(“%d”,&x);
newnode=makenode(x);
root=iterativeinsert(root,newnode);
break;
case 2: iterativeinorder(root);
break;
case 3: iterativepreorder(root);
break;
case 4: iterativepostorder(root);
break;
case 5: levelbyleveltraversal(root);
break;
case 6: printf(“nEnter the node to delete?”);
scanf(“%d”,&x);
root=deletenodeiterative(root,x);
break;
case 7: printf(“nEnter the number to search?”);
scanf(“%d”,&x);
iterativeSearchTree(root,x);
break;
case 8:x=largestiterative(root);
printf(“nLargest value = %d”,x);
break;
case 9:x=smallestiterative(root);
printf(“nSmallest value = %d”,x);
break;
case 10:flag=1;break;
default:printf(“nInvalid choice…”);
}
getch();
}while(flag!=1);
break;
case 3:
exit(0);
default:
printf(“nInvalid choice…!”);
}
}
}

Tags, ,

Program to create a Binary Search Tree

Binary Search Trees: 

A Binary Search Tree is a Binary Tree which satisfies the following conditions:

  1. The left subtree of the root contains keys smaller than the root.
  2. The right subtree of the root contains keys greater than the root.
  3. The left and right subtrees are also Binary Search Trees.
  4. There are no duplicates in the tree.

Program to create a Binary Search Tree:

/*Creating a Binary Search Tree*/
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

typedef struct binarytree
{int info;
struct binarytree *left;
struct binarytree *right;
}BT;

BT *create()
{BT *temp=(BT *)malloc(sizeof(BT));
if(temp==NULL)
{printf(“nMemory Allocation Error.”);
exit(1);
}
return temp;
}

BT *makenode(int x)
{BT *ptr=create();
ptr->info=x;
ptr->left=NULL;
ptr->right=NULL;
return ptr;
}

BT *insert(BT *root,int x)
{BT *p,*q,*ptr=makenode(x);
if(root==NULL)
{root=ptr;
return root;
}
p=q=root;
while(p!=NULL)
{q=p;
if(x<q->info)
p=q->left;
else
p=q->right;
}
if(x<q->info)
q->left=ptr;
else
q->right=ptr;
return root;
}

void inorder(BT *root)
{if(root)
{inorder(root->left);
printf(“%dt”,root->info);
inorder(root->right);
}
}

void preorder(BT *root)
{if(root)
{printf(“%dt”,root->info);
preorder(root->left);
preorder(root->right);
}
}

void postorder(BT *root)
{if(root)
{postorder(root->left);
postorder(root->right);
printf(“%dt”,root->info); }
}

void main()
{
BT *root=NULL;
int ch,x;
while(1)
{clrscr();
printf(“nBinary Search Tree-MENU”);
printf(“nn1. Insert Node”);
printf(“n2. Inorder Display”);
printf(“n3. Preorder Display”);
printf(“n4. Postorder Display”);
printf(“n5. Exit”);
printf(“nnEnter your choice?”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
printf(“nEnter number?”);
scanf(“%d”,&x);
root=insert(root,x);
break;
case 2:
inorder(root);
break;
case 3:
preorder(root);
break;
case 4:
postorder(root);
break;
case 5:
exit(0);
default:
printf(“nInvalid Choice.”);
}
getch();
}
}

 

Tags, ,

Binary Search Tree

Binary Search Tree

A Binary Search Tree is a Binary Tree which satisfies the following conditions:

  1. The left subtree of the root contains keys smaller than the root.
  2. The right subtree of the root contains keys greater than the root.
  3. The left and right subtrees are also Binary Search Trees.
  4. There are no duplicates in the tree.

A Binary Search Tree may be represented using arrays and linked list.

Representation of Binary Search Tree using Arrays:

Array representation of Binary Search Tree requires numbering of all the nodes of the tree beginning from the root to bottom and left to right for the same level.  Even the empty nodes are numbered.  They are then inserted in the array based on their numbering.

Array contains elements in proper numbering as indicated in the above figure.  Null values are left blank in the array or may be filled with zeroes.  The required size of the array for n elements will be 2n-1.

Representation of Binary Search Tree using Linked List:

Linked list representation of a binary tree is using a node that contains three parts, an information part, an address to the left child node and another address to the right child node.  A Binary search tree using linked list is explained in the figure below:

Example:

 

Operations:  The operations that can be performed on a BST are given below:

 

Recursive Traversal (Inorder, Preorder, Postorder)

In-order:

  • Traverse left subtree.
  • Visit the root.
  • Traverse right subtree.
 /*Traverses BST in inorder by recursive definition*/
void inorder(BST *root)
{
if(root)
{inorder(root->left);
printf(“%dt”,root->info);
inorder(root->right);
}
}

 Pre-order:

  • Visit the root.
  • Traverse left subtree.
  • Traverse right subtree.

 /*Traverses BST in preorder by recursive definition*/
void preorder(BST *root)
{
if(root)
{printf(“%dt”,root->info);
preorder(root->left);
preorder(root->right);
}
}

 Post-order:

  • Traverse left subtree.
  • Traverse right subtree.
  • Visit the root.

 /*Traverses BST in postorder using recursive definition*/
void postorder(BST *root)
{
if(root)
{postorder(root->left);
postorder(root->right);
printf(“%dt”,root->info);
}
}

Non-Recursive Traversal:

/*Global stack declaration used for iterative traversals*/

typedef struct stack
{int top;
BST *items[MAX];
}stk;

/*Checks whether the stack is empty or not*/

int empty(stk *s)
{return(s->top==-1);
}

/*Push a node of BST into the stack*/

void push(stk *s, BST *t)
{if(s->top==MAX-1)
{printf(“nStack Overflow…!”);
return;
}
s->items[++(s->top)]=t;
}

/*Pops/returns a node of BST from the top of the stack*/

BST *pop(stk *s)
{if(s->top==-1)
{printf(“nStack Underflow…!”);
return NULL;
}
return(s->items[(s->top)–]);
}

Iterative In-order traversal:

/*Iterative Inorder Traversal*/

void iterativeinorder(BST *root)
{stk s;
BST *p=root;
s.top=-1;
do
{while(p!=NULL)
{push(&s,p);
p=p->left;
}

if(!empty(&s))
{p=pop(&s);
printf(“%dt”,p->info);
p=p->right;
}
}while(!empty(&s) || p!=NULL);
}

Iterative Pre-order traversal:

/*Iterative Preorder Traversal*/

void iterativepreorder(BST *root)
{stk s;
BST *p=root;
s.top=-1;
do
{
while(p!=NULL)
{printf(“%dt”,p->info);
push(&s,p);
p=p->left;
}

if(!empty(&s))
{p=pop(&s);
p=p->right;
}
}while(!empty(&s) || p!=NULL);
}

Iterative Post-order traversal:

/*Global stack declarations used for postorder iterative traversals*/
struct pstack
{BST *tree;
int visitedleft,visitedright;
}pstk[MAX];/*Global declaration of top*/
int top=-1;void ppush(struct pstack pstk[],BST *t,int VL,int VR)
{if(top==MAX-1)
{printf(“nStack Overflow…!”);
return;
}
top++;
pstk[top].tree = t;
pstk[top].visitedleft=VL;
pstk[top].visitedright=VR;
}/*Pop the topmost element from the stack*/
struct pstack *ppop(struct pstack *pstk)
{struct pstack *temp;
if(top==-1)
{printf(“nStack Underflow…!”);
return NULL;
}
temp=&pstk[top];
top–;
return temp;
}/*Checks & returns the value of top*/
int pempty()
{return(top==-1);
}/*Iterative Postorder Traversal*/
void iterativepostorder(BST *root)
{
struct pstack *temp;
BST *p=root;
while(1)
{while(p!=NULL)
{ppush(pstk,p,1,0);
p=p->left;
}
if(pempty())
return;
temp=ppop(pstk);
if(temp->visitedleft==1 && temp->visitedright==1)
printf(“%dt”,temp->tree->info);
else
{ppush(pstk,temp->tree,temp->visitedleft,1);
p=temp->tree->right;
}
}
}

Recursive Insertion:

/*Inserts a new node in a BST using recursive definition*/
BST *insert(BST *root,BST *num)
{if(root==NULL)
{root=num;
return root;
}
if(num->info < root->info)
root->left=insert(root->left,num);
else if(num->info > root->info)
root->right=insert(root->right,num);
else
printf(“nDuplicate Value…!”);
return root;
}

Non-Recursive Insertion:

/*Iteratively inserts a newnode in a BST*/
BST *iterativeinsert(BST *root,BST *newnode)
{BST *p=root;
if(root==NULL)
{root=newnode;
return root;
}
while(p!=NULL)
{
if(newnode->info < root->info)
{if(p->left)
p=p->left;
else
{p->left=newnode;
break;
}
}
else if(newnode->info > p->info)
{if(p->right)
p=p->right;
else
{p->right=newnode;
break;
}
}
else
{printf(“nDuplicate key found…!”);
break;
}
}
return root;
}

Finding height:

/*Return height of a tree – recursive definition*/
void heightTree(BST *root,int *height)
{int leftsubtree,rightsubtree;
if(root==NULL)
{*height=0;
}
else
{heightTree(root->left,&leftsubtree);
heightTree(root->right,&rightsubtree);
if(leftsubtree>rightsubtree)
*height=leftsubtree + 1;
else
*height=rightsubtree + 1;
}
}
Finding degree of a given node:
/*Returns degree of a given node*/
int degree(BST *root)
{if(root->left==NULL && root->right==NULL)
return 0;
else if(root->left!=NULL && root->right!=NULL)
return 2;
else
return 1;
}
Finding total number of nodes:
/*Return total nodes of a BST*/
int totalnodes(BST *root)
{if(root==NULL)
return 0;
else
return(totalnodes(root->left)+totalnodes(root->right)+1);
}
Finding number of leaves/exterior nodes

/*Return external/leaf nodes of a BST*/
int external(BST *root)
{if(root==NULL)
return 0;
else if(root->left==NULL && root->right==NULL)
return 1;
else
return(external(root->left)+external(root->right));
}
Finding number of interior/internal nodes
/*Return internal/interior nodes of a BST*/
int internal(BST *root)
{if((root==NULL) ||
((root->left==NULL)&&(root->right==NULL)))
return 0;
else
return(internal(root->left)+internal(root->right)+1);
}
Determining mirror image:
/*Generating mirror image*/
void mirror(BST *root)
{BST *temp;
if(root)
{mirror(root->left);
mirror(root->right);
temp=root->left;
root->left=root->right;
root->right=temp;
}
}
Finding smallest – Recursive definition
/*Return smallest value from BST using recursive definition*/
int smallestrecursive(BST *root)
{if(root==NULL)
return -1;
if(root->left==NULL)
return(root->info);
else
return smallestrecursive(root->left);
}
Finding smallest – Non-Recursive definition
/*Return smallest value from BST-Iterative Definition*/
int smallest(BST *root)
{BST *p=root;
if(root==NULL)
return -1;
while(p->left!=NULL)
p=p->left;
return(p->info);
}
Finding largest – Recursive definition
/*Return largest value from BST using recursive definition*/
int largestrecursive(BST *root)
{if(root==NULL)
return -1;
if(root->right==NULL)
return(root->info);
else
return largestrecursive(root->right);
}
Finding largest – Non-Recursive definition
/*Return largest value from BST-Iterative Definition*/
int largest(BST *root)
{BST *p=root;
if(root==NULL)
return -1;
while(p->right!=NULL)
p=p->right;
return(p->info);
}
Recursive Searching:
/*Searching a given node in a BST using recursive definition*/
void searchTree(BST *root,int num)
{if(root==NULL)
{printf(“Number not found…!”);
return;
}
if(num<root->info)
searchTree(root->left,num);
else if(num>root->info)
searchTree(root->right,num);
else
{printf(“nNumber is found…!”);
return;
}
}
Non-Recursive Searching:
/*Searching a given node in a BST using Iterative definition*/
void iterativeSearchTree(BST *root,int num)
{BST *p=root;
if(root==NULL)
{printf(“nNumber not found…!”);
return;
}
while(p!=NULL)
{if(num<root->info)
{if(root->left)
root=root->left;
else
{printf(“nNumber not found…!”);
return;
}
}
else if(num>root->info)
{if(root->right)
root=root->right;
else
{printf(“nNumber not found…!”);
return;
}
}
else
{printf(“nNumber found…!”);
return;
}
}
return;
}
Recursive Deletion:

/*Deletion of a node from BST using recursive definition*/
BST *deletenode(BST *root,int val)
{BST *temp;
if(root==NULL)
return root;
if(val<root->info)
root->left=deletenode(root->left,val);
else if(val>root->info)
root->right=deletenode(root->right,val);
else /*if only one node exists*/
{if(degree(root)==0)
{free(root);
return NULL;
}
/*if node contains one child either left or right*/
if(degree(root)==1)
{
if(root->right)
{temp=root->right;
free(root);
return temp;
}
else
{temp=root->left;
free(root);
return temp;
}
}
/*If node to be deleted contains both
left as well as right child*/
if(degree(root)==2)
{temp=root->right;
while(temp->left!=NULL)
temp=temp->left;
temp->left=root->left;
temp=root->right;
free(root);
return temp;
}
}
return root;
}

Function to return degree of a given node:

/*Returns degree of a given node*/
int degree(BST *root)
{if(root->left==NULL && root->right==NULL)
return 0;
else if(root->left!=NULL && root->right!=NULL)
return 2;
else
return 1;
}

Non-Recursive Deletion:

/*Deletion of a node from BST using iterative definition*/
BST *deletenodeiterative(BST *root,int val)
{
BST *cur,*prev,*temp;
if(root==NULL)
return root;
cur=root;
prev=NULL;
while(cur!=NULL && cur->info!=val)
{prev=cur;
if(val<cur->info)
cur=cur->left;
else
cur=cur->right;
}
if(cur==NULL)
return root;
if(degree(cur)==0)
{
if(prev) /*not a root node*/
{
if(prev->left==cur)
prev->left=NULL;
else
prev->right=NULL;
free(cur);
}
else
{free(cur);
return NULL;
}
}
else if(degree(cur)==1)
{if(cur->left)
{
if(prev)
{
if(prev->left==cur)
prev->left=cur->left;
else
prev->right=cur->left;
free(cur);
}
else{
prev=cur->left;
free(cur);
return(prev);
}
}
else
{
if(prev)
{
if(prev->left==cur)
prev->left=cur->right;
else
prev->right=cur->right;
free(cur);
}
else
{
prev=cur->right;
free(cur);
return (prev);
}
}
}
else if(degree(cur)==2)
{if(prev->left==cur)/*case I*/
/*then traverse left of right child*/
{temp=cur->right;
while(temp->left!=NULL)
temp=temp->left;
temp->left=cur->left;
prev->left=cur->right;
free(cur);
}
else/*case II*/
/*traverse left of right child*/
{temp=cur->right;
while(temp->left!=NULL)
temp=temp->left;
temp->left=cur->left;
if(prev!=NULL)
prev->right=cur->right;
temp=cur->right;
free(cur);
return temp;
}
}
return root;
}

Dispose BST:
/*function to dispose the BST*/
BST *dispose(BST *root)
{BST *left,*right;
if(root!=NULL && left!=NULL && right!=NULL)
{left=root->left;
right=root->right;
free(root);
root=dispose(left);
root=dispose(right);
}
return root;
}

Level by Level Traversal:

Level by Level traversal or Breadth-First Traversal is a traversal technique in which each node starting from the highest level is visited level by level, such that the nodes for the same level are visited from left to right.  An example of  Breadth First Traversal or Level by Level traversal is given below:

BFS traversal: A, B, C, D, E, F, G

For its implementation a queue may be used such that after a node is visided, its left or right child nodes, if present, are placed at the rear end of queue and the node at the front of the queue is visited.  The ‘C’ function to implement BFS traversal is given below:

/*Queue definition for Breadth first traversal*/

typedef struct queue
{int front,rear;
BST *arr[MAX];
}queue;

void enqueue(queue *q,BST *node)
{if(q->rear==MAX-1)
{printf(“nQueue Overflow…!”);
return;
}
q->arr[++q->rear]=node;
}

BST *dequeue(queue *q)
{if(q->rear==-1)
{printf(“nQueue underflow.”);
return NULL;
}
return(q->arr[q->front++]);
}

int empty(queue *q)
{return (q->front>q->rear);
}

/*Level by Level traversal or Depth First Traversal*/
void levelbyleveltraversal(BST *root)
{
queue q;
q.front=0;
q.rear=-1;
if(root!=NULL)
{enqueue(&q,root);
while(!empty(&q))
{
root=dequeue(&q);
printf(“%dt”,root->info);
if(root->left!=NULL)
enqueue(&q,root->left);
if(root->right!=NULL)
enqueue(&q,root->right);
}
}
}

Disposing:

/*function to dispose the BST*/
BST *dispose(BST *root)
{BST *left,*right;
if(root!=NULL)
{left=root->left;
right=root->right;
free(root);
root=dispose(left);
root=dispose(right);
}
return root;
}

Creating clone:

/*Creating clone of a given tree*/
BST *newroot=NULL; /*global definition of root of new tree*/

void clone(BST *root)
{
BST *temp;
if(root)
{printf(“nMaking node %d”,root->info);
temp=makenode(root->info);
newroot=insert(newroot,temp);
clone(root->left);
clone(root->right);
}
}

Tags, ,

Advanced Trees

Advanced Trees

Definitions:

Red/Black Tree:

It was invented by Rudolf Bayer in 1972.  Red-black trees are one of the preferred methods of maintaining binary search trees.  An n node red-black tree has the height of O(logn).  Moreover balancing time for such a tree on account of insertion and deletion is O(logn).  A red-black tree is a binary search tree with the following properties:

  • Every node is colored either red or black.
  • The root node is black.
  • The value of any node is greater than the value of its left child and less than the value of its right child.
  • Every red node that is not a leaf node has only black children.
  • Every path from the root to a leaf contains the same number of black nodes.
  • All leaf nodes are black.

A red-black tree contains one more field for storing the color the node either red or black.

Splay Tree:

A splay tree is a binary search tree.  It was invented by Daniel Sleator and Robert Tarjan.  All normal operations on a splay tree are based on one basic operation called splaying.  Splaying the tree for a certain element rearranges the tree so that the element is placed at the root of the tree.  To do this, the element is first found with a standard tree search, then tree rotations are performed in a specific fashion to bring the element to the top.  Thus in a splay tree certain elements will be accessed more often than others, thereby, resulting in good performance for certain applications such as implementing caches.  It performs basic operations such as insertion, look-up and removal in O(logn) average time.

Trie:

A trie is a data structure used for storing strings.  One node is reserved for every common prefix.  The strings are stored in extra leaf nodes.

Patricia Tree:

It is a data structure used to represent a Trie in compact form where all nodes with one child are merged with their parent.

Suffix Tree:

It is a patricia tree corresponding to a given string.  It is a compact representation of a trie corresponding to the suffixes of a given string where all nodes with one child are merged with their parent.

Multi-Suffix Tree:

A multi suffix tree is a suffix tree extended to multiple strings by concatenating the strings.

Bucket Trie:

A bucket trie is a type of trie where leaf nodes are buckets which can hold k strings.  Thus the size of the bucket is generally taken to be fixed.

Compact trie:

It is a trie in which non-branching subtrees leading to leaf nodes are cut off.

Digital Tree:

A tree for storing strings in which nodes are organized by substrings common to two or more strings.

Digital Search Tree:

It is a data structure, a trie, which stores the strings in internal nodes, so there is no need for extra leaf nodes to store the strings.

Complete Binary Tree:

A full binary tree is a tree in which every node has zero or two children.  A perfect binary tree is a complete binary tree in which leaves are at the same depth.  Sometimes the perfect binary tree is also called the complete binary tree.

Tagged Union:

A tagged union is a data structure used to hold a value that could take on several different values of fixed type.  Only one of the types can be in use at any one time, and a tag field explicitly indicates which one is in use.  It is also called a variant, variant record, or disjoint union.  Like ordinary unions, tagged unions can save storage by overlapping storage areas for each type since only one is in use at a time.  In languages with tagged unions, a tree node is often a tagged union of two types of nodes, one of which is a 3-tuple data, left child and right child and the other of which is a leaf node, which contains no data and functions much like the null value in a language with pointers.

Binary Space Partitioning:

It is a method for recursively subdividing a space into convex sets.  This subdivision gives rise to a representation of the scene by means of a tree data structure.

Binary Space Partition Trees:

Binary Space Partition Trees (BSP) were introduced by Fuchs, Kedem and Naylor around 1980.  BSP tree is a hierarchical subdivisions of n dimensional space into convex subspaces.  Each node has a front and back leaf.  Starting off with the root node, all subsequent insertions are partitioned by the hyperplane of the current node.  In two-dimensional space, a hyperplane is a line.  In three-dimensional space, a hyperplane is a plane.  The end goal of a BSP tree is for the hyerplanes of the leaf nodes to be trivially behind or in-front of the parent hyperplane.

Quadtree:

A quadtree is a tree data structure in which each internal node has up to four children.  Quadtrees are more often used to partition a two dimensional space by recursively subdividing it into four quadrants.  Some common applications of quadrees are image representation, spatial indexing etc.  Quadtrees are two dimensional analog of octrees.

Octrees:

An octree is a tree data structure mainly used for organizing 3-dimensional data.  Each node of an octree has eight children.

R-trees:

R-trees are tree data structures similar to B-trees, but are used for spatial access methods i.e. for indexing multi-dimensional information.  Each node of an R-tree has a variable number of entries.  Each entry within a non-leaf node stores two pieces of data; a way of identifying a child node and the bounding box of all entries within this child node.  A new element will go into the leaf node that requires the least enlargement in its bounding box.  The insertion and deletion algorithms use the bounding boxes from the nodes to ensure that nearby elements are placed in the same leaf node.  Different algorithms can be used to split nodes when they become too full, resulting in the “Quadratic” and “Linear” R-tree subtypes.

Hash Table:

A hash table is a data structure that provides fast lookup of a record indexed by a key where the domain of the key is too large for simple indexing; as would occur if an array were used.  Like arrays, hash tables can provide O(1) lookup with respect to the number of records in the table.  Hash tables are often used to implement associative arrays.

Parse Tree:

A parse tree is a grammatical structure represented as a tree data structure.  Grammar is the study of the rules governing the use of a language.  The subfields of grammar are phonetics, phonology, morphology, syntax and semantics.  Grammar is part of the general study of language called linguistics.

B+ Tree: 

A B+ tree index takes the form of a balanced tree in which every path from the root to the tree leaf is of the same length.  Each non-leaf node in the tree has between ‘n/2’ and ‘n’ children, where n is fixed for a particular tree.  The B+ tree structure creates performance overhead on insertion and deletion and adds space overhead.  The space overhead is acceptable when we consider the performance benefits of the B+ tree structure.  Each node of a B+ tree contains a pointer and the associated search key value.  The pointer in the leaf node of the B+ tree points either to a file with the associated search key value or to a bucket of pointers. Each leaf can hold upto (n-1) values.  The minimum value that a leaf node may contains is (n-1)/2.  The non-leaf nodes of the B+ tree form a multilevel sparse index on the leaf nodes.  The structure of the non-leaf node is the same as the leaf node, except that all pointers are pointers to tree nodes.  A non-leaf node may hold upto ‘n’ pointers but must hold atleast (n/2) pointers.  ‘B’ in the ‘B+’ trees stands for balanced.  It is the balance property of B+ trees that ensures good performance for lookup, insertion and deletion of records.  The main difference between a B tree index and a B+ index is that a B tree eliminates the redundant storage of search key values.  A B tree allows search key value to appear only once.  Thus, B+ tree is preferred for its structural simplicity.

Tags, ,

x Close

Like Us On Facebook