QuestionQuestion

Transcribed TextTranscribed Text

Assignment 7 Objectives • Binary tree data structures and operations • BST and application Basic binary tree data structure and operations Write C programs tree.h, tree.c to test binary a tree data structure. tree.h and tree.c contain the following data type definition, function prototypes and implementations. 1. design and implement a general binary tree data structure with the following features. typedef struct tree_node { int data; struct tree_node *left; struct tree_node *right; } TNODE; void insert_tree(TNODE **root, int val); /* creates a TNODE node and sets the data to value and returns the pointer */ TNODE *new_node(int value); /* this computes and returns the number of node count of the tree passed by root.*/ int get_count(TNODE *root); /* this computes and returns the number of the tree passed by root. */ int get_height(TNODE *root); /* this cleans the tree passed by rootp. */ void clean_tree(TNODE **rootp); /* this displays the node data of the tree by pre-order. */ void display_preorder(TNODE *root); /* this displays the node data of the tree by in-order. */ void display_inorder(TNODE *root); /* this displays the node data of the tree by post-order. */ void display_postorder(TNODE *root); /* this displays the tree in 2D text format */ void display_tree(TNODE *root, int prelen); /* this displays the tree in breadth-first order using additional queue data structure */ void iterative_bf_display(TNODE *root); /* this does the breadth-first search */ TNODE *iterative_bf_search(TNODE *root, int val); /* this does the depth-first search */ TNODE *iterative_df_search(TNODE *root, int val); You need to use auxiliary queue/stack data structures to implement the iterative breadth-first/depth-first traversal and search algorithms. Use the provided main program a7q1.c to test the above programs. The main function program creates the tree in the following diagram. tree diagram public test gcc tree.c a7q1.c -o a7q1 a7q1 display_tree |___A |___C |___G |___F |___B |___E |___D node count: 7 tree height: 3 display_preorder: A B D E C F G display_postorde: D E B F G C A display_inorder: D B E A F C G iterative_bf_display: A B C D E F G iterative_bf_search: F found: F iterative_bf_search: H not found: H iterative_df_search: G found: G BST with application Write a C program, named bst.h, bst.c, markstats.h, markstats.c, to store mark records by BST and to simple data statistics and hybrid data structure. The mark records are provided in file marks.txt. 1. bst.h and bst.c contain the definition of BST structure and functions, using the name field as key for search, insert and delete operations. typedef struct record { char name[40]; float score; } RECORD; typedef struct node { RECORD data; struct node *left; struct node *right; } TNODE; /* search bst by data.name */ TNODE *search(TNODE *root, char *name); /* insert record (name, score) into bst using data.name as key */ void insert(TNODE **rootp, char *name, float score); /* delete node of data.name from bst */ void delete(TNODE **rootp, char *name); /* get and return and delete the node of the smallest data.name node from the bst */ TNODE *extract_smallest_node(TNODE **rootp); /* display bst tree data by in-order */ void display_inorder(TNODE *root); /* clean the tree */ void clean_tree(TNODE **rootp); 2. markstats.h and markstats.c contain the following definition of mark and stats data structure, and operation functions. typedef struct mark_stats { TNODE *bst; int count; float mean; float stddev; } MARKS; /* add a record (name, score) into the bst and update the stats info incrementally */ void add_data(MARKS *dsp, char *name, float score); /* delete a record of name from the bst and update the stats info incrementally */ void remove_data(MARKS *dsp, char *name); void import_data(MARKS *dsp, char *filename); void report_data(MARKS *dsp, char *filename); void print_to_file_inorder(TNODE *root, FILE *filename); void display_marks(MARKS *dsp); void clean_marks(MARKS *dsp); char letter_grade(float score); public test Use the provided the main function program a7q2.c to test the above functions. gcc bst.c markstats.c a7q2.c -o a7q2 a7q2 If this marks.txt is used, the output file should be like this report.txt, and screen output is the like screen

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

#include <stdio.h>
#include <stdlib.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;
}
int get_count(TNODE *root) {
// your implementation;
if (root) {
return get_count(root->left) + get_count(root->right) + 1;
} else {
return 0;
}
}
int get_height(TNODE *root) {
if (root) {
int leftHeight = get_height(root->left);
int rightHeight = get_height(root->right);
if (leftHeight > rightHeight) {
return leftHeight+1;
} else {
return rightHeight+1;
}
} else {
return 0;
}
}
void clean_tree(TNODE **rootp) {
TNODE *root = *rootp;
if (root) {
if (root->left)
clean_tree(&root->left);
if (root->right)
clean_tree(&root->right);
free(root);
}
*rootp = NULL;
}
void display_preorder(TNODE *root) {
if (root) {
printf("%c ", root->data);
if (root->left) display_preorder(root->left);
if (root->right) display_preorder(root->right);
}
}
void display_inorder(TNODE *root) {
if (root) {
if (root->left) display_inorder(root->left);
printf("%c ", root->data);
if (root->right) display_inorder(root->right);
}
}
void display_postorder(TNODE *root) {
if (root) {
if (root->left) display_postorder(root->left);
if (root->right) display_postorder(root->right);
printf("%c ", root->data);
}
}
void display_tree(TNODE *root, int prelen) {
if (root) {
int i;
for (i = 0; i < prelen; i++)
printf("%c", ' ');
printf("%s", "|___");
printf("%c\n", root->data);
display_tree(root->right, prelen + 4);
display_tree(root->left, prelen + 4);
}
}
/* use auxiliary queue data structure for the algorithm */
void iterative_bf_display(TNODE *root) {
if (root != NULL) {
TNODE *tp;
QUEUE queue = {0}; // auxiliary queue
enqueue(&queue, root);
while (queue.front) {
tp = dequeue(&queue);
printf("%c ", tp->data);
if (tp->left) {
enqueue(&queue, tp->left);
}
if (tp->right) {
enqueue(&queue, tp->right);
}
}
}
}
/* use auxiliary queue data structure for the algorithm */...

By purchasing this solution you'll be able to access the following files:
a7.zip.

$45.00
for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Computer Science - Other Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats