Homework SourseNeed help with this Please give short explanation a What are
Need help with this. Please give short explanation.
a. What are the ancestors of node J?
b. What are the descendants of node T?
c. What are the descendants of node B?
d. What is the order in which the nodes are visited by a preorder traversal?
e. What is the order in which the nodes are visited by a postorder traversal?
Need help with this. Please give short explanation. a. What are the ancestors of node J? b. What are the descendants of node T? c. What are the descendants of node B? d. What is the order in which the nodes are visited by a preorder traversal? e. What is the order in which the nodes are visited by a postorder traversal?Solution
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
# include <stdio.h>
# include <conio.h>
# include <stdlib.h>
typedef struct BST {
int data;
struct BST *lchild, *rchild;
} node;
void insert(node *, node *);
void inorder(node *);
void preorder(node *);
void postorder(node *);
node *search(node *, int, node **);
void main() {
int choice;
char ans = \'N\';
int key;
node *new_node, *root, *tmp, *parent;
node *get_node();
root = NULL;
clrscr();
printf(\"\ Program For Binary Search Tree \");
do {
printf(\"\ 1.Create\");
printf(\"\ 2.Search\");
printf(\"\ 3.Recursive Traversals\");
printf(\"\ 4.Exit\");
printf(\"\ Enter your choice :\");
scanf(\"%d\", &choice);
switch (choice) {
case 1:
do {
new_node = get_node();
printf(\"\ Enter The Element \");
scanf(\"%d\", &new_node->data);
if (root == NULL) /* Tree is not Created */
root = new_node;
else
insert(root, new_node);
printf(\"\ Want To enter More Elements?(y/n)\");
ans = getch();
} while (ans == \'y\');
break;
case 2:
printf(\"\ Enter Element to be searched :\");
scanf(\"%d\", &key);
tmp = search(root, key, &parent);
printf(\"\ Parent of node %d is %d\", tmp->data, parent->data);
break;
case 3:
if (root == NULL)
printf(\"Tree Is Not Created\");
else {
printf(\"\ The Inorder display : \");
inorder(root);
printf(\"\ The Preorder display : \");
preorder(root);
printf(\"\ The Postorder display : \");
postorder(root);
}
break;
}
} while (choice != 4);
}
/*
Get new Node
*/
node *get_node() {
node *temp;
temp = (node *) malloc(sizeof(node));
temp->lchild = NULL;
temp->rchild = NULL;
return temp;
}
/*
This function is for creating a binary search tree
*/
void insert(node *root, node *new_node) {
if (new_node->data < root->data) {
if (root->lchild == NULL)
root->lchild = new_node;
else
insert(root->lchild, new_node);
}
if (new_node->data > root->data) {
if (root->rchild == NULL)
root->rchild = new_node;
else
insert(root->rchild, new_node);
}
}
/*
This function is for searching the node from
binary Search Tree
*/
node *search(node *root, int key, node **parent) {
node *temp;
temp = root;
while (temp != NULL) {
if (temp->data == key) {
printf(\"\ The %d Element is Present\", temp->data);
return temp;
}
*parent = temp;
if (temp->data > key)
temp = temp->lchild;
else
temp = temp->rchild;
}
return NULL;
}
/*
This function displays the tree in inorder fashion
*/
void inorder(node *temp) {
if (temp != NULL) {
inorder(temp->lchild);
printf(\"%d\", temp->data);
inorder(temp->rchild);
}
}
/*
This function displays the tree in preorder fashion
*/
void preorder(node *temp) {
if (temp != NULL) {
printf(\"%d\", temp->data);
preorder(temp->lchild);
preorder(temp->rchild);
}
}
/*
This function displays the tree in postorder fashion
*/
void postorder(node *temp) {
if (temp != NULL) {
postorder(temp->lchild);
postorder(temp->rchild);
printf(\"%d\", temp->data);
}
}
| 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 | # include <stdio.h> # include <conio.h> # include <stdlib.h> typedef struct BST { int data; struct BST *lchild, *rchild; } node; void insert(node *, node *); void inorder(node *); void preorder(node *); void postorder(node *); node *search(node *, int, node **); void main() { int choice; char ans = \'N\'; int key; node *new_node, *root, *tmp, *parent; node *get_node(); root = NULL; clrscr(); printf(\"\ Program For Binary Search Tree \"); do { printf(\"\ 1.Create\"); printf(\"\ 2.Search\"); printf(\"\ 3.Recursive Traversals\"); printf(\"\ 4.Exit\"); printf(\"\ Enter your choice :\"); scanf(\"%d\", &choice); switch (choice) { case 1: do { new_node = get_node(); printf(\"\ Enter The Element \"); scanf(\"%d\", &new_node->data); if (root == NULL) /* Tree is not Created */ root = new_node; else insert(root, new_node); printf(\"\ Want To enter More Elements?(y/n)\"); ans = getch(); } while (ans == \'y\'); break; case 2: printf(\"\ Enter Element to be searched :\"); scanf(\"%d\", &key); tmp = search(root, key, &parent); printf(\"\ Parent of node %d is %d\", tmp->data, parent->data); break; case 3: if (root == NULL) printf(\"Tree Is Not Created\"); else { printf(\"\ The Inorder display : \"); inorder(root); printf(\"\ The Preorder display : \"); preorder(root); printf(\"\ The Postorder display : \"); postorder(root); } break; } } while (choice != 4); } /* Get new Node */ node *get_node() { node *temp; temp = (node *) malloc(sizeof(node)); temp->lchild = NULL; temp->rchild = NULL; return temp; } /* This function is for creating a binary search tree */ void insert(node *root, node *new_node) { if (new_node->data < root->data) { if (root->lchild == NULL) root->lchild = new_node; else insert(root->lchild, new_node); } if (new_node->data > root->data) { if (root->rchild == NULL) root->rchild = new_node; else insert(root->rchild, new_node); } } /* This function is for searching the node from binary Search Tree */ node *search(node *root, int key, node **parent) { node *temp; temp = root; while (temp != NULL) { if (temp->data == key) { printf(\"\ The %d Element is Present\", temp->data); return temp; } *parent = temp; if (temp->data > key) temp = temp->lchild; else temp = temp->rchild; } return NULL; } /* This function displays the tree in inorder fashion */ void inorder(node *temp) { if (temp != NULL) { inorder(temp->lchild); printf(\"%d\", temp->data); inorder(temp->rchild); } } /* This function displays the tree in preorder fashion */ void preorder(node *temp) { if (temp != NULL) { printf(\"%d\", temp->data); preorder(temp->lchild); preorder(temp->rchild); } } /* This function displays the tree in postorder fashion */ void postorder(node *temp) { if (temp != NULL) { postorder(temp->lchild); postorder(temp->rchild); printf(\"%d\", temp->data); } } |
