This problem has been solved!

See the answer

Write C programs tree.h, tree.c to implement binary a tree data structure and basic operations. Header tree.h contains the following definitions of data types function prototypes, tree.c implements functions in tree.h using auxiliary queue and stack data structures given in queue_stack.h.

Design and implement a general binary tree data structure with the following features.

/* node structure of a binary tree */

typedef struct tnode {

int data;

struct tnode *left;

struct tnode *right;

} TNODE;

/* a structure to represent tree properties: order and height */

typedef struct tree_props {

int order; // as the number of nodes in a tree

int height; // as the height of a tree

} TPROPS;

/* this creates a TNODE node and sets the data to value and returns the pointer */

TNODE *new_node(int value);

/* this cleans the tree passed by address root pointer. */

void clean_tree(TNODE **rootp);

/* this computes and returns TPROPS value containing the number of nodes and height

* of tree passed by root address.

*/

TPROPS get_props(TNODE *root);

/* this displays the node data of the tree in pre-order. */

void display_preorder(TNODE *root);

/* this displays the node data of the tree in in-order. */

void display_inorder(TNODE *root);

/* this displays the node data of the tree in post-order. */

void display_postorder(TNODE *root);

/* this displays the tree in breadth-first-order using an auxiliary queue. */

void display_bforder(TNODE *root);

/* this does the breadth-first-search using an auxiliary queue. */

TNODE *iterative_bfs(TNODE *root, int val);

/* this does the depth-first-search using an auxiliary stack */

TNODE *iterative_dfs(TNODE *root, int val);

/* this inserts nodes into a complete binary tree using an auxiliary queue. */

void insert_complete(TNODE **rootp, int val);

Use the provided public test driver program tree_main.c to test the above programs, the output is as the following.

Public test

gcc tree.c tree_main.c -o q1

q1

display_tree():

|___:A

|___R:C

|___R:G

|___L:F

|___L:B

|___R:E

|___L:D

get_props().order:7

get_props().height:3

display_preorder():A B D E C F G

display_postorder():D E B F G C A

display_inorder():D B E A F C G

display_bforder(root):A B C D E F G

iterative_bfs(F):F

iterative_bfs(H):NULL

iterative_dfs(F):F

iterative_dfs(H):NULL

clean get_props().order:0

get_props().height:0

tree.h

#ifndef TREE_H

#define TREE_H

/* node structure of a binary tree */

typedef struct tnode {

int data;

struct tnode *left;

struct tnode *right;

} TNODE;

/* a structure to represent tree properties: order and height */

typedef struct tree_props {

int order; // as the number of nodes in a tree

int height; // as the height of a tree

} TPROPS;

/* this creates a TNODE node and sets the data to value and returns the pointer */

TNODE *new_node(int value);

/* this computes and returns TPROPS value containing the number of nodes and height

* of tree passed by root address.

*/

TPROPS get_props(TNODE *root);

/* this displays the node data of the tree in pre-order. */

void display_preorder(TNODE *root);

/* this displays the node data of the tree in in-order. */

void display_inorder(TNODE *root);

/* this displays the node data of the tree in post-order. */

void display_postorder(TNODE *root);

/* this displays the tree in breadth-first-order using an auxiliary queue. */

void display_bforder(TNODE *root);

/* this does the breadth-first-search using an auxiliary queue. */

TNODE *iterative_bfs(TNODE *root, int val);

/* this does the depth-first-search using an auxiliary stack */

TNODE *iterative_dfs(TNODE *root, int val);

/* this cleans the tree passed by address root pointer. */

void clean_tree(TNODE **rootp);

/* this inserts nodes into a complete binary tree using an auxiliary queue. */

void insert_complete(TNODE **rootp, int val);

#endif

tree.c

#include

#include

#include \"queue_stack.h\"

#include \"tree.h\"

TNODE *new_node(int value) {

TNODE *np = (TNODE *) malloc(sizeof(TNODE));

if (np == NULL) return NULL;

np->data = value;

np->left = NULL;

np->right = NULL;

return np;

}

TPROPS get_props(TNODE *root) {

// your implementation

}

void display_preorder(TNODE *root) {

// your implementation

}

void display_inorder(TNODE *root) {

// your implementation

}

void display_postorder(TNODE *root) {

// your implementation

}

/* use auxiliary queue data structure for the algorithm */

void display_bforder(TNODE *root) {

// your implementation

}

/* use auxiliary queue data structure for the algorithm */

TNODE *iterative_bfs(TNODE *root, int val) {

// your implementation

}

TNODE *iterative_dfs(TNODE *root, int val) {

// your implementation

}

// the following functions are given, need to add to your program.

void clean_tree(TNODE **rootp) {

TNODE *p = *rootp;

if (p) {

if (p->left)

clean_tree(&p->left);

if (p->right)

clean_tree(&p->right);

free(p);

}

*rootp = NULL;

}

