C Program to Implement a B Tree

This C Program constructs a binary tree.

Here is source code of the C Program to construct a binary tree. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C Program to Construct a B Tree
  3.  */
  4.  
  5. /***************************
  6.  * binarytree.h
  7.  ***************************/
  8.  
  9. typedef char DATA;
  10.  
  11. struct node
  12. {
  13. 	DATA d;
  14. 	struct node *left;
  15. 	struct node *right;
  16. };
  17.  
  18. typedef struct node NODE;
  19. typedef NODE *BTREE;
  20.  
  21. BTREE newnode(void);
  22. BTREE init_node(DATA d, BTREE p1, BTREE p2);
  23. BTREE create_tree(DATA a[], int i, int size);
  24. void preorder (BTREE root);
  25. void inorder (BTREE root);
  26. void postorder (BTREE root);
  27.  
  28. /**********************
  29.  * binarytree.c:
  30.  ***********************/
  31. #include <assert.h>
  32. #include <stdio.h>
  33. #include <stdlib.h>
  34. #include "binarytree.h"
  35.  
  36. BTREE new_node()
  37. {
  38.     return ((BTREE)malloc(sizeof(NODE)));
  39. }
  40.  
  41. BTREE init_node(DATA d1, BTREE p1, BTREE p2)
  42. {
  43.     BTREE t;
  44.  
  45.     t = new_node();
  46.     t->d = d1;
  47.     t->left = p1;
  48.     t->right = p2;
  49.     return t;
  50. }
  51.  
  52. /* create a linked binary tree from an array */
  53. BTREE create_tree(DATA a[], int i, int size)
  54. {
  55.     if (i >= size)
  56.         return NULL;
  57.     else
  58.         return(init_node(a[i],
  59.     create_tree(a, 2*i+1, size),
  60.     create_tree(a, 2*i+2, size)));
  61. }
  62.  
  63. /* preorder traversal */
  64. void preorder (BTREE root)
  65. {
  66.     if (root != NULL) {
  67.         printf("%c ", root->d);
  68.         preorder(root -> left);
  69.         preorder(root -> right);
  70.     }
  71. }
  72.  
  73. /* Inorder traversal */
  74. void inorder (BTREE root)
  75. {
  76.     if (root != NULL) {
  77.         inorder(root -> left);
  78.         printf("%c ", root->d);
  79.         inorder(root -> right);
  80.     }
  81. }
  82.  
  83. /* postorder binary tree traversal */
  84.  
  85. void postorder (BTREE root)
  86. {
  87.     if (root != NULL) {
  88.         postorder(root -> left);
  89.         postorder(root -> right);
  90.         printf("%c ", root->d);
  91.     }
  92. }
  93.  
  94. /***************************
  95.  * pgm.c
  96.  ***************************/
  97. #include <assert.h>
  98. #include <stdio.h>
  99. #include <stdlib.h>
  100.  
  101. #include "binarytree.c"
  102. #define ARRAY_SIZE 10
  103. int main(void)
  104. {
  105.     char a[ARRAY_SIZE] = {'g','d','i','b','f','h','j','a','c','e'};
  106.     BTREE root;
  107.  
  108.     root = create_tree(a, 0, ARRAY_SIZE) ;
  109.     assert(root != NULL);
  110.     printf("PREORDER\n");
  111.     preorder(root);
  112.     printf("\n");
  113.     printf("INORDER\n");
  114.     inorder(root);
  115.     printf("\n");
  116.  
  117.     printf("POSTORDER\n");
  118.     postorder(root);
  119.     printf("\n");
  120. }

$ cc pgm61.c
$ a.out
PREORDER
g d b a c f e i h j
INORDER
a b c d e f g h i j
POSTORDER
a c b e f d h j i g

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement
advertisement

Here’s the list of Best Books in C Programming, Data-Structures and Algorithms

If you wish to look at other example programs on Trees, go to Trees. If you wish to look at programming examples on all topics, go to C Programming Examples.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.