CPTR 318 Data Structures and Algorithms

Building a Binary Tree from Traversals

Please read the remarks about programming problems for this course.

A binary tree may be traversed in one of three standard ways:

Preorder: First visit the node, then traverse the node's left subtree recursively, and finally traverse the node's right subtree recursively.
Inorder: Traverse the node's left subtree recursively, then visit the node, and finally traverse the node's right subtree recursively.
Postorder: Traverse the node's left subtree recursively, then traverse the node's right subtree recursively, and finally visit the node,

Consider a binary tree (not necessarily a binary search tree) that contains unique elements (that is, it has no duplicate elements). It is not possible to deduce the tree's structure solely from the order of the list of elements visited during a single traversal. It is possible, however, to construct a binary tree containing unique elements from a preorder and an inorder traversal.

Given a binary tree node defined as

template <typename T> struct Node { T data; Node *left; Node *right; Node(const T& d, Node *lf, Node *rt) : data(d), left(lf), right(rt) {} };

complete the following function that constructs a binary tree given iterators to both preorder and inorder traversals:

template <typename T> Node<T> *build_tree(typename std::vector<T>::iterator pre_begin, typename std::vector<T>::iterator pre_end, typename std::vector<T>::iterator in_begin, typename std::vector<T>::iterator in_end) { // Add your code here }

Note that our binary trees here are generic binary trees and, thus, are not necessarily binary search trees. The tree will contain no duplicate elements.

To check that your function is correct, supply the missing code in the following function that draws a binary tree sideways:

template <typename T> void draw(Node<T> *tree, char link, int depth) { // Add your code here }

Additionally, implement the following dispose function that frees up the memory held by a binary tree:

template <typename T> void dispose(Node<T> *t) { // Add your code here }

To streamline your development and help you better understand your task in this assignment, I have provided the following three files:

tree_extra.hpp is the file you will edit. It contains stubs for the functions you must complete.
tree.hpp is the header file that client code will include that provides access to your functions. It provides some convenience functions (overloaded build_tree and draw functions) that make it easier for callers to use your build_tree and draw functions.
This tree.hpp header file #includes your tree_extra.hpp file. Your code makes this header file complete.
You should not modify this file. My test code will use this file as is and will use your tree_extra.hpp file as is, so if you modify tree.hpp to somehow "help" your tree_extra.hpp file, your code likely will not pass my tests and possibly will not compile.
simpletest.cpp is a simple test program that tries out your functions. Consider it a minimal test; you should add more tests to until you are satisfied that your code is correct.

The first thing you should do is download all the files, build, and run the simpletest.cpp program. It should compile only with warnings (the function stubs are not using the parameters passed to them, so the compiler issues warnings for unused parameters). When executed, the program should print the following:

TODO: Implement draw function ==================== TODO: Implement draw function

After you have correctly implemented the functions, the program should print the following:

/[2] \[8] -[36] /[5] /[3] \[10] \[100] \[11] ==================== /[Henry] \[Kit] -[Xena] /[Pat] \[Albert] \[Quin]

(Rotate your head 90 degrees counter-clockwise to see the trees as we normally would orient them.) The output of the first tree corresponds to the following graphical rendering of the tree:

Hint: Notice that the draw function performs a backwards inorder traversal (right subtree, node, left subtree), and the depth of the recursion controls the amount of horizontal space to the left of the printed node.

Since it can be challenging to write both the draw and the build_tree functions at the same time, I suggest writing the draw function first. You can use the following code to test your draw function:

Node<int> *sample_tree = new Node<int>(14, new Node<int>(11, new Node<int>(12, nullptr, nullptr), new Node<int>(5, nullptr, nullptr)), new Node<int>(6, nullptr, new Node<int>(5, nullptr, nullptr))); draw(sample_tree);

If your draw function is correct, the above code should display the following:

/[5] /[6] -[14] /[5] \[11] \[12]

Once you get draw working you can use it to verify that your build_tree function is correct. (You also can check your build_tree function by doing preorder and postorder traversals on the tree it returns and comparing the result to the original traversals.)

Before you submit your code, check once more that your tree_extra.hpp file builds correctly with the original tree.hpp and simpletest.cpp files. Submit your completed tree_extra.hpp source file to eclass.e.southern.edu.