Using the tree program, write a program to input twenty integers into a tree. Th
ID: 3573252 • Letter: U
Question
Using the tree program, write a program to input twenty integers into a tree.
The program should print out the inorder, preorder and postorder traversals for the tree indicating the LEVEL of each node as it is printed out.
In addition to that there should be statements indicating :
The number of leaves in the tree
The number of nodes with only one child
The number of nodes with two children
The maximum and minimum leaf levels
The height of the tree
Also indicate if the tree is balanced
For Example…if you entered the values
45
3
66
7
8
99
23
11
44
55
6
2
88
9
0
32
14
103
92
The tree program I gave you would print out that the root is 45, that 3 is the left of 45,
66 is the right of 45, etc etc…
It would then do the inorder traversal:
0 (level 3)
2 (level2)
3 (level1)
6 (level 3)
etc
Then you would say (not necessarily correct) something like:
There are 8 leaf nodes
There are 4 nodes with one child
There are 7 nodes with two children
Maximum leaf level = 6
Maximum leaf level = 3
not balanced...height = 6
Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
struct node
{
int value;
node* l;
node* r;
};
struct node* root;
struct node* insert(struct node* r, int value);
void inorderTraversal(struct node* r);
void preorderTraversal(struct node* r);
void postorderTraversal(struct node* r);
int FindLevel(struct node *node, int value);
unsigned int LeafCount(struct node* node);
int main()
{
root = NULL;
int n, v;
n=20;
int arr[100];
for(int i=0; i<n; i++){
printf("Data %d: ", i+1);
scanf("%d", &v);
arr[i]=v;
root = insert(root, v);
}
printf("Inorder Traversal: ");
inorderTraversal(root);
printf(" ");
printf("Preorder Traversal: ");
preorderTraversal(root);
printf(" ");
printf("Postorder Traversal: ");
postorderTraversal(root);
printf(" ");
for(int i=0;i<n;i++)
printf("%d (level %d) ",arr[i],FindLevel(root,arr[i]));
printf("There are %d Leaves in BST ",LeafCount(root));
return 0;
}
unsigned int LeafCount(struct node* node)
{
if(node == NULL)
return 0;
if(node->l == NULL && node->r==NULL)
return 1;
else
return LeafCount(node->l)+
LeafCount(node->r);
}
struct node* insert(struct node* r, int value)
{
if(r==NULL)
{
r = (struct node*) malloc(sizeof(struct node));
r->value = value;
r->l = NULL;
r->r = NULL;
}
else if(value < r->value){
r->l = insert(r->l, value);
}
else {
r->r = insert(r->r, value);
}
return r;
}
void inorderTraversal(struct node* r)
{
if(r!=NULL){
inorderTraversal(r->l);
printf("%d ", r->value);
inorderTraversal(r->r);
}
}
void preorderTraversal(struct node* r)
{
if(r!=NULL){
printf("%d ", r->value);
preorderTraversal(r->l);
preorderTraversal(r->r);
}
}
void postorderTraversal(struct node* r)
{
if(r!=NULL){
postorderTraversal(r->l);
postorderTraversal(r->r);
printf("%d ", r->value);
}
}
int FindLevelUtil(struct node *node, int value, int level)
{
if (node == NULL)
return 0;
if (node->value == value)
return level;
int downlevel = FindLevelUtil(node->l, value, level+1);
if (downlevel != 0)
return downlevel;
downlevel = FindLevelUtil(node->r, value, level+1);
return downlevel;
}
int FindLevel(struct node *node, int value)
{
return FindLevelUtil(node,value,1);
}
==================================================================
Output:
akshay@akshay-Inspiron-3537:~/Chegg$ gcc bbb.cpp
akshay@akshay-Inspiron-3537:~/Chegg$ ./a.out
Data 1: 1
Data 2: 2
Data 3: 3
Data 4: 4
Data 5: 5
Data 6: 6
Data 7: 7
Data 8: 8
Data 9: 9
Data 10: 10
Data 11: 11
Data 12: 12
Data 13: 13
Data 14: 14
Data 15: 15
Data 16: 16
Data 17: 17
Data 18: 18
Data 19: 19
Data 20: 20
Inorder Traversal: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Preorder Traversal: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Postorder Traversal: 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
1 (level 1)
2 (level 2)
3 (level 3)
4 (level 4)
5 (level 5)
6 (level 6)
7 (level 7)
8 (level 8)
9 (level 9)
10 (level 10)
11 (level 11)
12 (level 12)
13 (level 13)
14 (level 14)
15 (level 15)
16 (level 16)
17 (level 17)
18 (level 18)
19 (level 19)
20 (level 20)
There are 1 Leaves in BST
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.