void insert_complete(TNODE **rootp, int val){

if( *rootp == NULL) {

*rootp = new_node(val);

} else {

QUEUE queue = {0};

TNODE *p;

enqueue(&queue, *rootp);

while(queue.front){

p = dequeue(&queue);

if(p->left == NULL){

p->left = new_node(val);

break;

} else {

enqueue(&queue, p->left);

}

if(p->right == NULL){

p->right = new_node(val);

break;

} else {

enqueue(&queue, p->right);

}

}

}

}

#ifndef QUEUE_STACK_H

#define QUEUE_STACK_H

#include

#include

// definition

typedef struct node {

void *data; // data pointer

struct node *next;

} NODE;

typedef struct queue {

NODE *front, *rear;

} QUEUE;

void enqueue(QUEUE *qp, void *data);

void *dequeue(QUEUE *qp);

void clean_queue(QUEUE *qp);

typedef struct stack {

NODE *top;

} STACK;

void push(STACK *sp, void *data);

void pop(STACK *sp);

void clean_stack(STACK *sp);

// implementation

void enqueue(QUEUE *qp, void *data) {

NODE *p = (NODE*) malloc(sizeof(NODE));

if (p == NULL) return;

else {

p->data = data;

p->next = NULL;

if (qp->front == NULL) {

qp->front = p;

qp->rear = p;

} else {

(qp->rear)->next = p;

qp->rear = p;

}

}

}

void *dequeue(QUEUE *qp) {

void *temp = NULL;

if (qp->front) {

NODE *p = qp->front;

temp = p->data;

if (qp->front == qp->rear) {

qp->front = NULL;

qp->rear = NULL;

} else {

qp->front = p->next;

}

free(p);

return temp;

}

return NULL;

}

void clean_queue(QUEUE *qp) {

NODE *temp, *p = qp->front;

while (p != NULL) {

temp = p;

p = p->next;

free(temp);

}

qp->front = NULL;

qp->rear = NULL;

}

void push(STACK *sp, void *data) {

NODE *p = (NODE*) malloc(sizeof(NODE));

p->data = data;

p->next = NULL;

if (sp->top == NULL) {

sp->top = p;

} else {

p->next = sp->top;

sp->top = p ;

}

}

void pop(STACK *sp) {

if (sp->top != NULL) {

NODE *p = sp->top;

sp->top = p->next;

free(p);

}

}

void clean_stack(STACK *sp) {

NODE *temp, *p = sp->top;

while (p) {

temp = p;

p = p->next;

free(temp);

}

sp->top = NULL;

}

#endif

#include

#include \"tree.h\"

void search_info(char *sf, char key, TNODE *tnp){

if (tnp)

printf(\" %s(%c):%c\", sf, key, tnp->data);

else

printf(\" %s(%c):NULL\", sf, key);

}

void display_tree(TNODE *root, int pretype, int prelen) {

if (root) {

int i;

for (i = 0; i

printf(\"%c\", ' ');

}

if (pretype == 0)

printf(\"%s\", \"|___:\");

else if (pretype == 1)

printf(\"%s\", \"|___L:\");

else if (pretype == 2)

printf(\"%s\", \"|___R:\");

printf(\"%c \", root->data);

display_tree(root->right, 2, prelen + 4);

display_tree(root->left, 1, prelen + 4);

}

}

int main() {

TNODE *root = NULL;

int i;

for ( i = 0; i7;>

insert_complete(&root, i+'A');

}

printf(\" display_tree(): \");

display_tree(root, 0, 0);

printf(\"%s:%d \", \"get_props().order\", get_props(root).order);

printf(\"%s:%d \", \"get_props().height\", get_props(root).height);

printf(\"%s:\", \"display_preorder()\");

display_preorder(root);

printf(\" %s:\", \"display_postorder()\");

display_postorder(root);

printf(\" %s:\", \"display_inorder()\");

display_inorder(root);

printf(\" %s:\", \"display_bforder(root)\");

display_bforder(root);

// testing iterative_bfs function

char key = 'F';

TNODE *tnp = iterative_bfs(root, key);

search_info(\"iterative_bfs\", key, tnp);

key = 'H';

tnp = iterative_bfs(root, key);

search_info(\"iterative_bfs\", key, tnp);

// testing iterative_bfs function

key = 'F';

tnp = iterative_dfs(root, key);

search_info(\"iterative_dfs\", key, tnp);

key = 'H';

tnp = iterative_dfs(root, key);

search_info(\"iterative_dfs\", key, tnp);

clean_tree(&root);

printf(\" %s:%d\", \"clean get_props().order\", get_props(root).order);

printf(\" %s:%d \", \"get_props().height\", get_props(root).height);

return 0;

]