#ifndef BST_H #define BST_H #include #include #include #include #include #include #include #include using namespace std; template class bst { struct node { node() { key=Tkey(); left=right=NULL; } void print(); Tkey key; node *left; node *right; }; public: bst() { Troot=NULL; } bst() { clear(Troot); } bool empty() { return Troot==NULL; } void clear() { clear(Troot); Troot=NULL; } int num_nodes() { return num_nodes(Troot); } int num_leaves() { return num_leaves(Troot); } int height() { return height(Troot); } void insert(Tkey &key) { Troot = insert(Troot, key); } void print_inorder() { print_inorder(Troot); } void print_bylevel(); private: void clear(node *); int num_nodes(node *); int num_leaves(node *); int height(node *); node *insert(node *, Tkey &); void print_inorder(node *); node *Troot;}; template void bst::node::print() { cout << key << " :"; if (left) cout << " L=" << left->key; if (right) cout << " R=" << right->key; cout << " ";} template void bst::clear(node *T) { if (T) { clear(T->left); clear(T->right); delete T; T = NULL; } } template int bst::num_nodes(node *T) { if (T == NULL) return 0; return 1 + num_nodes(T->left) + num_nodes(T->right); } template int bst::num_leaves(node *T) { if (T == NULL) return 0; if ((T->left==NULL) && (T->right==NULL)) return 1; return num_leaves(T->left) + num_leaves(T->right);} template int bst::height(node *T) { if (T == NULL) return -1; int h_left = height(T->left); int h_right = height(T->right); return 1 + max(h_left, h_right);} template struct bst::node *bst::insert(node *T, Tkey &key){ if (T == NULL) { T = new node; T->key = key; } else { if (key < T->key) T->left = insert(T->left, key); else T->right = insert(T->right, key); } return T;} template void bst::print_inorder(node *T) { if (T) { print_inorder(T->left); T->print(); print_inorder(T->right); } } template void bst::print_bylevel() { if (Troot == NULL) return; queue Q; node *T; Q.push(Troot); while (!Q.empty()) { T = Q.front(); Q.pop(); T->print(); if (T->left) Q.push(T->left); if (T->right) Q.push(T->right); }} #endif /*-----------------------------------------------------------bst_usage.h: simple driver code-----------------------------------------------------------*/ #include #include #include #include #include #include #include #include #include "bst.h" using namespace std; int main(int argc, char *argv[]) { bst T; int key; while (cin >> key) T.insert(key); cout << "BINARY TREE" << " "; cout << "num_nodes = " << T.num_nodes() << " "; cout << "num_leaves = " << T.num_leaves() << " "; cout << "height = " << T.height() << " "; cout << " " << "inorder traversal" << " "; T.print_inorder(); cout << " " << "bylevel traversal" << " "; T.print_bylevel(); T.clear();}

/*unix> echo 4 2 1 3 2 6 5 7 | ./bst_usage BINARY TREE num_nodes = 8 num_leaves = 4 height = 3 inorder traversal bylevel traversal 1 : 4 : L=2 R=6 2 : L=1 R=3 2 : L=1 R=3 2 : 6 : L=5 R=7 3 : L=2 1 : 4 : L=2 R=6 3 : L=2 5 : 5 : 6 : L=5 R=7 7 : 7 : 2 : */

1.

M D T A R U P Q M

Sketch the binary tree produced by the algorithm from the bst1_handout when applied to the above data. The decision whether to go left or right isbased on whether the key is strictly less than the node key being tested or not. For example, the first M becomes the root of the tree. Since D is less than M, it becomes a left child (subtree) of M, T becomes a right child (subtree) of M, etc.Build the tree by hand. Determine the number of nodes and leaves as well as the height of the resulting tree.

2.List the tree node keys from Problem 1 using preorder, inorder and postorder traversals.