Chinaunix首页 | 论坛 | 博客

丫叩酱的ChinaUnix博客yakou.blog.chinaunix.net

首页　| 　博文目录　| 　关于我

丫叩酱

  • 博客访问： 476553
  • 博文数量： 112
  • 博客积分： 2436
  • 博客等级： 大尉
  • 技术积分： 2769
  • 用 户 组： 普通用户
  • 注册时间： 2012-03-04 19:48
文章分类

全部博文（112）

文章存档

2013年（7）

2012年（105）

我的朋友
最近访客
推荐博文
相关博文
二叉树 _0313

分类： C/C++

2012-03-22 16:30:13


点击(此处)折叠或打开

  1. //bin_tree_create.c

  3. //以先序和中序唯一确定一个二叉树，然后以先序、中序、后序和层次遍历输出二叉树（遍历输出时向先序、中序、后序和层次传递一个(输出)函数指针）

  5. #include <stdio.h>
  6. #include <stdlib.h>
  7. #include <assert.h>

  9. typedef struct btree
  10. {
  11.     int item;
  12.     struct btree *l, *r;
  13. }btree_t;


  16. int menu(void)
  17. {
  18.    int choice;

  20.    printf("menu:\n");
  21.    printf("0: exit\n1: print\n");
  22.    printf("Please make a choice:");
  23.    scanf("%d", &choice);

  25.    return choice;
  26. }

  28. int menu_print(void)
  29. {
  30.     int choice;

  32.     printf("0: exit\n1: pre_order\n2: in_order\n3: post_order\n4: dep_order\n");
  33.     printf("Please maka a print_choice:");
  34.     scanf("%d", &choice);

  36.     return choice;
  37. }

  39. btree_t *make_node(int item)
  40. {
  41.     btree_t *bt;

  43.     bt = malloc(sizeof(btree_t));
  44.     assert(bt);
  45.     
  46.     bt->item = item;
  47.     bt->l = NULL;
  48.     bt->r = NULL;

  50.     return bt;
  51. }

  53. btree_t *create_tree(int *pre, int *in, int n)
  54. {
  55.    int k;
  56.    btree_t *bt;

  58.    if(n == 0)
  59.         return NULL;

  61.    for(k = 0; pre[0] != in[k]; k++);

  63.    bt = make_node(pre[0]) ;
  64.    bt->l = create_tree(pre + 1, in, k);
  65.    bt->r = create_tree(pre + k + 1, in + k + 1, n - k -1 );

  67.    return bt;
  68. }

  70. void pre_order(btree_t *root, void (*visit)(btree_t *))
  71. {
  72.     if(root == NULL)
  73.         return ;
  74.     visit(root);
  75.     pre_order(root->l, visit);
  76.     pre_order(root->r, visit);
  77. }

  79. void in_order(btree_t *root, void (*visit)(btree_t *))
  80. {
  81.     if(root == NULL)
  82.         return ;
  83.     in_order(root->l, visit);
  84.     visit(root);
  85.     in_order(root->r, visit);
  86. }

  88. void post_order(btree_t *root, void (*visit)(btree_t *))
  89. {
  90.     if(root == NULL)
  91.         return ;
  92.     post_order(root->l, visit);
  93.     post_order(root->r, visit);
  94.     visit(root);
  95. }

  97. void dep_ord(btree_t *root, void (*visit)(btree_t *))
  98. {
  99.    if(root->l != NULL)
  100.         visit(root->l);
  101.    if(root->r != NULL)
  102.         visit(root->r);

  104.    if(root->l != NULL)
  105.         dep_ord(root->l, visit);
  106.    if(root->r != NULL)
  107.         dep_ord(root->r, visit);
  108. }

  110. void dep_order(btree_t *root, void (*visit)(btree_t *))
  111. {
  112.     if(root == NULL)
  113.         return ;
  114.     visit(root);
  115.     dep_ord(root, visit);
  116. }

  118. void print(btree_t *bt)
  119. {
  120.     printf("%d ", bt->item);
  121. }


  124. int main(int argc, const char *argv[])
  125. {
  126.     btree_t *root;

  128.     int pre[] = {4, 2, 1, 3, 5, 6};
  129.     int in[] = {1, 2, 3, 4, 5, 6};

  131.     root = create_tree(pre, in, sizeof(pre)/sizeof(int));
  132.     while(1)
  133.     {
  134.         switch(menu())
  135.         {
  136.             case 0:return 0;
  137.             case 1:
  138.             {
  139.                 while(1)
  140.                 {
  141.                     int flag = 0;
  142.                     switch(menu_print())
  143.                     {
  144.                         case 0:flag = 1;break;
  145.                         case 1:
  146.                                {
  147.                                    printf("pre_order:");
  148.                                    pre_order(root, print);
  149.                                    putchar('\n');
  150.                                    break;
  151.                                }
  152.                         case 2:
  153.                                {
  154.                                    printf("in_order:");
  155.                                    in_order(root, print);
  156.                                    putchar('\n');
  157.                                    break;
  158.                                }
  159.                         case 3:
  160.                                {
  161.                                    printf("post_order:");
  162.                                    post_order(root, print);
  163.                                    putchar('\n');
  164.                                    break;
  165.                         case 4:
  166.                                {
  167.                                    printf("dep_order:");
  168.                                    dep_order(root, print);
  169.                                    putchar('\n');
  170.                                    break;
  171.                                }
  172.                                }
  173.                         default:;
  174.                     }
  175.                     if(flag == 1)
  176.                         break;
  177.                 }
  178.                 break;
  179.             }

  181.             default:;
  182.         }
  183.     }

  185.     return 0;
  186. }

