Objectives

• Know how to create and use a library of integer trees
• Know how to implement some basic tree algorithms

Context and Preparation

You will find several files to help you get started with the lab:

• https://www.dequidt.me/uploads/se/trees.c and https://www.dequidt.me/uploads/se/trees.h containing basic tree processing functions

• https://www.dequidt.me/uploads/se/main.c a file that demonstrates the use of these functions

• https://www.dequidt.me/uploads/se/tree2pdf.c a second file that converts a tree to PDF

• https://www.dequidt.me/uploads/se/samples/ a directory containing data files: balanced.dot balanced.pdf balanced.txt degenerated.dot degenerated.pdf degenerated.txt empty.dot empty.pdf empty.txt leaf.dot leaf.pdf leaf.txt unspecified.dot unspecified.pdf unspecified.txt

Lab Questions

• Write the cons_tree(...) function that constructs a BST (done in lecture).

• Write the mk_empty_tree(...) function

• Write the is_empty(...) function

• Write the is_leaf(...) function — these are all auxiliary functions. (Done in lecture)

• Write the add(...) function that inserts an element into a BST (binary search tree, therefore ordered). (Done in lecture)

• Write the print_tree(...) function that prints a BST using recursive traversal, in ascending order (inorder).

• Verify that the previous traversal function produces the same sequence of values for the three files unspecified.txt, balanced.txt, and degenerated.txt, even though they are different trees (see the diagrams in the samples/ directory).

• Write a load_tree(...) function that builds an integer tree from a file.

• Write a free_tree(...) function that frees the memory used by a binary tree.

• Write a print_rec_edges(...) function that prints the pairs (parent =L=> child) for left children, and (parent =R=> child) for right children, of a given tree. Do not print empty subtrees. Apart from the =L/R=> arrow, the output matches the trees in the .dot files provided in the samples/ directory.

• The .pdf files were generated from the .dot files (provided in samples/). The .dot format is a simple textual representation format for trees [^1]. View the format of these files in your preferred text editor or using the less command. From a .dot file, the dot command generates a viewable version (.pdf, .png, …) as follows (in pdf for example):

dot -Tpdf samples/balanced.dot -o samples/balanced.pdf

The goal is then to generate such files for trees built from data files (such as those provided in samples/*.txt).

Preparation: A more complete tree2pdf.c file is provided which: Generates, by calling the generate_dot function, the .dot files corresponding to the data files whose names were passed as parameters (e.g., from samples/balanced.txt it generates samples/balanced.dot). Converts these .dot files to .pdf by a system call to the dot command.

• Implement the recursive_dot function that handles the general case.

• Then test with the command: ./tree2pdf samples/*.txt. You should recover the .dot and .pdf files.