Advertisement
wa12rior

Binary tree

May 28th, 2022
438
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /* Binary Tree */
  2.  
  3. #include <iostream>
  4. #include <deque>
  5. #include <climits>
  6. #include <vector>
  7. using namespace std;
  8.  
  9. struct Tree
  10. {
  11.     char data;
  12.     Tree *left;
  13.     Tree *right;  
  14.     Tree *parent;  
  15. };
  16.  
  17. Tree* lookUp(struct Tree *node, char key)
  18. {
  19.     if(node == NULL) return node;
  20.  
  21.     if(node->data == key) return node;
  22.     else {
  23.         if(node->data < key)
  24.         return lookUp(node->right, key) ;
  25.         else
  26.         return lookUp(node->left, key);
  27.     }
  28. }
  29.  
  30. Tree* leftMost(struct Tree *node)
  31. {
  32.     if(node == NULL) return NULL;
  33.     while(node->left != NULL)
  34.         node = node->left;
  35.     return node;
  36. }
  37.  
  38. struct Tree *newTreeNode(int data)
  39. {
  40.     Tree *node = new Tree;
  41.     node->data = data;
  42.     node->left = NULL;
  43.     node->right = NULL;
  44.     node->parent = NULL;
  45.  
  46.     return node;
  47. }
  48.  
  49. struct Tree* insertTreeNode(struct Tree *node, int data)
  50. {
  51.     static Tree *p;
  52.     Tree *retNode;
  53.  
  54.     //if(node != NULL) p = node;
  55.  
  56.     if(node == NULL)  {
  57.         retNode = newTreeNode(data);
  58.         retNode->parent = p;
  59.         return retNode;
  60.     }
  61.     if(data <= node->data ) {
  62.         p = node;
  63.         node->left = insertTreeNode(node->left,data);
  64.     }
  65.     else {
  66.         p = node;
  67.         node->right = insertTreeNode(node->right,data);
  68.     }
  69.     return node;
  70. }
  71.  
  72. void isBST(struct Tree *node)
  73. {
  74.     static int lastData = INT_MIN;
  75.     if(node == NULL) return;
  76.  
  77.     isBST(node->left);
  78.  
  79.     /* check if the given tree is BST */
  80.     if(lastData < node->data)
  81.         lastData = node->data;
  82.     else {
  83.         cout << "Not a BST" << endl;
  84.         return;
  85.     }
  86.  
  87.     isBST(node->right);
  88.     return;
  89. }
  90.  
  91. int treeSize(struct Tree *node)
  92. {
  93.     if(node == NULL) return 0;
  94.     else
  95.         return treeSize(node->left) + 1 + treeSize(node->right);
  96. }
  97.  
  98. int maxDepth(struct Tree *node)
  99. {
  100.     if(node == NULL || (node->left == NULL && node->right == NULL))
  101.             return 0;
  102.  
  103.     int leftDepth = maxDepth(node->left);
  104.     int rightDepth = maxDepth(node->right);
  105.  
  106.     return leftDepth > rightDepth ?
  107.                 leftDepth + 1 : rightDepth + 1;
  108. }
  109.  
  110. int minDepth(struct Tree *node)
  111. {
  112.     if(node == NULL || (node->left == NULL && node->right == NULL))
  113.             return 0;
  114.  
  115.     int leftDepth = minDepth(node->left);
  116.     int rightDepth = minDepth(node->right);
  117.  
  118.     return leftDepth < rightDepth ?
  119.                 leftDepth + 1 : rightDepth + 1;
  120. }
  121.  
  122. bool isBalanced(struct Tree *node)
  123. {
  124.     if(maxDepth(node)-minDepth(node) <= 1)
  125.         return true;
  126.     else
  127.         return false;
  128. }
  129.  
  130. /* Tree Minimum */
  131. Tree* minTree(struct Tree *node)
  132. {
  133.     if(node == NULL) return NULL;
  134.     while(node->left)
  135.         node = node -> left;
  136.     return node;
  137. }
  138.  
  139. /* Tree Maximum */
  140. Tree* maxTree(struct Tree *node)
  141. {
  142.     while(node->right)
  143.         node = node -> right;
  144.     return node;
  145. }
  146.  
  147. /* In Order Successor - a node which has the next higher key */
  148. Tree *succesorInOrder(struct Tree *node)
  149. {
  150.     /* if the node has right child, seccessor is Tree-Minimum */
  151.     if(node->right != NULL) return minTree(node->right);
  152.  
  153.     Tree *y = node->parent;
  154.     while(y != NULL && node == y->right) {
  155.         node = y;
  156.         y = y->parent;
  157.     }
  158.     return y;
  159. }
  160.  
  161. /* In Order Predecessor - a node which has the next lower key */
  162. Tree *predecessorInOrder(struct Tree *node)
  163. {
  164.     /* if the node has left child, predecessor is Tree-Maximum */
  165.     if(node->left != NULL) return maxTree(node->left);
  166.  
  167.     Tree *y = node->parent;
  168.     /* if it does not have a left child,
  169.     predecessor is its first left ancestor */
  170.     while(y != NULL && node == y->left) {
  171.         node = y;
  172.         y = y->parent;
  173.     }
  174.     return y;
  175. }
  176.  
  177. void reverseOrderPrint(struct Tree *node)
  178. {
  179.     if(node == NULL) return;
  180.     if(node->left == NULL && node->right == NULL) {
  181.         cout << node->data << " ";
  182.         return;
  183.     }
  184.    
  185.     reverseOrderPrint(node->right);
  186.     cout << node->data << " ";
  187.     reverseOrderPrint(node->left);
  188. }
  189.  
  190. Tree *lowestCommonAncestor(Tree *node, Tree *p, Tree *q)
  191. {
  192.     Tree *left, *right;
  193.     if(node == NULL) return NULL;
  194.     if(node->left == p || node->left == q
  195.         || node->right == p || node->right == q) return node;
  196.    
  197.     left = lowestCommonAncestor(node->left,p,q);
  198.     right = lowestCommonAncestor(node->right, p,q);
  199.     if(left && right)
  200.         return node;
  201.     else
  202.         return (left) ? left : right;  
  203. }
  204.  
  205. void clear(struct Tree *node)
  206. {
  207.     if(node != NULL) {
  208.         clear(node->left);
  209.         clear(node->right);
  210.         delete node;
  211.     }
  212. }
  213. /* print tree in order */
  214. /* 1. Traverse the left subtree.
  215.    2. Visit the root.
  216.    3. Traverse the right subtree.
  217. */
  218.  
  219. void printTreeInOrder(struct Tree *node)
  220. {
  221.     if(node == NULL) return;
  222.  
  223.     printTreeInOrder(node->left);
  224.     cout << node->data << " ";
  225.     printTreeInOrder(node->right);
  226. }
  227.  
  228. /* print tree in postorder*/
  229. /* 1. Traverse the left subtree.
  230.    2. Traverse the right subtree.
  231.    3. Visit the root.
  232. */
  233. void printTreePostOrder(struct Tree *node)
  234. {
  235.     if(node == NULL) return;
  236.  
  237.     printTreePostOrder(node->left);
  238.     printTreePostOrder(node->right);
  239.     cout << node->data << " ";
  240. }
  241.  
  242. /* print in preorder */
  243. /* 1. Visit the root.
  244.    2. Traverse the left subtree.
  245.    3. Traverse the right subtree.
  246. */
  247. void printTreePreOrder(struct Tree *node)
  248. {
  249.     if(node == NULL) return;
  250.  
  251.     cout << node->data << " ";
  252.     printTreePreOrder(node->left);
  253.     printTreePreOrder(node->right);
  254. }
  255.  
  256. /* In reverse of printTreeInOrder() */
  257. void printTreeReverseOrder(struct Tree *node)
  258. {
  259.     if(node == NULL) return;
  260.     if(node->left == NULL && node->right == NULL) {
  261.         cout << node->data << " ";
  262.         return;
  263.     }
  264.    
  265.     printTreeReverseOrder(node->right);
  266.     cout << node->data << " ";
  267.     printTreeReverseOrder(node->left);
  268. }
  269. /* recursion routine to find path */
  270. void pathFinder(struct Tree *node, int path[], int level)
  271. {
  272.     if(node == NULL) return;
  273.         // save leaf node
  274.     if(node->left == NULL && node->right == NULL) {
  275.         path[level] = node->data;
  276.         for(int i = 0; i <= level; i++) {
  277.         cout << (char)path[i];
  278.         }
  279.         cout << endl;
  280.         return;
  281.     }
  282.         // save parent node
  283.     path[level] = node->data;
  284.     pathFinder(node->left, path, level+1);
  285.     pathFinder(node->right, path, level+1);
  286. }
  287.  
  288. bool matchTree(Tree *r1, Tree *r2)
  289. {
  290.     /* Nothing left in the subtree */
  291.     if(r1 == NULL && r2 == NULL)
  292.         return true;
  293.     /* Big tree empty and subtree not found */
  294.     if(r1 == NULL || r2 == NULL)
  295.         return false;
  296.     /* Not matching */
  297.     if(r1->data != r2->data)
  298.         return false;
  299.     return (matchTree(r1->left, r2->left) &&
  300.             matchTree(r1->right, r2->right));
  301. }
  302.  
  303. bool subTree(Tree *r1, Tree *r2)
  304. {
  305.     /*Big tree empty and subtree not found */
  306.     if(r1 == NULL)
  307.         return false;
  308.     if(r1->data == r2->data)
  309.         if(matchTree(r1, r2)) return true;
  310.     return
  311.             (subTree(r1->left, r2) || subTree(r1->right, r2));
  312. }
  313.  
  314. bool isSubTree(Tree *r1, Tree *r2)
  315. {
  316.     /* Empty tree is subtree */
  317.     if(r2 == NULL)
  318.         return true;
  319.     else
  320.         return subTree(r1, r2);
  321. }
  322.  
  323. /* change a tree so that the roles of the left
  324. and right hand pointers are swapped at every node */
  325. void mirror(Tree *r)
  326. {
  327.     if(r == NULL) return;
  328.    
  329.     Tree *tmp;
  330.     mirror(r->left);
  331.     mirror(r->right);
  332.  
  333.     /* swap pointers */
  334.     tmp = r->right;
  335.     r->right = r->left;
  336.     r->left = tmp;
  337. }
  338.  
  339. /* create a new tree from a sorted array */
  340. Tree *addToBST(char arr[], int start, int end)
  341. {
  342.     if(end < start) return NULL;
  343.     int mid = (start + end)/2;
  344.  
  345.     Tree *r = new Tree;
  346.     r->data = arr[mid];
  347.     r->left = addToBST(arr, start, mid-1);
  348.     r->right = addToBST(arr, mid+1, end);
  349.     return r;
  350. }
  351.  
  352. Tree *createMinimalBST(char arr[], int size)
  353. {
  354.     return addToBST(arr,0,size-1);
  355. }
  356.  
  357. /* Breadth first traversal using queue */
  358. void BreadthFirstTraversal(Tree *root)
  359. {
  360.     if (root == NULL) return;
  361.     deque <Tree *> queue;
  362.     queue.push_back(root);
  363.  
  364.     while (!queue.empty()) {
  365.         Tree *p = queue.front();
  366.         cout << p->data << " ";
  367.         queue.pop_front();
  368.  
  369.         if (p->left != NULL)
  370.         queue.push_back(p->left);
  371.         if (p->right != NULL)
  372.         queue.push_back(p->right);
  373.     }
  374.     cout << endl;
  375. }
  376.  
  377. /* get the level of a node element: root level = 0 */
  378. int getLevel(struct Tree *node, int elm, int level)
  379. {
  380.     if(node == NULL) return 0;
  381.     if(elm == node->data)
  382.         return level;
  383.     else if(elm < node->data)
  384.         return getLevel(node->left, elm, level+1);
  385.     else
  386.         return getLevel(node->right, elm, level+1);
  387. }
  388.  
  389. /* This code prints out all nodes at the same depth (level) */
  390. void BreadthFirst_LevelElement_Print
  391.                (struct Tree *root, vector<vector<int> > &v)
  392. {
  393.     if(root == NULL) return;
  394.     deque<Tree *> q;
  395.     q.push_back(root);
  396.     while(!q.empty()) {
  397.         Tree *p =  q.front();
  398.         int lev = getLevel(root, p->data, 0);
  399.         v[lev].push_back(p->data);
  400.         q.pop_front();
  401.         if(p->left) q.push_back(p->left);
  402.         if(p->right)q.push_back(p->right);
  403.     }
  404.     return;
  405. }
  406.  
  407. /* levelPrint()
  408. prints nodes at the same level
  409. This is simpler than the BreadthFirstTraversal(root) above
  410. It takes 2D vector with the same size of level (= MaxDepth+1)
  411. and fills elements as we traverse (preOrder) */
  412.  
  413. void levelPrint(struct Tree *node, vector<vector<char> >&elm, int level)
  414. {
  415.     if(node == NULL) return;
  416.     // leaf nodes
  417.     if(node->left == NULL && node->right == NULL) {
  418.         elm[level].push_back(node->data);
  419.         return;
  420.     }
  421.     // other nodes
  422.     elm[level++].push_back(node->data);
  423.     levelPrint(node->left, elm, level);
  424.     levelPrint(node->right, elm, level);
  425. }
  426.  
  427. /* find n-th max node from a tree */
  428. void NthMax(struct Tree* t)
  429. {        
  430.     static int n_th_max = 5;
  431.     static int num = 0;
  432.     if(t == NULL) return;        
  433.     NthMax(t->right);        
  434.     num++;        
  435.     if(num == n_th_max)                
  436.         cout << n_th_max << "-th maximum data is "
  437.                  << t->data << endl;        
  438.     NthMax(t->left);
  439. }
  440.  
  441. /* Converting a BST into an Array */
  442. void TreeToArray(struct Tree *node, int a[]){
  443.     static int pos = 0;
  444.  
  445.     if(node){
  446.         TreeToArray(node->left,a);
  447.         a[pos++] = node->data;
  448.         TreeToArray(node->right,a);
  449.        }
  450. }
  451.  
  452. /* Separate even/odd level elements */
  453. /* This function is using BFS */
  454. void level_even_odd(struct Tree *node)
  455. {
  456.     vector<char> evenVec, oddVec;
  457.     if (node == NULL) return;
  458.     deque<struct Tree*> que;
  459.     que.push_back(node);
  460.  
  461.     while(!que.empty())
  462.     {
  463.         struct Tree *p = que.front();
  464.         int level = getLevel(node, p->data, 0) ;
  465.         // even level
  466.         if (level % 2 == 0)
  467.         evenVec.push_back(p->data);
  468.         else
  469.         oddVec.push_back(p->data);
  470.         que.pop_front();
  471.         if(p->left)  que.push_back(p->left);
  472.         if(p->right) que.push_back(p->right);
  473.     }
  474.    
  475.     cout << "even level elements : ";
  476.     for(int i = 0; i < evenVec.size(); i++)
  477.             cout << evenVec[i] << " ";
  478.     cout << endl << "odd level elements : ";
  479.         for(int i = 0; i < oddVec.size(); i++)
  480.             cout << oddVec[i] << " ";
  481.     cout << endl;
  482. }
  483.  
  484. int main(int argc, char **argv)
  485. {
  486.     char ch, ch1, ch2;
  487.     Tree *found;
  488.     Tree *succ;
  489.     Tree *pred;
  490.     Tree *ancestor;
  491.     char charArr[9]
  492.         = {'A','B','C','D','E','F','G','H','I'};
  493.  
  494.     Tree *root = newTreeNode('F');
  495.     insertTreeNode(root,'B');
  496.     insertTreeNode(root,'A');
  497.     insertTreeNode(root,'D');
  498.     insertTreeNode(root,'C');  
  499.     insertTreeNode(root,'E');
  500.     insertTreeNode(root,'G');
  501.     insertTreeNode(root,'I');
  502.     insertTreeNode(root,'H');
  503.  
  504.     /* is the tree BST? */
  505.     isBST(root);
  506.  
  507.     /* size of tree */
  508.     cout << "size = " << treeSize(root) << endl;
  509.  
  510.     /* max depth */
  511.     cout << "max depth = " << maxDepth(root) << endl;
  512.  
  513.     /* min depth */
  514.     cout << "min depth = " << minDepth(root) << endl;
  515.  
  516.     /* balanced tree? */
  517.     if(isBalanced(root))
  518.         cout << "This tree is balanced!\n";
  519.     else
  520.         cout << "This tree is not balanced!\n";
  521.  
  522.     /* min value of the tree*/
  523.     if(root)
  524.         cout << "Min value = " << minTree(root)->data << endl;
  525.  
  526.     /* max value of the tree*/
  527.     if(root)
  528.         cout << "Max value = " << maxTree(root)->data << endl;
  529.  
  530.     /* get the level of a data: root level = 0 */
  531.     cout << "Node B is at level: " << getLevel(root, 'B', 0) << endl;
  532.     cout << "Node H is at level: " << getLevel(root, 'H', 0) << endl;
  533.     cout << "Node F is at level: " << getLevel(root, 'F', 0) << endl;
  534.  
  535.         /* separate even/odd level elements */
  536.         level_even_odd(root);
  537.  
  538.     ch = 'B';
  539.     found = lookUp(root,ch);
  540.     if(found) {
  541.         cout << "Min value of subtree " << ch << " as a root is "
  542.              << minTree(found)->data << endl;
  543.         cout << "Max value of subtree " << ch << " as a root is "
  544.              << maxTree(found)->data << endl;
  545.     }
  546.  
  547.     ch = 'B';
  548.     found = lookUp(root,ch);
  549.     if(found) {
  550.         succ = succesorInOrder(found);
  551.         if(succ)
  552.         cout << "In Order Successor of " << ch << " is "
  553.              << succesorInOrder(found)->data << endl;
  554.         else
  555.         cout << "In Order Successor of " << ch << " is None\n";
  556.     }
  557.  
  558.     ch = 'E';
  559.     found = lookUp(root,ch);
  560.     if(found) {
  561.         succ = succesorInOrder(found);
  562.         if(succ)
  563.         cout << "In Order Successor of " << ch << " is "
  564.              << succesorInOrder(found)->data << endl;
  565.         else
  566.         cout << "In Order Successor of " << ch << " is None\n";
  567.     }
  568.  
  569.     ch = 'I';
  570.     found = lookUp(root,ch);
  571.     if(found) {
  572.         succ = succesorInOrder(found);
  573.         if(succ)
  574.         cout << "In Order Successor of " << ch << " is "
  575.              << succesorInOrder(found)->data << endl;
  576.         else
  577.         cout << "In Order Successor of " << ch << " is None\n";
  578.     }
  579.  
  580.     ch = 'B';
  581.     found = lookUp(root,ch);
  582.     if(found) {
  583.         pred = predecessorInOrder(found);
  584.         if(pred)
  585.         cout << "In Order Predecessor of " << ch << " is "
  586.              << predecessorInOrder(found)->data << endl;
  587.         else
  588.         cout << "In Order Predecessor of " << ch << " is None\n";
  589.     }
  590.  
  591.     ch = 'E';
  592.     found = lookUp(root,ch);
  593.     if(found) {
  594.         pred = predecessorInOrder(found);
  595.         if(pred)
  596.         cout << "In Order Predecessor of " << ch << " is "
  597.              << predecessorInOrder(found)->data << endl;
  598.         else
  599.         cout << "In Order Predecessor of " << ch << " is None\n";
  600.     }
  601.  
  602.     ch = 'I';
  603.     found = lookUp(root,ch);
  604.     if(found) {
  605.         pred = predecessorInOrder(found);
  606.         if(pred)
  607.         cout << "In Order Predecessor of " << ch << " is "
  608.              << predecessorInOrder(found)->data << endl;
  609.         else
  610.         cout << "In Order Predecessor of " << ch << " is None\n";
  611.     }
  612.  
  613.     /* Lowest Common Ancestor */
  614.     ch1 = 'A';
  615.     ch2 = 'C';
  616.     ancestor =
  617.         lowestCommonAncestor(root,
  618.             lookUp(root,ch1), lookUp(root,ch2));
  619.     if(ancestor)
  620.         cout << "The lowest common ancestor of " << ch1 << " and "
  621.         << ch2 << " is " << ancestor->data << endl;
  622.  
  623.     ch1 = 'E';
  624.     ch2 = 'H';
  625.     ancestor =
  626.         lowestCommonAncestor(root,
  627.             lookUp(root,ch1), lookUp(root,ch2));
  628.     if(ancestor)
  629.         cout << "The lowest common ancestor of " << ch1 << " and "
  630.         << ch2 << " is " << ancestor->data << endl;
  631.  
  632.     ch1 = 'D';
  633.     ch2 = 'E';
  634.     ancestor =
  635.         lowestCommonAncestor(root,
  636.             lookUp(root,ch1), lookUp(root,ch2));
  637.     if(ancestor)
  638.         cout << "The lowest common ancestor of " << ch1 << " and "
  639.         << ch2 << " is " << ancestor->data << endl;
  640.  
  641.     ch1 = 'G';
  642.     ch2 = 'I';
  643.     ancestor =
  644.         lowestCommonAncestor(root,
  645.             lookUp(root,ch1), lookUp(root,ch2));
  646.     if(ancestor)
  647.         cout << "The lowest common ancestor of " << ch1 << " and "
  648.         << ch2 << " is " << ancestor->data << endl;
  649.  
  650.     ch1 = 'H';
  651.     ch2 = 'I';
  652.     ancestor =
  653.         lowestCommonAncestor(root,
  654.             lookUp(root,ch1), lookUp(root,ch2));
  655.     if(ancestor)
  656.         cout << "The lowest common ancestor of " << ch1 << " and "
  657.         << ch2 << " is " << ancestor->data << endl;
  658.  
  659.     /* print tree in order */
  660.     cout << "increasing sort order\n";
  661.     printTreeInOrder(root);
  662.     cout << endl;
  663.  
  664.     /* print tree in postorder*/
  665.     cout << "post order \n";
  666.     printTreePostOrder(root);
  667.     cout << endl;
  668.  
  669.     /* print tree in preorder*/
  670.     cout << "pre order \n";
  671.     printTreePreOrder(root);
  672.     cout << endl;
  673.  
  674.     /* print tree in reverse order*/
  675.     cout << "reverse order \n";
  676.     printTreeReverseOrder(root);
  677.     cout << endl;
  678.  
  679.     /* lookUp */
  680.     ch = 'D';
  681.     found = lookUp(root,ch);
  682.     if(found)
  683.         cout << found->data << " is in the tree\n";
  684.     else
  685.         cout << ch << " is not in the tree\n";
  686.  
  687.     /* lookUp */
  688.     ch = 'M';
  689.     found = lookUp(root,ch);
  690.     if(found)
  691.         cout << found->data << " is in the tree\n";
  692.     else
  693.         cout << ch << " is not in the tree\n";
  694.  
  695.     /* printing all paths :
  696.     Given a binary tree, print out all of its root-to-leaf
  697.     paths, one per line. Uses a recursive helper to do the work. */
  698.     cout << "printing paths ..." << endl;
  699.     int path[10];
  700.     pathFinder(root, path, 0);
  701.  
  702.     /* find n-th maximum node */
  703.     NthMax(root);
  704.  
  705.     /* Traversing level-order.
  706.     We visit every node on a level before going to a lower level.
  707.     This is also called Breadth-first traversal.*/
  708.     cout << "printing with Breadth-first traversal" << endl;
  709.     BreadthFirstTraversal(root);
  710.  
  711.     /* Prints all element at the same depth (level) */
  712.     int row = maxDepth(root);
  713.     vector<vector<int> > levVec(row+1);
  714.     BreadthFirst_LevelElement_Print(root, levVec);
  715.     for(int m = 0; m < levVec.size(); m++) {
  716.         cout << "Level at " << m << ": ";
  717.         for(int n = 0; n < levVec[m].size(); n++)
  718.         cout << (char)levVec[m][n] << " ";
  719.         cout << endl;
  720.     }
  721.  
  722.     /* levelPrint()
  723.     prints nodes at the same level
  724.     This is simpler than the BreadthFirstTraversal(root) above
  725.     It takes 2D vector (elm) with the same size of level (= MaxDepth+1)
  726.     and fills elements as we traverse (preOrder) */
  727.     vector<vector<char> > elm;
  728.     int mxDepth = maxDepth(root);
  729.     elm.resize(mxDepth+1);
  730.     int level = 0;
  731.     levelPrint(root, elm, level);
  732.     cout << "levelPrint() " << endl;
  733.     for(int i = 0; i <= mxDepth; i++) {
  734.         cout << "level " << i << ": " ;
  735.         for(int j = 0; j < elm[i].size(); j++)
  736.         cout << elm[i][j] << " ";
  737.         cout << endl;
  738.     }
  739.  
  740.     /* convert the tree into an array */
  741.     int treeSz = treeSize(root);
  742.     int *array = new int[treeSz];
  743.     TreeToArray(root,array);
  744.     cout << "New array: ";
  745.     for (int i = 0; i < treeSz; i++)
  746.         cout << (char)array[i] << ' ';
  747.     cout << endl;
  748.     delete [] array;
  749.  
  750.     /* subtree */
  751.     Tree *root2 = newTreeNode('D');
  752.     insertTreeNode(root2,'C');  
  753.     insertTreeNode(root2,'E');
  754.     cout << "1-2 subtree: " << isSubTree(root, root2) << endl;
  755.  
  756.     Tree *root3 = newTreeNode('B');
  757.     insertTreeNode(root3,'A');  
  758.     insertTreeNode(root3,'D');
  759.     insertTreeNode(root3,'C');  
  760.     insertTreeNode(root3,'E');
  761.     cout << "1-3 subtree: " << isSubTree(root, root3) << endl;
  762.  
  763.     Tree *root4 = newTreeNode('B');
  764.     insertTreeNode(root4,'D');
  765.     insertTreeNode(root4,'C');  
  766.     insertTreeNode(root4,'E');
  767.     cout << "1-4 subtree: " << isSubTree(root, root4) << endl;
  768.  
  769.     cout << "2-3 subtree: " << isSubTree(root2, root3) << endl;
  770.     cout << "3-2 subtree: " << isSubTree(root3, root2) << endl;
  771.  
  772.     /* swap left and right */
  773.     mirror(root);
  774.  
  775.     /* deleting a tree */
  776.     clear(root);
  777.  
  778.     /* make a new tree with minimal depth */
  779.     Tree *newRoot = createMinimalBST(charArr,9);
  780.  
  781.     return 0;
  782. }
Advertisement
RAW Paste Data Copied
Advertisement