-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathComplete Binary Tree and Traversals
136 lines (121 loc) · 3.27 KB
/
Complete Binary Tree and Traversals
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
Implement a C program to construct a Complete Binary Tree and also display the elements in the tree using Inorder , Preorder and Postorder traversals.
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
struct tree
{
int data;
struct tree *right,*left;
};
struct queue
{
int front, rear;
int size;
struct tree* *array;
};
struct tree* newNode(int data);
struct queue* createQueue(int size);
void enqueue(struct tree *root, struct queue* queue);
struct tree* dequeue(struct queue* queue);
void insert(struct tree **root, int data, struct queue* queue);
void inorder(struct tree *);
void preorder(struct tree *);
void postorder(struct tree *);
int main()
{
struct tree* root = NULL;
char ans[3];
int data;
struct queue* queue = createQueue(50);
do
{
printf("Enter the element to be inserted in the tree\n");
scanf("%d",&data);
insert(&root, data, queue);
printf("Do you want to insert another element?\n");
scanf("%s",ans);
} while (strcmp(ans,"yes") ==0);
printf("Inorder Traversal : The elements in the tree are");
inorder(root);
printf("\n");
printf("Preorder Traversal : The elements in the tree are");
preorder(root);
printf("\n");
printf("Postorder Traversal : The elements in the tree are");
postorder(root);
return 0;
}
struct tree* newNode(int data)
{
struct tree *nn = (struct tree*)malloc(sizeof(struct tree));
nn->data = data;
nn->left = NULL;
nn->right = NULL;
return nn;
}
struct queue* createQueue(int size)
{
struct queue* queue = (struct queue*)malloc(sizeof(struct queue));
queue->size = size;
queue->front = -1;
queue->rear = -1;
queue->array = (struct tree**)malloc(size*sizeof(struct tree*));
return queue;
}
void insert(struct tree **root, int data, struct queue* queue)
{
struct tree *temp = newNode(data);
if(*root == NULL)
*root = temp;
else{
struct tree *front = queue->array[queue->front];
if(front->left==NULL)
front->left = temp;
else if(front->right == NULL)
front->right = temp;
if(front->left!=NULL && front->right!=NULL)
dequeue(queue);
}
enqueue(temp,queue);
}
void enqueue(struct tree *root, struct queue* queue)
{
if(queue->rear==queue->size-1)
return;
queue->array[++queue->rear] = root;
if(queue->front == -1)
queue->front++;
}
struct tree* dequeue(struct queue* queue)
{
if(queue->front==-1)
return NULL;
struct tree *temp = queue->array[queue->front];
if(queue->front==queue->rear)
queue->rear = queue->front = -1;
else
queue->front++;
return temp;
}
void inorder(struct tree *temp) {
if(temp!=NULL){
inorder(temp->left);
printf(" %d",temp->data);
inorder(temp->right);
}
}
void preorder(struct tree *temp) {
if(temp!=NULL){
printf(" %d",temp->data);
preorder(temp->left);
preorder(temp->right);
}
}
void postorder(struct tree *temp) {
if(temp!=NULL){
postorder(temp->left);
postorder(temp->right);
printf(" %d",temp->data);
}
}