Advertisement
informaticage

Binary Search Tree C implementation OII

Oct 24th, 2019
294
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.39 KB | None | 0 0
  1. #include <stdio.h>
  2.  
  3. /**
  4.     Defining a node
  5. **/
  6. struct node {
  7.     char data;
  8.     struct node *left;
  9.     struct node *right;
  10. };
  11.  
  12. typedef struct node Node;
  13.  
  14. /// Tree construction
  15. Node* new_node ( char );
  16.  
  17. /*** BST only functions **/
  18. Node* search ( Node*, char );
  19.  
  20. Node* insert ( Node*, char );
  21. /**
  22.     Dept first search
  23. **/
  24. /// Dept first search in order
  25. void dfs_in_order ( Node* );
  26.  
  27. /// Dept first search pre order
  28. void dfs_pre_order ( Node* );
  29.  
  30. /// Dept first search post order
  31. void dfs_post_order ( Node* );
  32.  
  33. int main ( void )
  34. {
  35.     Node *root = new_node( 'H' );
  36.  
  37.     insert ( root, 'B' );
  38.     insert ( root, 'Z' );
  39.     insert ( root, 'D' );
  40.     insert ( root, 'F' );
  41.     insert ( root, 'C' );
  42.  
  43.     printf ( "DFS Pre order: \n" );
  44.     dfs_pre_order( root );
  45.  
  46.     printf ( "\nDFS In order: \n" );
  47.     dfs_in_order( root );
  48.  
  49.     printf ( "\nDFS Post order: \n" );
  50.     dfs_post_order( root );
  51.  
  52.     return 0;
  53. }
  54.  
  55. Node* search ( Node* tree, char data ) {
  56.     if ( tree == NULL || tree->data == data )
  57.         return tree;
  58.  
  59.     if ( data > tree->data )
  60.         return search ( tree->right, data );
  61.  
  62.     return search ( tree->left, data );
  63. }
  64.  
  65. Node* new_node ( char data ) {
  66.     Node *new_node = ( Node* ) malloc ( sizeof ( Node ) );
  67.  
  68.     new_node->data = data;
  69.     new_node->left = NULL;
  70.     new_node->right = NULL;
  71.  
  72.     return new_node;
  73. }
  74.  
  75. Node* insert ( Node* tree, char data ) {
  76.     if ( tree == NULL ) return new_node( data );
  77.  
  78.     if ( tree->data < data )
  79.         tree->left = insert ( tree->left, data );
  80.  
  81.     if ( tree->data > data )
  82.         tree->right = insert ( tree->right, data );
  83.  
  84.     return tree;
  85. }
  86.  
  87. void dfs_in_order ( Node *tree ) {
  88.     /// Root
  89.     if ( tree == NULL )
  90.         return;
  91.  
  92.     /// Left subtree
  93.     dfs_in_order( tree->left );
  94.  
  95.     printf ( "%c ", tree->data );
  96.  
  97.     /// Right subtree
  98.     dfs_in_order( tree->right );
  99. }
  100.  
  101. void dfs_pre_order ( Node *tree ) {
  102.     /// Root
  103.     if ( tree == NULL )
  104.         return;
  105.  
  106.     printf ( "%c ", tree->data );
  107.  
  108.     /// Left subtree
  109.     dfs_pre_order( tree->left );
  110.  
  111.     /// Right subtree
  112.     dfs_pre_order( tree->right );
  113. }
  114.  
  115. void dfs_post_order ( Node *tree ) {
  116.     /// Root
  117.     if ( tree == NULL )
  118.         return;
  119.  
  120.     /// Left subtree
  121.     dfs_post_order( tree->left );
  122.  
  123.     /// Right subtree
  124.     dfs_post_order( tree->right );
  125.  
  126.     printf ( "%c ", tree->data );
  127. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement