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:

Pre-order: 10 3 8 7 5 20
In-order: 3 5 7 8 10 20
Post-order: 5 7 8 3 20 10

Enjoy!

Download