Binary Tree Program
//
// main.c
// binary-tree
//
// Created by shivah on 3/17/20.
// Copyright © 2020 shivah. All rights reserved.
//
#include <stdio.h>
#include <stdlib.h>
struct node{
int info;
struct node *left;
struct node *right;
};
int a[7] = {0,0,0,0,0,0,0};
int i = 0;
void insert(struct node **sr, int num){
if( (*sr) == NULL ){
(*sr) = (struct node *)malloc(sizeof(struct node));
(*sr)->info = num;
(*sr)->left = (*sr)->right = NULL;
return;
}else if( num < (*sr)->info ){
insert( &((*sr)->left), num);
}else{
insert( &((*sr)->right), num);
}
return;
}
void inorder(struct node *sr){
if( sr == NULL){
//printf("Empty tree\n");
return;
}else{
inorder(sr->left);
printf("element=%d\n", sr->info);
inorder(sr->right);
}
}
void printKDistant(struct node *root , int k)
{
if(root == NULL){
return;
}
if(k == 0){
printf("%d\t", root->info);
return;
}else{
printKDistant(root->left, k-1);
printKDistant(root->right, k-1);
}
}
void kpreorder(struct node *sr){
if( sr == NULL){
//printf("Empty tree\n");
return;
}else{
a[i] = sr->info;
i++;
printf("element=%d i =%d \n", sr->info, i);
kpreorder(sr->left);
kpreorder(sr->right);
}
}
int node_count(struct node *sr){
int x = 0, y = 0;
if(sr == NULL){
return 0;
}else{
x = node_count(sr->left);
y = node_count(sr->right);
return(x+y+1);
}
return 0;
}
int degree2_node_count(struct node *sr){
int x = 0, y = 0, z= 0;
if(sr == NULL){
return 0;
}else{
x = degree2_node_count(sr->left);
y = degree2_node_count(sr->right);
if( (sr->left != NULL ) && (sr->right != NULL) ){
return(x+y+1);
}else{
return(x+y);
}
}
return 0;
}
int leaf_node_count(struct node *sr){
int x = 0, y = 0;
if(sr == NULL){
return 0;
}else{
x = leaf_node_count(sr->left);
y = leaf_node_count(sr->right);
if( (sr->left == NULL ) && (sr->right == NULL) ){
return(x+y+1);
}else{
return(x+y);
}
}
return 0;
}
//Sum of the all the tree node info
int sum_all_node(struct node *sr){
int x = 0, y = 0;
if(sr == NULL){
return 0;
}else{
x = sum_all_node(sr->left);
y = sum_all_node(sr->right);
return(x+y+sr->info);
}
return 0;
}
//return sum of node in which
int max_left_right_node(struct node *sr){
int x = 0, y = 0;
if(sr == NULL){
return 0;
}else{
x = max_left_right_node(sr->left);
y = max_left_right_node(sr->right);
if(x > y)
return x+1;
else
return(y+1);
}
return 0;
}
//Count Number of Unival Subtrees
int universal_subtree(struct node *sr){
int x = 0, y = 0;
if(sr == NULL){
return 0;
}else{
x = universal_subtree(sr->left);
y = universal_subtree(sr->right);
if ( ( (sr->left == NULL) && (sr->right == NULL)) )
return(x+y+1);
else if( ( (sr->left != NULL) && (sr->right != NULL) ) ) {
if ( ( sr->info == sr->left->info == sr->right->info ) )
return(x+y+1);
}
else
return(x+y);
}
return 0;
}
void pconstruct(struct node *sr){
}
int main(int argc, const char * argv[]) {
struct node *root = NULL;
insert(&root,15);
insert(&root, 10);
insert(&root, 20);
insert(&root, 8);
insert(&root, 19);
insert(&root,20);
insert(&root,11);
// insert(&root,11);
// insert(&root,21);
//Count number of nodes
printf("number of node in the tree is = %d\n", node_count(root));
printf("number of node of degree2 in the tree is = %d\n", degree2_node_count(root));
printf("number of leaf node in the tree is = %d\n", leaf_node_count(root));
printf("Sum of the all the node value in the tree is = %d\n", sum_all_node(root));
printf("max number of the left and right node in the tree is = %d\n", max_left_right_node(root));
printf("Number of the universal sub tree is = %d\n", universal_subtree(root));
inorder(root);
printf("preorder \n");
kpreorder(root);
printf("\n");
//printKDistant(root, 1);
for(i = 0; i< 7; i++){
printf("%d\t", a[i]);
}
return 0;
}
Comments
Post a Comment