CSCI2100F/ESTR2102B Data Structures (Spring 2022)
Lab Assignment #5
Schedule: Week 8
- To familiarize the implementations of general tree
- To familiarize the tree terminology
Submission guideline (Online judge) - Name your program(s) according to the question (e.g. lab5-q1.c)
- Write your programs under“Desktop/mywork/lab5”
- Duplicate your programs before submission
- Submit your programs under“Desktop/submission/lab5”
- Check the submission folder for your grading report (Be patience, auto grading needs
some time. You can F5 to update the browser.) - Resubmit your work if you cannot receive full score
- Visit“Other Locations/Computer/2100share/lab4”in the VM to download the
starting programs - Version of the gcc compiler in the online judge: C99
- Deadline: 7th March, 2023 (Tuesday)
- Late penalty is 30%, and the judge for lab 5 is closed on 14th March, 2023
(Tuesday). - There will be 5 late days in total for all 10 labs. The late days will be used
automatically if your submission is beyond the deadline and achieve a better score.
Grading scheme (CSCI2100F) - Total score is 100%
- The weighting of each question is marked on the question
- Bonus score is at most 13%
Bonus score: Extra question (13%)
http://www.6daixie.com/contents/13/7597.html
○ Mark given according to the number of correct answers of the question (13%)
Requirements for ESTR2102B: Non-zero scores for the extra question
Useful commands
- Compile your program
gcc -o prog labX-q1.c labX-q1-tc1.c
gcc -o prog labX-q3.c -
Run the program with arguments
○ For data structure implementation:
./prog outputfile.txt
○ For sample input and sample output:
./prog inputfile.txt outputfile.txt
1
Question 1: General Tree – Child-Sibling Implementation (40%)
You are going to implement the general tree abstract data type using left-child right-sibling
design. The header file“lab5-q1.h”and the description of the functions are as follows.
Your program should not contain main(). Name your program as“lab5-q1.c”.
// lab5-q1.h
// Cannot modify this file
typedef struct tree_cs {
int key; / key of the node /
int value; / value stored in the node /
struct tree_cs first_child; / pointer to the first child */
struct tree_cs next_sibling;/ pointer to the next sibling */
} Tree_CS;
/ Initialize the tree with a root #1 /
/ Create a new tree T with initialized root as (key, value) /
void tree_init(Tree_CS **T, int key, int value);
/ Insert (key, value) to the tree T #2 #3 /
/ If key already exist in T, then update the value /
/ If key does not exist in T, /
/ then add (key, value) to the last child of node with parent_key /
void tree_insert(Tree_CS *T, int parent_key, int key, int value);
/ Delete leaf with key from the tree T #4 #5 #6 /
/ If key in T and is a leaf, then delete the node /
/* Note: if it is the first child, then the second child becomes the
first child */
/* Note: it if is in the middle of the sibling, then the list structure
of siblings need to be maintained */
/ If key in T and key is not a leaf, then do nothing /
/ If key does not in T, then do nothing /
void tree_delete(Tree_CS *T, int key);
/ Check if key exist in the tree T or not #7 /
/ If key in T, return 1 /
/ If key not in T, return 0 /
int tree_contain(Tree_CS *T, int key);
/ Find the node based on the key in the tree T #8 /
/ If key in T, return the node of key /
/ If key does not exist in T, return NULL /
Tree_CS tree_find(Tree_CS T, int key);
/ Free the tree T, if T is not NULL #9 /
/ Assign NULL to T after free /
void tree_free(Tree_CS **T);
2
/* The print function print the tree in an output string using preorder
traversal #10 */
/ The number in the bracket is key, number after bracket is value /
/ If the tree looks like /
/ (0)17 /
/ | \ /
/ (1)12 (2)18 /
/ | | \ /
/ (4)0 (3)2 (8)5 /
/ Then, the output string is “(0)17 (1)12 (4)0 (2)18 (3)2 (8)5 ” /
/ You can assume the number of nodes is not more than 100 /
char tree_print(Tree_CS T);
Sample Test Case (lab5-q1-tc1.c):
// This file is named as lab5-q1-tc1.cinclude”lab5-q1.h”
include<stdio.h>
include<stdlib.h>
include<string.h>
include<limits.h>
int main(int argc, char *argv[]){
FILE *fout;
Tree_CS *T;
int isCorrect, i;
fout = fopen(argv[1], “w”);
/ default, your program is correct /
isCorrect = 1;
/ check the function, tree_init() /
T = NULL;
tree_init(&T, 4, 7);
/ if T is not initialized appropriately /
if (T == NULL) {
isCorrect = 0;
} else if (T->key != 4 || T->value != 7 || T->first_child != NULL
|| T->next_sibling != NULL) {
isCorrect = 0;
}
/ output “Correct” if the tree_init() is correctly implemented /
if (isCorrect == 1) {
fprintf(fout, “Tree: Correct\n”);
} else {
fprintf(fout, “Tree: Wrong Answer\n”);
}
fclose(fout);
return 0;
}
3
Question 2: Binary Tree – Array Implementation (30%)
You are going to implement the binary tree abstract data type using array implementation.
The header file“lab5-q2.h”and the description of the functions are as follows.
Your program should not contain main(). Name your program as“lab5-q2.c”.
// lab5-q2.h
// Cannot modify this file
/ Binary tree data structure with array implementation /
/ The first element is stored in (key[0], value[0]) /
/ If key is unused, set key = INT_MAX, value = -2100 /
typedef struct _btree{
int key; / An array of keys for the nodes */
double value; / An array of values for the nodes */
int max_size; / The max number of nodes /
} BTree;
/ Initialize the tree with a root #1 /
/ Create an empty BTree first /
/ The root (key, value) is stored at (key[0], value[0]) /
/ If key is unused, set key = INT_MAX, value = -2100 /
void tree_init(BTree **T, int key, double value, int max_size);
/ Initialize the tree with arrays #2 /
/ Create an empty BTree first /
/ n defines the number of (key,value) pairs of the array /
/ If key is unused, set key = INT_MAX, value = -2100 /
void tree_init_with_array(BTree *T, int key, double *value, int n, int
max_size);
/ Initialize the empty tree with height of root #3 /
/ Based on the height, calculate the max_size /
/ Create an empty BTree with max_size /
/ If key is unused, set key = INT_MAX, value = -2100 /
void tree_init_with_height(BTree **T, int height);
/ Get the index of parent #4 /
/ Return the index of the parent /
/ Return -2100 if the parent index is invalid or unused /
int tree_parent(BTree *T, int child_index);
/ Get the index of left child #5 /
/ Return the index of the left child /
/ Return -2100 if the left child index is invalid or unused /
int tree_lchild(BTree *T, int parent_index);
/ Get the index of right child #6 /
/ Return the index of the right child /
/ Return -2100 if the right child index is invalid or unused /
int tree_rchild(BTree *T, int parent_index);
4
/ Insert or update a node #7 /
/ If key exists in T, update the value /
/ If key not in T, insert (key, double) as left child of parent_index/
/ If the left child cannot be inserted, then do nothing /
/ If the left child is used by other key, then do nothing /
void tree_insert_lchild(BTree *T, int parent_index, int key, double
value);
/ Insert or update a node #8 /
/ If key exists in T, update the value /
/ If key not in T, insert (key,double) as right child of parent_index/
/ If the right child cannot be inserted, then do nothing /
/ If the right child is used by other key, then do nothing /
void tree_insert_rchild(BTree *T, int parent_index, int key, double
value);
/ Find the value based on the key in the tree T or not #9 /
/ If key in T, return the corresponding value /
/ If key not in T, return -2100.00 /
double tree_key_find(BTree *T, int key);
/ Find the value based on the index in the tree T or not #10 /
/ If index is used, return the corresponding value /
/ If index is unused or exceeding the max_size, return -2100.00 /
double tree_index_find(BTree *T, int index);
/ Free the tree T, if T is not NULL #11 /
/ Assign NULL to T after free */
void tree_free(BTree **T);
/* The print function print the tree in an output string using postorder
traversal #12 */
/ The number in the bracket is key, number after bracket is value /
/ If the tree looks like /
/ (0)1.7 /
/ | \ /
/ (1)1.2 (2)1.8 /
/ | | \ /
/ (4)0 (3)2 (6)5 /
/* Then, the output string is “(4)0.00 (1)1.20 (3)2.00 (6)5.00 (2)1.80
(0)1.70 ” */
/ You can assume the number of nodes is not more than 100 /
char tree_print(BTree T);
Sample Test Case (lab5-q2-tc1.c):
// This file is named as lab5-q1-tc1.cinclude”lab5-q2.h”
include<stdio.h>
include<stdlib.h>
include<string.h>
5
include<limits.h>
int main(int argc, char *argv[]){
FILE *fout;
BTree *T;
int isCorrect, i;
fout = fopen(argv[1], “w”);
/ default, your program is correct /
isCorrect = 1;
/ check the function, tree_init() /
T = NULL;
tree_init(&T, 4, 7., 10);
/ if T is not initialized appropriately /
if (T == NULL) {
isCorrect = 0;
} else if (T->max_size != 10) {
isCorrect = 0;
} else if (T->key[0] != 4 || fabs(T->value[0] – 7) > 1e-8) {
isCorrect = 0;
} else {
for (i = 1; i < 10; i++) {
if (T->key[i]!=INT_MAX||fabs(T->value[i]+2100)>1e-8){
isCorrect = 0;
}
}
}
/ output “Correct” if the tree_init() is correctly implemented /
if (isCorrect == 1) {
fprintf(fout, “Tree: Correct\n”);
} else {
fprintf(fout, “Tree: Wrong Answer\n”);
}
fclose(fout);
return 0;
}
6
Question 3: Lowest Common Ancestor (30%)
You are given a general tree. You are asked to identify the lowest common ancestor of two
nodes, i.e. the deepest ancestor of the two given nodes. All nodes only contain a unique
number ranging from 0 to 200.
Your program should read the input from the file, and output the answer to another file. The
first argument is the input file name, while the second argument is the output file name.
Name your program as“lab5-q3.c”.
Input file: First line, an integer N, indicating the number of nodes in the tree. Following n – 1
lines, p n, two integers, node p is the parent of node n. The p in line 2 is the root of the tree.
Last line, a b, two integers, find the lowest common ancestor of node a and node b.
Output file: An integer, l, indicates the lowest common ancestor of node a and node b.
Sample Input:
2 - 1
- 1
Sample Output:
0
7
Question 4: Balanced Binary Tree (Bonus 13%)
You are given a binary tree. You are asked to check whether the tree is a balanced tree or
not. If it is not a balanced tree, you need to find out the list of all nodes leading to an
unbalanced tree. All nodes only contain a unique number ranging from 0 to 200.
Your program should read the input from the file, and output the answer to another file. The
first argument is the input file name, while the second argument is the output file name.
Name your program as“lab5-q4.c”.
Hint: You cannot use the array implementation in Q.2 for this problem.
Input file: First line, an integer N, indicating the number of nodes in the tree. Following n – 1
lines, p n, two integers, node p is the parent of node n. The p in line 2 is the root of the tree.
Output file: If it is a balanced binary tree, then output“It is a balanced binary tree.”.
Otherwise, output the list of unbalanced nodes in ascending numeric order.
Sample Input 1:
2 - 1
Sample Output 1:
It is a balanced binary tree.
Sample Input 2:
4 - 1
- 2
- 3
Sample Output 3: - 1
8