We extend the concept of linked data structures to structure containing nodes with more than one self-referenced field. A binary tree is made of nodes, where each node contains a "left" reference, a "right" reference, and a data element. The topmost node in the tree is called the root. Every node (excluding root) in a tree is connected by a directed edge from exactly one other node. This node is called a parent. On the other hand, each node can be connected to arbitrary number of nodes, called children. Nodes with no children are called leaves, or external nodes. Nodes which are not leaves are called internal nodes. Nodes with the same parent are called siblings. One example of creation of binary tree is given below Fig2.
Tree terminologies
- The depth of a node is the number of edges from the root to the node.
- The height of a node is the number of edges from the node to the deepest leaf.
- The height of a tree is a height of the root.
- A leaf node which does not have any child node.
- The child nodes of a given parent node are called siblings.
- A strictly binary tree.is a binary tree in which each node has exactly zero or two children.
- A complete binary tree is a binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right.
Properties of Binary tree
- The number of external nodes is 1 more than the number of internal nodes. It is easy to see this if we start removing external nodes with their internal parent, one pair at a time. At the end of this process only the root with its two children will remain.
- The number of external nodes is at least h+1, where h is the height of the tree, and at most 2h. The later holds for a full binary tree, which is a tree where internal nodes completely fill every level.
- The number of nodes is at least h and at most 2h-1.
- A binary tree with n nodes has exactly n-1 edges.
Height of a Binary Tree
We know that binary tree with height h can have no more 2h-1 elements. Thus if n is the total number of nodes then
n <= 2h-1
n+1 <= 2h
log n+1 <= log 2h
log n+1 <= h*log 2
log
n+1 <= h*1
h >= log n+1
Representation Of a Binary Tree
Binary tree can be represented either using array or using linked
list. In case of array implementation tree can be stored
sequentially i.e. a block of memory is to be allocated before going
to store the actual tree in it. The following rules are used to
decide the location of any node:
The root node is at location 1
and for any other node with index i,1 < i <= n, parent(i)=i/2; left
child(i)=2i and right child(i)=2i+1.The advantage of using array is
there is no pointer and node can be accessed through index. But it
is not suitable to use because insertion and deletion creates more
data movements. So we go for another method i.e. linked
representation. In the next topics readers will find how to
represent tree in linked format.
| Inorder Traversal | In a inorder traversal, work at a node is performed after processing it's left child and before processing it's right child. For example, inorder traversal is:D B F E A G C K J H L which is shown in Fig 1. |
|---|---|
| Preorder Traversal | In a preorder traversal, work at a node is performed before (pre) its children are processed. For example, preorder traversal is: A B D E F C G H J K L which is shown in Fig 1. |
| Postorder Traversal | In a postorder traversal, the work at a node is performed after (post) its children are evaluated. For example, postorder traversal is: D F E B G K J L H C which is shown in Fig 1. |
Now as we have familiar with traversal of binary tree we will construct the tree from different traversals. Here we will consider two cases.
Case 1:
In order: E A K C F H D B G
Pre order: F A E C K D H G B
How to construct tree from these two traversal is given below in following Fig 2.
Fig. construct tree form inorder-preorder traversal
Post order: H D I E B J F K L G C A
In order: H D B I E A F J C K G L
How to construct tree from these two traversal is given below in following Fig 3.
Source code is given below to construct tree from different traversal.
Creating Tree From Different Traversal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
#include <stdio.h>
#include <stdlib.h>
#define MAX 50
struct node
{
int data;
struct node* left;
struct node* right;
};
int search(int *arr, int , int , int );
struct node* newNode(int data);
/* Recursive function to construct binary of size len from
Inorder traversal in[] and Preorder traversal pre[]. */
struct node* buildTree(int *in, int *pre, int inStart, int inEnd)
{
static int preIndex = 0;
if(inStart > inEnd)
return NULL;
/* Pick current node from Preorder traversal using preIndex
and increment preIndex */
struct node *tNode = newNode(pre[preIndex++]);
/* If this node has no children then return */
if(inStart == inEnd)
return tNode;
/* Else find the index of this node in Inorder traversal */
int inIndex = search(in, inStart, inEnd, tNode->data);
/* Using index in Inorder traversal, construct left and
right subtress */
tNode->left = buildTree(in, pre, inStart, inIndex-1);
tNode->right = buildTree(in, pre, inIndex+1, inEnd);
return tNode;
}
/* when we consider inorder and postorder traversal*/
struct node* buildTree1(int *in, int *post, int inStart, int inEnd,int postStart,int postEnd)
{
if(inStart > inEnd || postStart>postEnd)
return NULL;
int rootValue=post[postEnd];
/* Pick current node from Preorder traversal using preIndex
and increment preIndex */
struct node *tNode = newNode(rootValue);
/* find the index of this node in Inorder traversal */
int inIndex = search(in, inStart, inEnd, rootValue);
/* Using index in Inorder traversal, construct left and
right subtress */
tNode->left = buildTree1(in, post, inStart, inIndex-1,postStart,postStart+inIndex-(inStart+1));
tNode->right = buildTree1(in, post, inIndex+1, inEnd,postStart+inIndex-inStart,postEnd-1);
return tNode;
}
/* Function to find index of value in arr[start...end]
The function assumes that value is present in in[] */
int search(int *arr, int start, int end, int value)
{
int i;
for(i = start; i <= end; i++)
{
if(arr[i] == value)
return i;
}
}
/* function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/* This funtcion is here just to test buildTree() */
void printpostorder(struct node* node)
{
if (node == NULL)
return;
/* first recur on left child */
printpostorder(node->left);
/* now recur on right child */
printpostorder(node->right);
/* then print the data of node */
printf("%d|", node->data);
}
void printpreorder(struct node* node)
{
if (node == NULL)
return;
/* print data of node */
printf("%d|",node->data);
/* now recur on left child */
printpreorder(node->left);
/* now recur on right child */
printpreorder(node->right);
}
int main()
{
int *in,*pre,*post;
int i,n,len,ch,j,temp;
in=(int *)malloc(sizeof(int)*MAX);
pre=(int *)malloc(sizeof(int)*MAX);
post=(int *)malloc(sizeof(int)*MAX);
while(1)
{
printf("\n1.inorder and preorder traversal is given");
printf("\n2.inorder and postorder traversal is given");
printf("\n3.exit");
printf("\nenter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("\nEnter how many numbers you will put:");
scanf("%d",&n);
printf("\nenter the inorder traversal:");
for(i=0;i < n;i++)
scanf("%d",&in[i]);
printf("\nenter the preorder traversal:");
for(i=0;i < n;i++)
scanf("%d",&pre[i]);
len=n;
struct node *root = buildTree(in, pre, 0, len - 1);
printf("\npostorder traversal of the constructed tree is:");
printpostorder(root);
break;
case 2: printf("\nEnter how many numbers you will put:");
scanf("%d",&n);
printf("\nenter the inorder traversal:");
for(i=0;i < n;i++)
scanf("%d",&in[i]);
printf("\nenter the postorder traversal:");
for(i=0;i < n;i++)
scanf("%d",&post[i]);
len=n;
struct node *rt = buildTree1(in, post,0,len-1,0,len-1);
printf("\npreorder traversal of the constructed tree is:");
printpreorder(rt);
break;
case 3: return 0;
}
}
Posts
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.