MCS-021 Assignments Solution January-2012: Question 2: Write an algorithm for the conversion of a Tree into a Binary Tree. Also, write the corresponding program.(20 marks)

Algorithm for the implementation of a Binary tree: Step-1: If value of new element < current element, then go to step-2 or else step -3

Step-2: If the current element does not have a left sub-tree, then make new element the left child of the current element; else make the existing left child as current element and go to step-1

Step-3: If the current element does not have a right sub-tree, then make new element the right child of the current element; else make the existing right child as current element and go to step-1

The process of converting the general tree to a binary tree is as follows:    1. use the root of the general tree as the root of the binary tree    2. Determine the first child of the root. This is the leftmost node in the general tree at the next        level    3. Insert this node. The child reference of the parent node refers to this node    4. Continue finding the first child of each parent node and insert it below the parent node with        the child reference of the parent to this node. 5. When no more first children exist in the path just used, move back to the parent of the last    node entered and repeat the above process. In other words, determine the first sibling of the    last node entered. 6. Complete the tree for all nodes. In order to locate where the node fits you must search for the    first child at that level and then follow the sibling references to a nil where the next sibling    can be inserted. The children of any sibling node can be inserted by locating the parent and    then inserting the first child. Then the above process is repeated. /* Binary Tree */ #include <iostream> #include <deque> #include <climits> using namespace std; struct Tree { char data; Tree *left; Tree *right; Tree *parent; }; Tree* lookUp(struct Tree *node, char key) { if(node == NULL) return node; if(node->data == key) return node; else { if(node->data < key) return lookUp(node->right, key) ; else return lookUp(node->left, key); } } Tree* leftMost(struct Tree *node) { if(node == NULL) return NULL; while(node->left != NULL) node = node->left; return node; } struct Tree *newTreeNode(int data) { Tree *node = new Tree; node->data = data; node->left = NULL; node->right = NULL; node->parent = NULL; return node; } struct Tree* insertTreeNode(struct Tree *node, int data) { static Tree *p; Tree *retNode; return lookUp(node->left, key); } } Tree* leftMost(struct Tree *node) { if(node == NULL) return NULL; while(node->left != NULL) node = node->left; return node; } struct Tree *newTreeNode(int data) { Tree *node = new Tree; node->data = data; node->left = NULL; node->right = NULL; node->parent = NULL; return node; } struct Tree* insertTreeNode(struct Tree *node, int data) { static Tree *p; Tree *retNode; if(node != NULL) p = node; if(node == NULL) { retNode = newTreeNode(data); retNode->parent = p; return retNode; } if(data <= node->data ) { p = node; node->left = insertTreeNode(node->left,data); } else { p = node; node->right = insertTreeNode(node->right,data); } return node; } void isBST(struct Tree *node) { static int lastData = INT_MIN; if(node == NULL) return; isBST(node->left); /* check if the given tree is BST */ if(lastData < node->data) lastData = node->data; else { cout << "Not a BST" << endl; return; } isBST(node->right); return; } int treeSize(struct Tree *node) { if(node == NULL) return 0; else return treeSize(node->left) + 1 + treeSize(node->right); } int maxDepth(struct Tree *node) { if(node == NULL) return 0; int leftDepth = maxDepth(node->left); int rightDepth = maxDepth(node->right); return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1; } int minDepth(struct Tree *node) { if(node == NULL) return 0; int leftDepth = minDepth(node->left); int rightDepth = minDepth(node->right); return leftDepth < rightDepth ? leftDepth + 1 : rightDepth + 1; } bool isBalanced(struct Tree *node) { if(maxDepth(node)-minDepth(node) <= 1) return true; else return false; } /* Tree Minimum */ Tree* minTree(struct Tree *node) { if(node == NULL) return NULL; while(node->left) node = node -> left; return node; } /* Tree Maximum */ Tree* maxTree(struct Tree *node) { while(node->right) node = node -> right; return node; } /* In Order Successor - a node which has the next higher key */ Tree *succesorInOrder(struct Tree *node) { /* if the node has right child, seccessor is Tree-Minimum */ if(node->right != NULL) return minTree(node->right); Tree *y = node->parent; while(y != NULL && node == y->right) { node = y; y = y->parent; } return y; } /* In Order Predecessor - a node which has the next lower key */ Tree *predecessorInOrder(struct Tree *node) { /* if the node has left child, predecessor is Tree-Maximum */ if(node->left != NULL) return maxTree(node->left); Tree *y = node->parent; /* if it does not have a left child, predecessor is its first left ancestor */ while(y != NULL && node == y->left) { node = y; y = y->parent; } return y; } Tree *lowestCommonAncestor(Tree *root, Tree *p, Tree *q) { Tree *left, *right; if(root == NULL) return NULL; if(root->left == p || root->left == q || root->right == p || root->right == q) return root; else { left = lowestCommonAncestor(root->left,p,q); right = lowestCommonAncestor(root->right, p,q); if(left && right) return root; else return (left) ? left : right; } } void clear(struct Tree *node) { if(node != NULL) { clear(node->left); clear(node->right); delete node; } } /* print tree in order */ /* 1. Traverse the left subtree. 2. Visit the root. 3. Traverse the right subtree. */ void printTreeInOrder(struct Tree *node) { static int lastData = INT_MIN; if(node == NULL) return; printTreeInOrder(node->left); cout << node->data << " "; printTreeInOrder(node->right); } /* print tree in postorder*/ /* 1. Traverse the left subtree. 2. Traverse the right subtree. 3. Visit the root. */ void printTreePostOrder(struct Tree *node) { if(node == NULL) return; printTreePostOrder(node->left); printTreePostOrder(node->right); cout << node->data << " "; } /* print in preorder */ /* 1. Visit the root. 2. Traverse the left subtree. 3. Traverse the right subtree. */ void printTreePreOrder(struct Tree *node) { if(node == NULL) return; cout << node->data << " "; printTreePreOrder(node->left); printTreePreOrder(node->right); } /* printing array */ void printThisPath(int path[], int n) { for(int i = 0; i < n; i++) cout << (char)path[i] << " "; cout << endl; } /* recursion routine to find path */ void pathFinder(struct Tree *node, int path[], int pathLength) { if(node == NULL) return; path[pathLength++] = node->data; /* Leaf node is the end of a path. So, let's print the path */ if(node->left == NULL && node->right == NULL) printThisPath(path, pathLength); else { pathFinder(node->left, path, pathLength); pathFinder(node->right, path, pathLength); } } /*printing all paths : Given a binary tree, print out all of its root-to-leaf paths, one per line. Uses a recursive helper to do the work. */ void printAllPaths(struct Tree *root) { int path[100]; pathFinder(root,path,0); } bool matchTree(Tree *r1, Tree *r2) { /* Nothing left in the subtree */ if(r1 == NULL && r2 == NULL) return true; /* Big tree empty and subtree not found */ if(r1 == NULL || r2 == NULL) return false; /* Not matching */ if(r1->data != r2->data) return false; return (matchTree(r1->left, r2->left) && matchTree(r1->right, r2->right)); } bool subTree(Tree *r1, Tree *r2) { /*Big tree empty and subtree not found */ if(r1 == NULL) return false; if(r1->data == r2->data) if(matchTree(r1, r2)) return true; return (subTree(r1->left, r2) || subTree(r1->right, r2)); } bool isSubTree(Tree *r1, Tree *r2) { /* Empty tree is subtree */ if(r2 == NULL) return true; else return subTree(r1, r2); } /* change a tree so that the roles of the left and right hand pointers are swapped at every node */ void mirror(Tree *r) { if(r == NULL) return; Tree *tmp; mirror(r->left); mirror(r->right); /* swap pointers */ tmp = r->right; r->right = r->left; r->left = tmp; } /* create a new tree from a sorted array */ Tree *addToBST(char arr[], int start, int end) { if(end < start) return NULL; int mid = (start + end)/2; Tree *r = new Tree; r->data = arr[mid]; r->left = addToBST(arr, start, mid-1); r->right = addToBST(arr, mid+1, end); return r; } Tree *createMinimalBST(char arr[], int size) { return addToBST(arr,0,size-1); } /* Breadth first traversal using queue */ void BreadthFirstTraversal(Tree *root) { if (root == NULL) return; deque <Tree *> queue; queue.push_back(root); while (!queue.empty()) { Tree *p = queue.front(); cout << p->data << " "; queue.pop_front(); if (p->left != NULL) queue.push_back(p->left); if (p->right != NULL) queue.push_back(p->right); } cout << endl; } /* find n-th max node from a tree */ void NthMax(struct Tree* t) { static int n_th_max = 5; static int num = 0; if(t == NULL) return; NthMax(t->right); num++; if(num == n_th_max) cout << n_th_max << "-th maximum data is " << t->data << endl; NthMax(t->left); } /* Converting a BST into an Array */ void TreeToArray(struct Tree *node, int a[]){ static int pos = 0; if(node){ TreeToArray(node->left,a); a[pos++] = node->data; TreeToArray(node->right,a); } } int main(int argc, char **argv) { char ch, ch1, ch2; Tree *found; Tree *succ; Tree *pred; Tree *ancestor; char charArr[9] = {'A','B','C','D','E','F','G','H','I'}; Tree *root = newTreeNode('F'); insertTreeNode(root,'B'); insertTreeNode(root,'A'); insertTreeNode(root,'D'); insertTreeNode(root,'C'); insertTreeNode(root,'E'); insertTreeNode(root,'G'); insertTreeNode(root,'I'); insertTreeNode(root,'H'); /* is the tree BST? */ isBST(root); /* size of tree */ cout << "size = " << treeSize(root) << endl; /* max depth */ cout << "max depth = " << maxDepth(root) << endl; /* min depth */ cout << "min depth = " << minDepth(root) << endl; /* balanced tree? */ if(isBalanced(root)) cout << "This tree is balanced!\n"; else cout << "This tree is not balanced!\n"; /* min value of the tree*/ if(root) cout << "Min value = " << minTree(root)->data << endl; /* max value of the tree*/ if(root) cout << "Max value = " << maxTree(root)->data << endl; ch = 'B'; found = lookUp(root,ch); if(found) { cout << "Min value of subtree " << ch << " as a root is " << minTree(found)->data << endl; cout << "Max value of subtree " << ch << " as a root is " << maxTree(found)->data << endl; } ch = 'B'; found = lookUp(root,ch); if(found) { succ = succesorInOrder(found); if(succ) cout << "In Order Successor of " << ch << " is " << succesorInOrder(found)->data << endl; else cout << "In Order Successor of " << ch << " is None\n"; } ch = 'E'; found = lookUp(root,ch); if(found) { succ = succesorInOrder(found); if(succ) cout << "In Order Successor of " << ch << " is " << succesorInOrder(found)->data << endl; else cout << "In Order Successor of " << ch << " is None\n"; } ch = 'I'; found = lookUp(root,ch); if(found) { succ = succesorInOrder(found); if(succ) cout << "In Order Successor of " << ch << " is " << succesorInOrder(found)->data << endl; else cout << "In Order Successor of " << ch << " is None\n"; } ch = 'B'; found = lookUp(root,ch); if(found) { pred = predecessorInOrder(found); if(pred) cout << "In Order Predecessor of " << ch << " is " << predecessorInOrder(found)->data << endl; else cout << "In Order Predecessor of " << ch << " is None\n"; } ch = 'E'; found = lookUp(root,ch); if(found) { pred = predecessorInOrder(found); if(pred) cout << "In Order Predecessor of " << ch << " is " << predecessorInOrder(found)->data << endl; else cout << "In Order Predecessor of " << ch << " is None\n"; } ch = 'I'; found = lookUp(root,ch); if(found) { pred = predecessorInOrder(found); if(pred) cout << "In Order Predecessor of " << ch << " is " << predecessorInOrder(found)->data << endl; else cout << "In Order Predecessor of " << ch << " is None\n"; } /* Lowest Common Ancestor */ ch1 = 'A'; ch2 = 'C'; ancestor = lowestCommonAncestor(root, lookUp(root,ch1), lookUp(root,ch2)); if(ancestor) cout << "The lowest common ancestor of " << ch1 << " and " << ch2 << " is " << ancestor->data << endl; ch1 = 'E'; ch2 = 'H'; ancestor = lowestCommonAncestor(root, lookUp(root,ch1), lookUp(root,ch2)); if(ancestor) cout << "The lowest common ancestor of " << ch1 << " and " << ch2 << " is " << ancestor->data << endl; /* print tree in order */ cout << "increasing sort order\n"; printTreeInOrder(root); cout << endl; /* print tree in postorder*/ cout << "post order \n"; printTreePostOrder(root); cout << endl; /* print tree in preorder*/ cout << "pre order \n"; printTreePreOrder(root); cout << endl; /* lookUp */ ch = 'D'; found = lookUp(root,ch); if(found) cout << found->data << " is in the tree\n"; else cout << ch << " is not in the tree\n"; /* lookUp */ ch = 'M'; found = lookUp(root,ch); if(found) cout << found->data << " is in the tree\n"; else cout << ch << " is not in the tree\n"; /* printing all paths : Given a binary tree, print out all of its root-to-leaf paths, one per line. Uses a recursive helper to do the work. */ cout << "printing paths ..." << endl; printAllPaths(root); /* find n-th maximum node */ NthMax(root); /* convert the tree into an array */ int treeSz = treeSize(root); int *array = new int[treeSz]; TreeToArray(root,array); cout << "New array: "; for (int i = 0; i < treeSz; i++) cout << (char)array[i] << ' '; cout << endl; delete [] array; /* subtree */ Tree *root2 = newTreeNode('D'); insertTreeNode(root2,'C'); insertTreeNode(root2,'E'); cout << "1-2 subtree: " << isSubTree(root, root2) << endl; Tree *root3 = newTreeNode('B'); insertTreeNode(root3,'A'); insertTreeNode(root3,'D'); insertTreeNode(root3,'C'); insertTreeNode(root3,'E'); cout << "1-3 subtree: " << isSubTree(root, root3) << endl; Tree *root4 = newTreeNode('B'); insertTreeNode(root4,'D'); insertTreeNode(root4,'C'); insertTreeNode(root4,'E'); cout << "1-4 subtree: " << isSubTree(root, root4) << endl; cout << "2-3 subtree: " << isSubTree(root2, root3) << endl; cout << "3-2 subtree: " << isSubTree(root3, root2) << endl; /* swap left and right */ mirror(root); /* deleting a tree */ clear(root); /* make a new tree with minimal depth */ Tree *newRoot = createMinimalBST(charArr,9); /* Traversing level-order. We visit every node on a level before going to a lower level. This is also called Breadth-first traversal.*/ cout << "printing with Breadth-first traversal" << endl; BreadthFirstTraversal(newRoot); return 0; }