fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4.  #define COUNT 10
  5. // Data structure to store a binary tree node
  6. struct Node
  7. {
  8.     char key;
  9.     struct Node *left, *right;
  10. };
  11.  
  12. // Function to create a new binary tree node having a given key
  13. struct Node* newNode(char key)
  14. {
  15.     struct Node* node = (struct Node*)malloc(sizeof(struct Node));
  16.     node->key = key;
  17.     node->left = node->right = NULL;
  18.  
  19.     return node;
  20. }
  21.  
  22. // Recursive function to perform inorder traversal on a given binary tree
  23. void inorder(struct Node* root)
  24. {
  25.     if (root == NULL) {
  26.         return;
  27.     }
  28.  
  29.     inorder(root->left);
  30.     printf("%c ", root->key);
  31.     inorder(root->right);
  32. }
  33.  
  34. void postorder(struct Node* root) {
  35. 	if(root == NULL)	return;
  36.  
  37. 	postorder(root->left);
  38. 	postorder(root->right);
  39. 	printf("%c ", root->key);
  40. }
  41.  
  42. // Recursive function to build a BST from a preorder sequence.
  43. struct Node* constructBST(char preorder[], int start, int end)
  44. {
  45.     // base case
  46.     if (start > end) {
  47.         return NULL;
  48.     }
  49.  
  50.     // Construct the root node of the subtree formed by keys of the
  51.     // preorder sequence in range `[start, end]`
  52.     struct Node* node = newNode(preorder[start]);
  53.  
  54.     // search the index of the first element in the current range of preorder
  55.     // sequence larger than the root node's value
  56.     int i;
  57.     for (i = start; i <= end; i++)
  58.     {
  59.         if (preorder[i] > node->key) {
  60.             break;
  61.         }
  62.     }
  63.  
  64.     // recursively construct the left subtree
  65.     node->left = constructBST(preorder, start + 1, i - 1);
  66.  
  67.     // recursively construct the right subtree
  68.     node->right = constructBST(preorder, i, end);
  69.  
  70.     // return current node
  71.     return node;
  72. }
  73.  
  74. void print2DUtil(Node *root, int space)
  75. {
  76.     // Base case
  77.     if (root == NULL)
  78.         return;
  79.  
  80.     // Increase distance between levels
  81.     space += COUNT;
  82.  
  83.     // Process right child first
  84.     print2DUtil(root->right, space);
  85.  
  86.     // Print current node after space
  87.     // count
  88.     printf("\n");
  89.     for (int i = COUNT; i < space; i++)
  90.         printf(" ");
  91.     printf("%c\n", root->key);
  92.  
  93.     // Process left child
  94.     print2DUtil(root->left, space);
  95. }
  96.  
  97. // Wrapper over print2DUtil()
  98. void print2D(Node *root)
  99. {
  100.     // Pass initial space count as 0
  101.     print2DUtil(root, 0);
  102. }
  103.  
  104. int main(void)
  105. {
  106.     /* Construct the following BST
  107.               15
  108.             /    \
  109.            /      \
  110.           10       20
  111.          /  \     /  \
  112.         /    \   /    \
  113.        8     12 16    25
  114.     */
  115.  
  116.     char preorder[] = { 'O', 'P', 'Q', 'R', 'S', 'T' };
  117.     int n = sizeof(preorder)/sizeof(preorder[0]);
  118.  
  119.     // construct the BST
  120.     struct Node* root = constructBST(preorder, 0, n - 1);
  121.  
  122.     // print the BST
  123.     printf("Inorder traversal of BST is ");
  124.  
  125.     // inorder on the BST always returns a sorted sequence
  126.     inorder(root);
  127.  
  128.     printf("Postorder: ");
  129.     postorder(root);
  130.  
  131.     print2D(root);
  132.  
  133.     return 0;
  134. }
Success #stdin #stdout 0s 5516KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Inorder traversal of BST is O P Q R S T Postorder: T S R Q P O 
                                                  T

                                        S

                              R

                    Q

          P

O
https://ideone.com/MkBJZs
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!