bintreetemplate.h

#include // Provides assert #include // Provides setw #include // Provides cout #include // Provides NULL, size_t

using namespace std;

// Programming note: Some compilers require that the default argument is // listed in the implementation as well as the prototype, so we have // include the default arguments for create_node. template BinaryTreeNode* create_node( const Item& entry, BinaryTreeNode* l_ptr, BinaryTreeNode* r_ptr ) { BinaryTreeNode* result_ptr;

result_ptr = new BinaryTreeNode; result_ptr->data = entry; result_ptr->left = l_ptr; result_ptr->right = r_ptr;

return result_ptr; }

template BinaryTreeNode* tree_copy(const BinaryTreeNode* root_ptr) // Library facilities used: stdlib.h { BinaryTreeNode *l_ptr; BinaryTreeNode *r_ptr;

if (root_ptr == NULL) return NULL; else { l_ptr = tree_copy(root_ptr->left); r_ptr = tree_copy(root_ptr->right); return create_node(root_ptr->data, l_ptr, r_ptr); } }

template void tree_clear(BinaryTreeNode*& root_ptr) { if (root_ptr != NULL) { tree_clear(root_ptr->left); tree_clear(root_ptr->right); delete root_ptr; root_ptr = NULL; } }

template bool is_leaf(const BinaryTreeNode& node) { return (node.left == NULL) && (node.right == NULL); }

template void inorder(Process f, BinaryTreeNode* node_ptr) { if (node_ptr != NULL) { inorder(f, node_ptr->left); f(node_ptr->data); inorder(f, node_ptr->right); } }

template void postorder(Process f, BinaryTreeNode* node_ptr) { if (node_ptr != NULL) { postorder(f, node_ptr->left); postorder(f, node_ptr->right); f(node_ptr->data); } }

template void preorder(Process f, BinaryTreeNode* node_ptr) { if (node_ptr != NULL) { f(node_ptr->data); preorder(f, node_ptr->left); preorder(f, node_ptr->right); } }

template size_t tree_size(const BinaryTreeNode* node_ptr) // Library facilities used: stdlib.h { if (node_ptr == NULL) return 0; else return 1 + tree_size(node_ptr->left) + tree_size(node_ptr->right); }

// // template // void printTreeAtDepth (BinaryTreeNode* node_ptr, SizeType depth) // Precondition: node_ptr is a pointer to a node in a binary // tree (or node_ptr may be NULL to indicate the empty tree). // If the pointer is NULL, then depth is expected to be 0. // If the pointer is not NULL, then depth is the depth of // the node pointed to by node_ptr. // Postcondition: If node_ptr is non-NULL, then the contents // of *node_ptr and all its descendants have been written // to cout with the << operator, using a backward in-order // traversal. Each node is indented 4 times its depth. template void printTreeAtDepth (BinaryTreeNode* node_ptr, SizeType depth) // Library facilities used: iomanip.h, iostream.h, stdlib.h { if (node_ptr != NULL) { printTreeAtDepth (node_ptr->right, depth+1); cout << setw(4*depth) << ""; // Indent 4*depth spaces cout << node_ptr->data << endl; printTreeAtDepth (node_ptr->left, depth+1); } }

template void printTree(BinaryTreeNode* node_ptr) { printTreeAtDepth (node_ptr, 0); }

bintree.h

#ifndef BINTREE_H #define BINTREE_H #include // Provides NULL

template struct BinaryTreeNode { Item data; BinaryTreeNode* left; BinaryTreeNode* right; };

template BinaryTreeNode* create_node( const Item& entry, BinaryTreeNode* l_ptr = NULL, BinaryTreeNode* r_ptr = NULL );

template BinaryTreeNode* tree_copy(const BinaryTreeNode* root_ptr);

template void tree_clear(BinaryTreeNode*& root_ptr); template bool is_leaf(const BinaryTreeNode& ptr);

template void preorder(Process f, BinaryTreeNode*);

template void inorder(Process f, BinaryTreeNode*);

template void postorder(Process f, BinaryTreeNode*);

template size_t tree_size(const BinaryTreeNode* root_ptr);

template void printTree (BinaryTreeNode* node_ptr);

template void insert (BinaryTreeNode* & root_ptr, Item Target); // template // void remove (BinaryTreeNode* & root_ptr, Item Target); // delete is predefined, so we use the name "remove" rather than "delete".

// template // BinaryTreeNode* reflect (const BinaryTreeNode* root_ptr);

template int height(const BinaryTreeNode* root_ptr) { int ldepth = 0; int rdepth = 0; if (root_ptr == NULL) return -1; else { int ldepth = height(root_ptr->left); int rdepth = height(root_ptr->right); if (ldepth > rdepth) return (ldepth + 1); else return (rdepth + 1); } } #include "bintreetemplate.h" #endif