Advertisement
Guest User

Binary Tree

a guest
Dec 20th, 2011
226
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.89 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. struct Node
  5. {
  6.        int keyValue;
  7.        Node *left;
  8.        Node *right;
  9. };
  10.  
  11. class BinaryTree
  12. {
  13.       public:
  14.       BinaryTree();
  15.       ~BinaryTree();
  16.       void insert(int key);
  17.       void destroyTree();
  18.       int size(Node *leaf);
  19.       int maxDepth(Node *leaf);
  20.       int height(Node *leaf);
  21.       void printTree(Node *leaf);
  22.       void printPostorder(Node *leaf);
  23.      
  24.       // private ?!
  25.       void destroyTree(Node *leaf);
  26.       void insert(int key, Node *leaf);
  27.       Node *root;
  28.      
  29. };
  30.  
  31. BinaryTree::BinaryTree()
  32. {
  33.      root = NULL;
  34. }
  35.  
  36. BinaryTree::~BinaryTree()
  37. {
  38.      destroyTree();
  39. }
  40.  
  41. void BinaryTree::destroyTree(Node *leaf)
  42. {
  43.      if(leaf != NULL)
  44.      {
  45.              destroyTree(leaf->left);
  46.              destroyTree(leaf->right);
  47.              delete leaf;
  48.      }
  49. }
  50.  
  51. void BinaryTree::insert(int key, Node *leaf)
  52. {
  53.      if(key < leaf->keyValue)
  54.      {
  55.             if(leaf->left != NULL) insert(key, leaf->left);
  56.             else
  57.             {
  58.                 leaf->left = new Node;
  59.                 leaf->left->keyValue = key;
  60.                 leaf->left->left = NULL;    //Sets the left child of the child node to null
  61.                 leaf->left->right = NULL;   //Sets the right child of the child node to null
  62.             }  
  63.      }
  64.      else if(key >= leaf->keyValue)
  65.      {
  66.             if(leaf->right!=NULL) insert(key, leaf->right);
  67.             else
  68.             {
  69.                 leaf->right = new Node;
  70.                 leaf->right->keyValue = key;
  71.                 leaf->right->left = NULL;  //Sets the left child of the child node to null
  72.                 leaf->right->right = NULL; //Sets the right child of the child node to null
  73.             }
  74.      }
  75. }
  76.  
  77. int BinaryTree::size(Node *leaf)
  78. {
  79.     if (leaf == NULL)
  80.     {
  81.              return(0);
  82.     }
  83.     else
  84.     {
  85.     return(size(leaf->left) + 1 + size(leaf->right));
  86.     }
  87. }
  88.  
  89. // computes the maxDepth
  90. int BinaryTree::maxDepth(Node* leaf)
  91. {
  92.     if (leaf == NULL)    return(0);
  93.     else
  94.     {
  95.     // depth of each subtree
  96.     int leftDepth = maxDepth(leaf->left);
  97.     int rightDepth = maxDepth(leaf->right);
  98.  
  99.     // use the larger one
  100.     if (leftDepth > rightDepth) return(leftDepth + 1);
  101.     else return(rightDepth + 1);
  102.     }
  103. }
  104.  
  105. int BinaryTree::height(Node *leaf)
  106. {
  107.     int heightOne = 0;
  108.     int heightTwo = 0;
  109.     if (leaf == NULL) return 0;
  110.     if (leaf->left) heightOne = height(leaf->left);
  111.     if (leaf->right) heightTwo = height(leaf->right);
  112.     int h = max(heightOne, heightTwo) + 1;
  113.     return h;
  114. }
  115.  
  116. void BinaryTree::printTree(Node *leaf)
  117. {
  118.      if (leaf == NULL) return;
  119.      printTree(leaf->left);
  120.      cout << " " << leaf->keyValue;
  121.      printTree(leaf->right);    
  122. }
  123.  
  124. void BinaryTree::printPostorder(Node *leaf)
  125. {
  126.      if (leaf == NULL) return;
  127.      // recursive call on both subtrees
  128.      printPostorder(leaf->left);
  129.      printPostorder(leaf->right);
  130.  
  131.      // then the node itself
  132.      cout << " " << leaf->keyValue;
  133.      
  134. }
  135.  
  136. void BinaryTree::insert(int key)
  137. {
  138.      if(root != NULL)
  139.      insert(key, root);
  140.      else
  141.      {
  142.          root = new Node;
  143.          root->keyValue = key;
  144.          root->left = NULL;
  145.          root->right = NULL;
  146.      }
  147. }
  148.  
  149. void BinaryTree::destroyTree()
  150. {
  151.      destroyTree(root);
  152. }
  153.  
  154. int main()
  155. {
  156.     BinaryTree exampleTree;
  157.     // inserting elements
  158.     for (int i = 1; i <= 10; i++)
  159.     {
  160.     exampleTree.insert(i);
  161.     }
  162.     cout << "Size: " << exampleTree.size(exampleTree.root) << endl;
  163.     cout << "Height: " << exampleTree.height(exampleTree.root) << endl;
  164.     cout << "Depth: " << exampleTree.maxDepth(exampleTree.root) << endl;
  165.     cout << "Print: ";
  166.     exampleTree.printTree(exampleTree.root);
  167.     cout << endl;
  168.     cout << "Postorder: ";
  169.     exampleTree.printPostorder(exampleTree.root);
  170.     cout << endl;
  171.     system("PAUSE");
  172.     return 0;
  173. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement