Definition: A binary tree is a finite set of elements that is either empty or is partitioned into three disjoint subsets. The first subset is a single element set called the root of the tree. The other two subsets are themselves binary trees, called the left and right subtrees of the original tree.
18.1 BASIC TERMINOLOGY
Consider the following figure to appreciate the basic terminologies associated with a tree data structure representation.
The tree in fig. 18.1 contains eight nodes with A as its root. The left and right subtrees of the node A, are rooted at B and C respectively. The nodes D, E, G and H have no children nodes and are called leaf nodes. The nonleaf nodes e.g. B or C can be treated as the root of their respective binary trees. The hierarchical structure of a tree establishes relationships between the nodes related by their positions in the structure. Thus in figure 18.1 the node A is the parent node having two children with B and C as left and right children respectively. Hence, B and C are sibling nodes since they are the descendants of the same parent node A. A node that does not have any child node is considered to be a leaf node.
18.2 PROPERTIES OF A BINARY TREE
Before concentrating on the implementation of binary trees, let us first examine some of its properties. In particular, let us examine how the factors like depth, level, number of leaf nodes and total number of nodes and their relationships determine the characteristics of a binary tree.
The level of a node in a binary tree is identified with respect to the position of the root of the tree. For example in figure 18.2, the level of the node A (root) is 0, and its left and right subtrees are at level 1 i.e. at a level which is one more than that of their parent. Similarly, the node F is at level 2.
The depth of a binary tree is the maximum level of any leaf in the tree. The binary tree in figure 18.2 has depth(d) 2.
If a binary tree has n nodes at level l, the number of nodes in the next level (i.e. l + 1) can be at most 2n. The maximum number of nodes at a particular level will vary from 1 at level 0, to 2 at level 1, 4 at level 2 and so on. The maximum number of nodes at a level l is 2l, where l can take any value between 0 and d (depth of the tree).
In a complete binary tree, all intermediate nodes must have two children. Thus a complete binary tree will have exactly 2k number of nodes at each level(k). The total number of nodes (totn) in a complete binary tree is the sum of number of nodes at each level k where k varies between 0 and d.
totn = 20 + 21 + 22 + ......... + 2d =
Therefore, if the total number of nodes in complete binary tree is known, we can easily compute the depth (d) of the tree. The depth (d) is determined by,
d = log2 (totn + 1) - 1
Thus if a complete binary tree contains 15 nodes then the depth d is,
d = log2(15 + 1) -1 = 4 - 1 = 3
A binary tree of depth d is called an almost complete binary tree if :
1. Each leaf in the tree is either at level d or at d - 1.
2. For any node A in the tree with a right descendant at level d, all left descendants of A, which are leaves, are also at level d.
18.3 LINKED REPRESENTATION OF BINARY TREE
The linked representation of a binary tree involves usage of two dedicated pointers to join left and right subtrees. One can also maintain another pointer (father) which points to the parent of the node. Apart from these pointers, a node maintains the relevant information pertaining to it.
With the linked representation of a binary tree structure, insertion and deletion of nodes can be readily handled by simple pointer manipulations.
A binary tree is a useful data structure when two-way decisions must be made at each point in a process. For example, a sorted data can be readily arranged in a binary tree data structure such that at each node the data value of its left-child be less than or equal to that of the node. Similarly, the data for the right child can be greater than or equal to the data value of the node.
The figure 18.3a shows binary tree representation of a sorted data sequence :
1 3 4 5 6 8 9
Fig. 18.3a :A complete Binary tree.
Fig. 18.3b : data arranged in a linear sequence.
The figure 18.3a which is a complete binary tree of depth 2 has 5 as its root. Such a structure increases efficiency of searching for locating a desired information (using a binary search algorithm). If the data is arranged in a linear sequence as in figure 18.3b, to locate a value say 9, one would require successive comparison of the number with each element in the given sequence. So total number of comparisons to locate the last element (worst case) would be equal to the number of elements in the list minus one. But in case of a complete binary tree, to locate any data component, the maximum number of searches would be always lesser than or equal to d + 1 where d is depth. This is due to the fact that each comparison with the node data results in selection of either the left or the right subtree. Thus limiting the search only to half of the original tree. Hence to locate 9 in figure 18.3a, the first comparison will begin with the root (info 5). This would indicate that the requisite data (9) being greater than 5, can be located at the right subtree of the current node (i.e. node having value 5).
The traversal of a tree, or in other words, visiting each node in the tree structure can be done in three ways preorder, inorder and postorder. In the following we discuss each of these traversal algorithms and compare their output considering the tree structure given in the figure 18.3a.
Preorder traversal performs the following three operations:
1. Visit the root.
2. Traverse the left subtree in preorder.
3. Traverse the right subtree in preorder.
The preorder traversal of the binary tree in figure 18.3a produces the output :
5 3 1 4 8 6 9
Inorder traversal performs the following three operations:
2. Traverse the left subtree in inorder.
1. Visit the root.
3. Traverse the right subtree in inorder.
The sequence of nodes of fig 18.3a that will be traversed using inorder traversal are :
1 3 4 5 6 8 9
Postorder traversal performs the following three operations:
1. Traverse the left subtree in postorder.
2. Traverse the right subtree in postorder.
3. Visit the root.
The postorder traversal of the binary tree in fig 18.3a results in the following sequence of nodes :
1 4 3 6 9 8 5
We now give an implementation of the ADT binary tree and its traversal routines in C. Here we have used two pointers r and l to indicate the right and left trees of a node. While implementing an ADT binary tree, besides the traversal routines, we should also support operations such as insert and delete for inserting a node into the tree and deleting a node from it. The function allocate is used to create a node of a binary tree. Note a node thus created can itself be treated as a binary tree with no right and left child subtrees.
EXAMPLE 18.1 :
#include
struct bintree {
int data;
struct bintree *r,*l;
};
typedef struct bintree TREE;
TREE *delete_node(TREE *p,int data),*allocate(int dt);
void insert(TREE *rt, int dt);
void inorder(TREE *rt);
/* inorder routine */
void inorder(TREE *rt)
{
if(!rt)
return;
inorder(rt->l);
printf("%d, ",rt->data); /* visit the root */
inorder(rt->r);
}
/* preorder routine */
void preorder(TREE *rt)
{
if(!rt)
return;
printf("%d, ",rt->data); /* visit the root */
preorder(rt->l);
preorder(rt->r);
}
/* postorder routine */
void postorder(TREE *rt)
{
if(!rt)
return;
postorder(rt->l);
postorder(rt->r);
printf("%d, ",rt->data); /* visit the root */
}
/* allocate memory for a node and store data */
TREE *allocate(int data)
{
TREE *temp;
temp=(TREE *) malloc(sizeof(TREE));
temp->r=temp->l=NULL;
temp->data=data;
return(temp);
}
/* nonrecursive insert routine */
void insert(TREE *rt,int data)
{
TREE *t,*s,*temp;
t=s=rt;
temp=allocate(data);
while(data != t->data && (s))
{
t=s;
if(data <>data)
s=t->l;
else
s=t->r;
}
if(data == t->data)
{
printf("Duplicate data \n");
free(temp);
}
else
if (data
t->l=temp;
else
t->r=temp;
}
/* recursive delete routine */
TREE *delete_node(TREE *p,int data)
{
TREE *q,*s;
if(!p)
{
printf("No data \n");
return(p);
}
if(data == p->data)
{
q=s=p;
if(!(p->r))
{
p=q->l;
free(q);
return(p);
}
else
if(!(p->l))
{
p=q->r;
free(q);
return(p);
}
else
{
p=p->r;
s=p;
while(s->l)
s=s->l;
s->l=q->l;
free(q);
return(p);
}
}
if(data > p->data)
p->r=delete_node(p->r,data);
else
if(data <>data)
p->l=delete_node(p->l,data);
return(p);
}
A recursive implementation of the insert operation in a binary tree is shown in the example 18.2 . This function is called with the address of root node and the new node to be inserted. It is assumed that information to be stored in a new node to be inserted has already been provided before calling the rec_insert function. The function returns the pointer to root of the tree at the end of execution (note the function returns a pointer to a TREE i.e. TREE *rec_insert). In the calling program, the rec_insert is invoked as,
root=rec_insert(root,new)
If the tree is empty (i.e. root is NULL) the function returns the address of the new node and the address of the new node gets assigned to the root. Further insertion of any new node is done by comparing the information of the new node with that of the root node. In case the new node information is found to be greater than that of the root node, the current root’s right subtree is considered to be the new root and the pointer (rt->r) is used in the next invocation of rec_insert. On the other hand if the new data value is smaller than that of the root node of the tree under consideration, the left subtree is used for insertion. This is achieved by calling the rec_insert with rt->l as its root node. The process continues till a leaf node is reached. At that point, the insertion takes place as the left or the right child of this leaf node.
EXAMPLE 18.2 :
/* recursive insert routine */
TREE *rec_insert(TREE *rt,TREE *nw)
{
if(!rt)
return(nw);
if(nw->data > rt->data)
rt->r=rec_insert(rt->r,nw);
else
if(nw->data <>data)
rt->l=rec_insert(rt->l,nw);
return(rt);
}
2. Find the sequence of vertices of the following binary trees which will be visited using i) preorder ii) postorder iii) inorder traversal procedures.
No comments:
Post a Comment