点击(此处)折叠或打开

  1. //btree.c

  3. //要求：
  4. //以先序和中序唯一确定一个二叉树
  5. //实现以先序、中序、后序和层次输出二叉树
  6. //实现插入和删除节点
  7. //求二叉树的深度
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <assert.h>

  5. typedef struct btree
  6. {
  7.     int item;
  8.     struct btree *l, *r;
  9. }btree_t;


  12. int menu(void)
  13. {
  14.    int choice;

  16.    printf("menu:\n");
  17.    printf("0: exit\n1: print\n2: insert\n3: delete\n4: depth\n");
  18.    printf("Please make a choice:");
  19.    scanf("%d", &choice);

  21.    return choice;
  22. }

  24. int menu_print(void)
  25. {
  26.     int choice;

  28.     printf("print menu:\n0: exit\n1: pre_order\n2: in_order\n3: post_order\n4: dep_order\n");
  29.     printf("Please maka a print_choice:");
  30.     scanf("%d", &choice);

  32.     return choice;
  33. }

  35. btree_t *make_node(int item)
  36. {
  37.     btree_t *bt;

  39.     bt = malloc(sizeof(btree_t));
  40.     assert(bt);
  41.     
  42.     bt->item = item;
  43.     bt->l = NULL;
  44.     bt->r = NULL;

  46.     return bt;
  47. }

  49. btree_t *create_tree(int *pre, int *in, int n)
  50. {
  51.    int k;
  52.    btree_t *bt;

  54.    if(n == 0)
  55.         return NULL;

  57.    for(k = 0; pre[0] != in[k]; k++);

  59.    bt = make_node(pre[0]) ;
  60.    bt->l = create_tree(pre + 1, in, k);
  61.    bt->r = create_tree(pre + k + 1, in + k + 1, n - k -1 );

  63.    return bt;
  64. }

  66. void pre_order(btree_t *root)
  67. {
  68.     if(root == NULL)
  69.         return ;
  70.     printf("%d ", root->item);
  71.     pre_order(root->l);
  72.     pre_order(root->r);
  73. }

  75. void in_order(btree_t *root)
  76. {
  77.     if(root == NULL)
  78.         return ;
  79.     in_order(root->l);
  80.     printf("%d ", root->item);
  81.     in_order(root->r);
  82. }

  84. void post_order(btree_t *root)
  85. {
  86.     if(root == NULL)
  87.         return ;
  88.     post_order(root->l);
  89.     post_order(root->r);
  90.     printf("%d ", root->item);
  91. }

  93. void dep_ord(btree_t *root)
  94. {
  95.    if(root->l != NULL)
  96.         printf("%d ", root->l->item);
  97.    if(root->r != NULL)
  98.         printf("%d ", root->r->item);

  100.    if(root->l != NULL)
  101.         dep_ord(root->l);
  102.    if(root->r != NULL)
  103.         dep_ord(root->r);
  104. }

  106. void dep_order(btree_t *root)
  107. {
  108.     if(root == NULL)
  109.         return ;
  110.     printf("%d ", root->item);
  111.     dep_ord(root);
  112. }

  114. int depth(btree_t *root)
  115. {
  116.     int dl, dr;

  118.     if(root == NULL)
  119.         return 0;
  120.     dl = depth(root->l) ;
  121.     dr = depth(root->r);

  123.     return 1 + (dl > dr? dl : dr);
  124. }


  127. btree_t *insert(btree_t *root, int key)
  128. {
  129.     if(! root)
  130.         return make_node(key);
  131.     if(root->item > key)
  132.         root->l = insert(root->l, key);
  133.     if(root->item < key)
  134.         root->r = insert(root->r, key);
  135.     return root;
  136. }

  138. btree_t *delete(btree_t *root, int key)
  139. {
  140.     if(! root)
  141.         return NULL;
  142.     if(root->item > key)
  143.         root->l = delete(root->l, key);
  144.     else
  145.         if(root->item < key)
  146.             root->r = delete(root->r, key);
  147.         else
  148.         {
  149.             if(root->l == NULL && root->r == NULL)
  150.             {
  151.                 free(root);
  152.                 root = NULL;
  153.             }
  154.             else
  155.                 if(root->l)
  156.                 {
  157.                     btree_t *p;
  158.                     for(p = root->l; p->r; p = p->r);
  159.                     root->item = p->item;

  161.                     root->l = delete(root->l, p->item);
  162.                 }
  163.                 else if(root->r)
  164.                 {
  165.                     btree_t *p;
  166.                     for(p = root->r; p->l; p = p->l);
  167.                     root->item = p->item;

  169.                     root->r = delete(root->r, p->item);
  170.                 }
  171.         }
  172.     return root;
  173. }

  175. int main(int argc, const char *argv[])
  176. {
  177.     btree_t *root;

  179.     int pre[] = {40, 20, 10, 30, 50, 60};
  180.     int in[] = {10, 20, 30, 40, 50, 60};

  182.     root = create_tree(pre, in, sizeof(pre)/sizeof(int));
  183.     while(1)
  184.     {
  185.         switch(menu())
  186.         {
  187.             case 0:return 0;
  188.             case 1:
  189.             {
  190.                 while(1)
  191.                 {
  192.                     int flag = 0;
  193.                     switch(menu_print())
  194.                     {
  195.                         case 0:flag = 1;break;
  196.                         case 1:
  197.                                {
  198.                                    printf("pre_order:");
  199.                                    pre_order(root);
  200.                                    putchar('\n');
  201.                                    break;
  202.                                }
  203.                         case 2:
  204.                                {
  205.                                    printf("in_order:");
  206.                                    in_order(root);
  207.                                    putchar('\n');
  208.                                    break;
  209.                                }
  210.                         case 3:
  211.                                {
  212.                                    printf("post_order:");
  213.                                    post_order(root);
  214.                                    putchar('\n');
  215.                                    break;
  216.                         case 4:
  217.                                {
  218.                                    printf("dep_order:");
  219.                                    dep_order(root);
  220.                                    putchar('\n');
  221.                                    break;
  222.                                }
  223.                                }
  224.                         default:;
  225.                     }
  226.                     if(flag == 1)
  227.                         break;
  228.                 }
  229.                 break;
  230.             }
  231.             case 2:
  232.             {

  234.                 while(1)
  235.                 {
  236.                     int key;
  237.                     printf("insert menu:\n");
  238.                     printf("0: exit\n");
  239.                     printf("key = ");
  240.                     scanf("%d", &key);
  241.                     if(key == 0)
  242.                         break;
  243.                     root = insert(root, key) ;
  244.                 }
  245.                 break;
  246.             }
  247.             case 3:
  248.             {
  249.                 while(1)
  250.                 {
  251.                     int key;
  252.                     printf("delete menu:\n");
  253.                     printf("0: exit\n");
  254.                     printf("key = ");
  255.                     scanf("%d", &key);
  256.                     if(key == 0)
  257.                         break;
  258.                     root = delete(root, key);
  259.                 }
  260.                 break;
  261.             }
  262.             case 4:
  263.             {
  264.                 printf("depth = %d\n", depth(root));
  265.                 break;
  266.             }
  267.             default:;
  268.         }
  269.     }

  271.     return 0;
  272. }

