create_node
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3.  
  4. typedef struct _node{
  5.     int data;
  6.     struct _node *left;
  7.     struct _node *right;
  8. } NODE;
  9.  
  10. NODE *root;
  11.  
  12. NODE *create_node(int d){   //引数は整数データ
  13.     NODE *p;
  14.     p = (NODE *)malloc(sizeof(NODE));
  15.     p->data = d;
  16.     p->left = null;
  17.     p->right = null;
  18.     return p;   //戻り値は作った節点を示すポインタ
  19. }
  20.  
  21. /*
  22.     ここまでは課題のPDF参照
  23.     以下、適宜解説していく
  24. */
  25.  
  26. void insert_data(int d, double t){
  27.     if(root == null){   //rootがNULL, すなわち初めのデータが木に挿入されるとき
  28.         root = create_node(d);
  29.     }
  30.     else{               //rootがNULLでない, すなわち既にデータが木に存在するとき
  31.         double r;
  32.         NODE *p;
  33.         p = root;
  34.         while(p != null){   //pがNULLになるまでループ. しかし、pがNULLになることはプログラム上有り得ない. 試しに(p != NULL)を(1)にしてみても動く...はず.
  35.             r = (double)rand() / ((double)RAND_MAX + 1.0);  //0~1の間で乱数発生. 仕組みは前回の課題を参照. rをdouble型にするのを忘れずに.
  36.             if(r > t){
  37.                 if(p->right == null){
  38.                     p->right = create_node(d);
  39.                     return;
  40.                 }
  41.                 else{
  42.                     p = p->right;
  43.                 }
  44.             }
  45.             else{
  46.                 if(p->left == null){
  47.                     p->left = create_node(d);
  48.                     return;
  49.                 }
  50.                 else{
  51.                     p = p->left;
  52.                 }
  53.             }
  54.         }
  55.     }
  56. }
  57.  
  58. int total_depth(NODE *p, int depth){
  59.     int sum = 0;
  60.     if(p != null){
  61.         sum += total_depth(p->right, depth + 1);
  62.         sum += depth;
  63.         sum += total_depth(p->left, depth + 1);
  64.     }
  65.     return sum;
  66. }
  67.  
  68. int height(NODE *p, int depth){     //原理はtotal_depthとほぼ同じ. total_depthは深さを全て足し合わせて記録していたが, heightは深さの最高値 = 高さを記録し続ける.
  69.     int h = 0;
  70.     if(p != null){
  71.         h = depth;
  72.         int x;
  73.         x = height(p->right, depth + 1);
  74.         if(x > h) h = x;
  75.         x = height(p->left, depth + 1);
  76.         if(x > h) h = x;
  77.     }
  78.     return h;
  79. }
  80.  
  81. void print_detail(double n){    //関数名の通り. 引数はデータ数. 課題に必要なデータを, データ数を渡すだけで全て表示してくれる優れもの.
  82.     NODE *p;
  83.     p = root;
  84.     int x = total_depth(p, 0);
  85.     int y = height(p, 0);
  86.     printf("深さ合計: %dn深さ平均: %fn高さ:%dn", x, (double)x/n, y);
  87. }
  88.  
  89. void print_data(NODE *p, int depth){    //課題に関係ないが、ちゃんと木が作られているかを確認するための関数. 木を横にしたような出力になる.
  90.     if(p != null){
  91.         int i;
  92.         print_data(p->right, depth + 1);
  93.         for(i = 0; i < depth; i++){
  94.             printf("   ");
  95.         }
  96.         printf("%d(%d)n", p->data, depth);
  97.         print_data(p->left, depth + 1);
  98.     }
  99. }                                       //実はこれも原理はほぼtotal_depthと同じ. 何も記録し続けない代わりに, データを逐一出力するようにしているだけ.
  100.  
  101. void print_tree(void){                  //上のprint_dataを呼び出すためだけの関数. これでmain関数から楽に呼び出している.
  102.     NODE *p;
  103.     p = root;
  104.     print_data(p, 0);
  105. }
  106.  
  107. int main(){                            //mainは特に解説なし. 注意点として, print_treeを使うときはnを小さくして置いたほうがいい.
  108.     int i, n = 1000000;
  109.     srand(n+1);
  110.     for(i = 0; i < n; i++){
  111.         insert_data((double)rand() / ((double)RAND_MAX + 1.0) * n, 0.1);
  112.     }
  113.     print_detail(n);
  114.     //print_tree();
  115.     return 0;
  116. }
Parsed in 0.018 seconds