Simple Binary Tree in C++ - Part 1

Submitted by DoctorSpeedCode on Wednesday, August 13, 2014 - 06:07.
Today we are about to see how simple and fast it is to build a binary tree in C++. Binary trees are generally useful when you need a quick search in a given data set. The tree we are creating is with an int value, but you can change to any other type! First, we need the following declarations: 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. typedef struct x {
  6.     int value;
  7.     struct x *L, *R;
  8. } leaf;
As you can see, we have defined the leaf structure. It holds a value, and 2 pointers (L and R) to the left and right leaf, respectively. Now, we will define the insert method. In the next tutorial, we are going to define the other operations too! 
  1. void insert(leaf *&currentLeaf, int val) {
  2.     if (currentLeaf == NULL) {
  3.         currentLeaf = new leaf;
  4.         currentLeaf->value = val;
  5.         currentLeaf->L = NULL;
  6.         currentLeaf->R = NULL;
  7.     } else {
  8.         if (val < currentLeaf->value) {
  9.             insert(currentLeaf->L, val);
  10.         } else {
  11.             insert(currentLeaf->R, val);
  12.         }
  13.     }
  14. }
As you can see, right from the beginning (insert) the data is sorted based on a simple rule: if the value is smaller, it's the left leaf, if it's larger then it's the right leaf. It is a recursive function, but very simple to comprehend. We also define 3 routines for outputting leafs in pre-, in-, and post-order. 
  1. void printPreOrder(leaf *currentLeaf) {
  2.     if (currentLeaf == NULL) {
  3.         return;
  4.     }
  5.     cout << currentLeaf->value << " ";
  6.     printPreOrder(currentLeaf->L);
  7.     printPreOrder(currentLeaf->R);
  8. }
  9.  
  10. void printInOrder(leaf *currentLeaf) {
  11.     if (currentLeaf == NULL) {
  12.         return;
  13.     }
  14.     printInOrder(currentLeaf->L);
  15.     cout << currentLeaf->value << " ";
  16.     printInOrder(currentLeaf->R);
  17. }
  18.  
  19. void printPostOrder(leaf *currentLeaf) {
  20.     if (currentLeaf == NULL) {
  21.         return;
  22.     }
  23.     printPostOrder(currentLeaf->L);
  24.     printPostOrder(currentLeaf->R);
  25.     cout << currentLeaf->value << " ";
  26. }
The 3 routines are almost identical - the only difference is when the leaf value is printed! We have created a test program to insert some numbers and then output the tree calling all 3 output methods (orders). Here is the full source code for main.cpp: 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. typedef struct x {
  6.     int value;
  7.     struct x *L, *R;
  8. } leaf;
  9.  
  10. void insert(leaf *&currentLeaf, int val) {
  11.     if (currentLeaf == NULL) {
  12.         currentLeaf = new leaf;
  13.         currentLeaf->value = val;
  14.         currentLeaf->L = NULL;
  15.         currentLeaf->R = NULL;
  16.     } else {
  17.         if (val < currentLeaf->value) {
  18.             insert(currentLeaf->L, val);
  19.         } else {
  20.             insert(currentLeaf->R, val);
  21.         }
  22.     }
  23. }
  24.  
  25. void printPreOrder(leaf *currentLeaf) {
  26.     if (currentLeaf == NULL) {
  27.         return;
  28.     }
  29.     cout << currentLeaf->value << " ";
  30.     printPreOrder(currentLeaf->L);
  31.     printPreOrder(currentLeaf->R);
  32. }
  33.  
  34. void printInOrder(leaf *currentLeaf) {
  35.     if (currentLeaf == NULL) {
  36.         return;
  37.     }
  38.     printInOrder(currentLeaf->L);
  39.     cout << currentLeaf->value << " ";
  40.     printInOrder(currentLeaf->R);
  41. }
  42.  
  43. void printPostOrder(leaf *currentLeaf) {
  44.     if (currentLeaf == NULL) {
  45.         return;
  46.     }
  47.     printPostOrder(currentLeaf->L);
  48.     printPostOrder(currentLeaf->R);
  49.     cout << currentLeaf->value << " ";
  50. }
  51.  
  52. int main(int argc, char** argv) {
  53.     leaf *treeRoot = NULL;
  54.  
  55.     insert(treeRoot, 10);
  56.     insert(treeRoot, 3);
  57.     insert(treeRoot, 8);
  58.     insert(treeRoot, 7);
  59.     insert(treeRoot, 20);
  60.     insert(treeRoot, 5);
  61.  
  62.     cout << "Pre-order: ";
  63.     printPreOrder(treeRoot);
  64.     cout << endl;
  65.     cout << "In-order: ";
  66.     printInOrder(treeRoot);
  67.     cout << endl;
  68.     cout << "Post-order: ";
  69.     printPostOrder(treeRoot);
  70.     cout << endl;
  71.  
  72.     return 0;
  73. }
The output is the following: 
  1. Pre-order: 10 3 8 7 5 20 
  2. In-order: 3 5 7 8 10 20 
  3. Post-order: 5 7 8 3 20 10
Enjoy!

Tags

Add new comment

About text formats
  • 27 views