点击(此处)折叠或打开

  1. //bt_search.c

  3. //生成一个26个英文字母的二叉树，输入一个字母，若找到输出；否则输出没找到

  5. #include <stdio.h>
  6. #include <stdlib.h>
  7. #include <time.h>
  8. #include <assert.h>

  10. typedef struct btree
  11. {
  12.     char ch;
  13.     struct btree *l, *r;
  14. }btree_t;

  16. btree_t *make_node(char ch)
  17. {
  18.     btree_t *bt;

  20.     bt = malloc(sizeof(btree_t));
  21.     assert(bt);

  23.     bt->ch = ch;
  24.     bt->l = NULL;
  25.     bt->r = NULL;

  27.     return bt;
  28. }

  30. btree_t *insert(btree_t *root, char ch)
  31. {
  32.     if(! root)
  33.         return make_node(ch);
  34.     if(root->ch > ch)
  35.         root->l = insert(root->l, ch);
  36.     if(root->ch < ch)
  37.         root->r = insert(root->r, ch);
  38.     return root;
  39. }

  41. int counter(btree_t *root)
  42. {
  43.     int counter_l, counter_r;
  44.     if(root == NULL)
  45.         return 0;
  46.     counter_l = counter(root->l);
  47.     counter_r = counter(root->r);

  49.     return counter_l + counter_r + 1;

  51. }

  53. btree_t *create(btree_t *root)
  54. {

  56.     srand(time(NULL));
  57.     while(counter(root) < 26)
  58.     {
  59.         root = insert(root, rand() % 26 + 'A');
  60.     }

  62.     return root;
  63. }

  65. void in_order(btree_t *root)
  66. {
  67.     if(! root)
  68.         return ;
  69.     in_order(root->l);
  70.     printf("%c ", root->ch);
  71.     in_order(root->r);
  72. }

  74. btree_t *search(btree_t *root, char ch)
  75. {
  76.    if(! root)
  77.         return NULL;

  79.    if(root->ch > ch)
  80.         return root->l = search(root->l, ch);
  81.    if(root->ch < ch)
  82.        return root->r = search(root->r, ch);

  84.    return root;
  85. }

  87. int main(int argc, const char *argv[])
  88. {
  89.     btree_t *root = NULL;
  90.     char ch;

  92.     root = create(root);
  93.     in_order(root);
  94.     putchar('\n');

  96.     printf("search:");
  97.     scanf("%c", &ch);

  99.     btree_t *bt;
  100.     bt = search(root, ch);
  101.     if(bt)
  102.         printf("find:ch = %c\n", bt->ch);
  103.     else
  104.         printf("not find\n");
  105.     return 0;
  106. }

阅读(1444) | 评论(0) | 转发(3) |
0

上一篇：多文件的单词数统计 _0312

下一篇：快译通 _0317

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6