C 13
Tree.c Guest on 5th April 2021 10:54:33 AM
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <assert.h>
  4.  
  5. typedef struct node {
  6.   char key;
  7.   struct node *p;
  8.   struct node *left;
  9.   struct node *right;
  10. } mynode;
  11.  
  12. mynode *root=NULL;
  13.  
  14. void preorder_tree_walk(mynode *x) {
  15.   if (x!=NULL) {
  16.     printf("node: %c\n", x->key);
  17.     preorder_tree_walk(x->left);
  18.     preorder_tree_walk(x->right);
  19.   }
  20. }
  21.  
  22. void inorder_tree_walk(mynode *x) {
  23.   if (x!=NULL) {
  24.     inorder_tree_walk(x->left);
  25.     printf("node: %c\n", x->key);
  26.     inorder_tree_walk(x->right);
  27.   }
  28. }
  29.  
  30. void posorder_tree_walk(mynode *x) {
  31.   if (x!=NULL) {
  32.     posorder_tree_walk(x->left);
  33.     posorder_tree_walk(x->right);
  34.     printf("node: %c\n", x->key);
  35.   }
  36. }
  37.  
  38. int insert(mynode *z, char key) {
  39.   mynode *y, *x;
  40.   z = (mynode*) malloc(sizeof(mynode));
  41.   z->key=key; z->left=NULL; z->right=NULL; y = NULL; x=root;
  42.   while (x != NULL) {
  43.     y = x;
  44.     if (z->key < x->key) x = x->left;
  45.     else x = x->right;
  46.   }
  47.  
  48.   z->p = y;
  49.   if (y==NULL) {root = z; root->left=NULL; root->right=NULL;}
  50.   else if (z->key < y->key) y->left = z;
  51.   else if (z->key > y->key) y->right = z;
  52.  
  53.   return 0;
  54. }
  55.  
  56. mynode* tree_search(mynode *x, int k) {
  57.   if (x == NULL || k == x->key)
  58.     return x;
  59.   if (k < x->key)
  60.     tree_search(x->left, k);
  61.   else
  62.     tree_search(x->right,k);
  63. }
  64.  
  65. mynode* tree_minimum(mynode *x) {
  66.   while (x->left != NULL)
  67.     x=x->left;
  68.   return x;
  69. }
  70.  
  71. mynode* tree_maximum(mynode *x) {
  72.   while (x->right != NULL)
  73.     x=x->right;
  74.   return x;
  75. }
  76.  
  77. int main(void) {
  78.   mynode *t;
  79.   insert(t, 'F');
  80.   insert(t, 'C');
  81.   insert(t, 'E');
  82.   insert(t, 'L');
  83.   insert(t, 'G');
  84.   insert(t, 'A');
  85.   insert(t, 'B');
  86.   insert(t, 'I');
  87.   insert(t, 'H');
  88.   insert(t, 'J');
  89.   printf("### inorder_tree_walk: \n");
  90.   inorder_tree_walk(root);
  91.   printf("### preorder_tree_walk: \n");
  92.   preorder_tree_walk(root);
  93.   printf("### posorder_tree_walk: \n");
  94.   posorder_tree_walk(root);
  95.   t = tree_search(root,'A');
  96.   assert(t->key == 'A');
  97.   printf("### tree_search: %c = %c\n", 'A', t->key);
  98.   t = tree_minimum(root);
  99.   assert(t->key == 'A');
  100.   printf("### tree_minimum: %c\n", t->key);
  101.   t = tree_maximum(root);
  102.   assert(t->key == 'L');
  103.   printf("### tree_maximum: %c\n", t->key);
  104.  
  105.   return 0;
  106. }

Paste-bin is for source code and general debugging text.

Login or Register to edit, delete and keep track of your pastes and more.

Raw Paste

Login or Register to edit or fork this paste. It's free.