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,

It is not possible to deduce a binary 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 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 vector<T>::iterator pre_begin, typename vector<T>::iterator pre_end, typename vector<T>::iterator in_begin, typename vector<T>::iterator in_end) { // Add your code here }

To check that your function is correct, supply the missing code in the following tandem of overloaded functions that together draw a binary tree sideways:

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

Note that you need implement the first function only—the second function is complete.

When executed, the following client code fragment

// Specify a preorder and inorder traversal vector<int> pre = { 36, 100, 11, 3, 10, 5, 2, 8 }, in = { 11, 100, 10, 3, 5, 36, 8, 2 }; // Build the binary tree from the traversals Node<int> *tree = build_tree<int>(begin(pre), end(pre), begin(in), end(in)); // Draw the resulting tree draw(tree);

should produce the following output:

/[2] \[8] -[36] /[5] /[3] \[10] \[100] \[11]

(Rotate your head 90 degrees counter-clockwise to see the tree as we normally would orient it.)

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.

When you have implemented and tested the two functions, place them in a file named treetrav.cpp. Include the expected comments, but do not include any other code besides the two function definitions—this is because I will #include your file into my test code.

You may believe that it would be a good idea to provide a function to free up the space held by a binary tree that a client created via your build_tree function. The following should work nicely:

template <typename T> void dispose_tree(Node *t) { if (t) { dispose_tree(t->left); dispose_tree(t->right); delete t; } }

You do not need to provide this function, as my test code takes care of it for you. You probably want to add this code to your test code.

Submit your treetrav.cpp source file to eclass.e.southern.edu.