Exercise: 1. Write a program to implement a complete binary tree using Linked lists. The programs should include functions to perform the following operations: a. Insert(): inserts a new item to the complete binary tree. The items are of integer type. b. Height(): returns the height of a node recursively. c. Preorder(): returns the preorder traversal sequence of the binary tree. Use recursive implementation. d. Postorder(): returns the postorder traversal sequence of the binary tree. Use recursive implementation. e. Inorder(): returns the inorder traversal sequence of the binary tree. Use recursive implementation. f. Levelorder(): returns the level order traversal sequence of the binary tree.

The code is: #include #include

struct node{ struct node*lchild; int data; struct node*rchild; }*root=NULL;

typedef struct{ int top; int size; struct node **p; }stack;

typedef struct{ int size; int front; int rear; struct node **Q; }queue;

void form(queue*q){ q->size=100; q->front=0; q->rear=0; q->Q=(struct node **)malloc(q->size*sizeof(struct node*));

} void enq(queue*q,struct node*x){ if((q->rear+1)%q->size==q->front) printf("q full"); else{ q->rear=(q->rear +1)%(q->size); q->Q[q->rear]=x; } }

struct node*deq(queue*q){ if(q->front==q->rear) printf("q empty");

else{ struct node*x=NULL; q->front=(q->front+1)%q->size; x=q->Q[q->front]; return x; } }

int isEmpty(queue q){ return q.front==q.rear; }

stack s; queue q;

void make(struct node*p){ struct node*a; struct node*b; queue Q; form(&Q); int x;

root=(struct node*)malloc(sizeof(struct node)); root->data=10; root->lchild=root->rchild=NULL; enq(&Q,root); p=root; while(!isEmpty(Q)){ b=deq(&Q); printf("enter lc of %d ",b->data); scanf("%d",&x); if(x!=-1){ a=(struct node*)malloc(sizeof(struct node)); a->data=x; a->lchild=NULL; a->rchild=NULL; p->lchild=a; p=a; enq(&Q,a); }

printf("enter rc of %d ",b->data); scanf("%d",&x); if(x!=-1){ a=(struct node*)malloc(sizeof(struct node)); a->data=x; a->lchild=NULL; a->rchild=NULL; p->rchild=a; p=a; enq(&Q,a); }

}

}

void insert(int key){ struct node*p=root; struct node*q=NULL; while(p){ q=p; p=p->lchild; } struct node*a=(struct node*)malloc(sizeof(struct node)); a->data=key; a->lchild=a->rchild=NULL; q->lchild=a; }

void preorder(struct node*p){ if(p){ printf("%d ",p->data); preorder(p->lchild); preorder(p->rchild); } }

void postorder(struct node*p){ if(p){ postorder(p->lchild); postorder(p->rchild); printf("%d ",p->data); } }

void inorder(struct node*p){ if(p){ inorder(p->lchild); printf("%d ",p->data); inorder(p->rchild); } }

void lvlorder(struct node*p){ enq(&q,p); printf("%d ",p->data); while(!isEmpty(q)){ struct node*x=deq(&q); if(x->lchild!=NULL){ printf("%d ",x->lchild->data); enq(&q,x->lchild); } if(x->rchild!=NULL){ printf("%d ",x->rchild->data); enq(&q,x->rchild); } }

}

int count(struct node*p){ int x=0,y=0; struct node*q=p; if(p){ x=count(p->lchild); if(p->lchild==NULL && p->rchild==NULL) x++; } if(q){ y=count(q->rchild); if(p->lchild==NULL && p->rchild==NULL) y++; } return (y+x); } int ht(int x){ static int c=0; if(x>1){ c++; return ht(x/2); }

return c; }

int main(){

form(&q); make(root); //insert(13); //preorder(root); //postorder(root); int a=count(root); //printf("%d",ht(a)); lvlorder(root);

return 0; }

Explain the code line by line with logic and explain the connection with question