fork(1) download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. struct bst {
  5.    int value;
  6.    struct bst* left;
  7.    struct bst* right;
  8. };
  9.  
  10. void bst_add2(struct bst*, struct bst*);
  11. void bst_add(struct bst** tree, int value);
  12. int bst_search(struct bst* tree, int value);
  13. int bst_getCount(struct bst* tree);
  14. int bst_getDepth(struct bst* tree);
  15. int bst_getMin(struct bst* tree);
  16. int bst_getMax(struct bst* tree);
  17. void bst_print(struct bst* tree);
  18. void command_search(struct bst* tree);
  19. void command_add(struct bst** tree);
  20. void command_print(struct bst* tree);
  21. void question2(void);
  22. void question3(void);
  23. void question4(void);
  24.  
  25. void bst_add2(struct bst* tree, struct bst* n) {
  26.    if (n->value < tree->value) {
  27.       if (tree->left == NULL) {
  28.          tree->left = n;
  29.       } else {
  30.          bst_add2(tree->left, n);
  31.       }
  32.    } else {
  33.       if (tree->right == NULL) {
  34.          tree->right = n;
  35.       } else {
  36.          bst_add2(tree->right, n);
  37.       }
  38.    }
  39. }
  40.  
  41. void bst_add(struct bst** tree, int value) {
  42.    struct bst* n;
  43.  
  44.    n = malloc(sizeof(struct bst));
  45.    n->value = value;
  46.    n->left = NULL;
  47.    n->right = NULL;
  48.  
  49.    if (*tree == NULL) {
  50.       *tree = n;
  51.    } else {
  52.       bst_add2(*tree, n);
  53.    }
  54. }
  55.  
  56. int bst_search(struct bst* tree, int value) {
  57.    if (tree == NULL) {
  58.       return 0;
  59.    }
  60.    if (value < tree->value) {
  61.       return bst_search(tree->left, value);
  62.    } else if (tree->value < value) {
  63.       return bst_search(tree->right, value);
  64.    } else {
  65.       return 1;
  66.    }
  67. }
  68.  
  69. int bst_getCount(struct bst* tree) {
  70.    if (tree == NULL) {
  71.       return 0;
  72.    } else {
  73.       return bst_getCount(tree->left) + bst_getCount(tree->right) + 1;
  74.    }
  75. }
  76.  
  77. int bst_getDepth(struct bst* tree) {
  78.    int l;
  79.    int r;
  80.    if (tree == NULL) {
  81.       return 0;
  82.    } else {
  83.       l = bst_getDepth(tree->left);
  84.       r = bst_getDepth(tree->right);
  85.       if (l < r) {
  86.          return r + 1;
  87.       } else {
  88.          return l + 1;
  89.       }
  90.    }
  91. }
  92.  
  93. int bst_getMin(struct bst* tree) {
  94.    if (tree == NULL) {
  95.       return -1;
  96.    } else {
  97.       if (tree->left == NULL) {
  98.          return tree->value;
  99.       } else {
  100.          return bst_getMin(tree->left);
  101.       }
  102.    }
  103. }
  104.  
  105. int bst_getMax(struct bst* tree) {
  106.    if (tree == NULL) {
  107.       return -1;
  108.    } else {
  109.       if (tree->right == NULL) {
  110.          return tree->value;
  111.       } else {
  112.          return bst_getMax(tree->right);
  113.       }
  114.    }
  115. }
  116.  
  117. void bst_print(struct bst* tree) {
  118.    if (tree == NULL) {
  119.       return;
  120.    }
  121.    bst_print(tree->left);
  122.    printf("%d\n", tree->value);
  123.    bst_print(tree->right);
  124. }
  125.  
  126. void command_search(struct bst* tree) {
  127.    int n;
  128.    printf("search\n");
  129.    printf("data>");
  130.    scanf("%d%*c", &n);
  131.    if (bst_search(tree, n)) {
  132.       printf("data already exists\n");
  133.    } else {
  134.       printf("data does not exist\n");
  135.    }
  136. }
  137.  
  138. void command_add(struct bst** tree) {
  139.    int n;
  140.    printf("add\n");
  141.    printf("data>");
  142.    scanf("%d%*c", &n);
  143.    printf("n:%d\n", n);
  144.    bst_add(tree, n);
  145. }
  146.  
  147. void command_print(struct bst* tree) {
  148.    printf("print\n");
  149.    bst_print(tree);
  150. }
  151.  
  152. void question2(void) {
  153.    struct bst* tree;
  154.    tree = NULL;
  155.    bst_add(&tree, 6);
  156.    bst_add(&tree, 4);
  157.    bst_add(&tree, 3);
  158.    bst_add(&tree, 8);
  159.    bst_add(&tree, 5);
  160.    bst_add(&tree, 9);
  161.    bst_add(&tree, 7);
  162.    bst_print(tree);
  163. }
  164.  
  165. void question3(void) {
  166.    struct bst* tree;
  167.    char c;
  168.    tree = NULL;
  169.    while (1) {
  170.       printf("s:search, i:add, p:print, q:quit\n");
  171.       printf("command>");
  172.       scanf("%c%*c", &c);
  173.       if (c == 's') {
  174.          command_search(tree);
  175.       } else if (c == 'i') {
  176.          command_add(&tree);
  177.       } else if (c == 'p') {
  178.          command_print(tree);
  179.       } else if (c == 'q') {
  180.          break;
  181.       }
  182.    }
  183. }
  184.  
  185. void question4(void) {
  186.    struct bst* tree;
  187.    int i;
  188.    tree = NULL;
  189.    for (i = 0; i < 10000; i++) {
  190.       bst_add(&tree, rand() % 10000);
  191.    }
  192.    printf("データの総数 %d\n", bst_getCount(tree));
  193.    printf("木の深さの最大値 %d\n", bst_getDepth(tree));   
  194.    printf("データの最小値 %d\n", bst_getMin(tree));   
  195.    printf("データの最大値 %d\n", bst_getMax(tree));
  196. }
  197.  
  198. int main(void) {
  199.    question2();
  200.    question3();
  201.    question4();
  202.    return EXIT_SUCCESS;
  203. }
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/G1KlHt
language:
C (gcc 8.3)
created:
11 years 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!