Chinaunix首页 | 论坛 | 博客
  • 博客访问: 261714
  • 博文数量: 59
  • 博客积分: 442
  • 博客等级: 下士
  • 技术积分: 900
  • 用 户 组: 普通用户
  • 注册时间: 2010-03-27 14:53
文章分类

全部博文(59)

文章存档

2018年(1)

2017年(14)

2016年(31)

2015年(1)

2013年(3)

2012年(9)

我的朋友

分类: C/C++

2017-03-12 14:29:42

代码实现了二叉树的创建、查找、插入、删除、遍历。

以下着重说删除,分3种情况:
case 1:要删除的节点t即有左子树又有右子树,如图c的node 5
case 2:要删除的节点即没左子树又没右子树,如图a的node 13
case 3:要删除的节点有单支子树,或左或右,如图b的node 16或node 10,另外也要注册被删除节点是父亲的左还是右子树

点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>

  3. typedef struct BiTree {
  4.     int data;
  5.     struct BiTree* lchild;
  6.     struct BiTree* rchild;
  7. }BST;

  8. void visit_node(BST* t)
  9. {
  10.     if(t != NULL)
  11.         printf("%d\n", t->data);
  12. }

  13. /* 遍历整个树,中序遍历 */
  14. void traverse_tree(BST* t)
  15. {
  16.     if(t == NULL)
  17.         return;
  18.     traverse_tree(t->lchild);
  19.     visit_node(t);
  20.     traverse_tree(t->rchild);
  21. }
  22. #if 0
  23. /* 插入节点,递归方法 */
  24. BST* insert_node_recursion(BST** t, int v)
  25. {
  26.     if(*t == NULL) {
  27.         *t = (BST*)malloc(sizeof(BST));
  28.         (*t)->data = v;
  29.         (*t)->lchild = (*t)->rchild = NULL;
  30.         return *t;
  31.     }
  32.     
  33.     if (v < (*t)->data)
  34.         (*t)->lchild = insert_node_recursion(&((*t)->lchild), v);
  35.     else
  36.         (*t)->rchild = insert_node_recursion(&((*t)->rchild), v);
  37.     
  38.     return *t;
  39. }
  40. #else
  41. /* 插入节点,递归方法 */
  42. BST* insert_node_recursion(BST* t, int v)
  43. {
  44.     if(t == NULL) {
  45.         BST* n;
  46.         n = (BST*)malloc(sizeof(BST));
  47.         n->data = v;
  48.         n->lchild = n->rchild = NULL;
  49.         return n;
  50.     }
  51.     
  52.     if (v < t->data)
  53.         t->lchild = insert_node_recursion(t->lchild, v);
  54.     else if(v > t->data)
  55.         t->rchild = insert_node_recursion(t->rchild, v);

  56.     return t;
  57. }
  58. #endif

  59. /* 插入节点,普通方法 */
  60. BST* insert_node_normal(BST* t, int v)
  61. {
  62.     BST* pre = NULL;
  63.     BST* new = NULL;
  64.     BST* head = t;
  65.     int l, r;
  66.     
  67.     while(t && t->data != v) {
  68.         pre = t;
  69.         l = r = 0;
  70.         if(v < t->data) {
  71.             l = 1;
  72.             t = t->lchild;
  73.         } else {
  74.             r = 1;
  75.             t = t->rchild;
  76.         }
  77.     }
  78.     
  79.     new = (BST*)malloc(sizeof(BST));
  80.     new->data = v;
  81.     new->lchild = new->rchild = NULL;
  82.     
  83.     if (pre != NULL)
  84.         l ? (pre->lchild = new) : (pre->rchild = new);
  85.     
  86.     if(head == NULL)
  87.         return new;
  88.     else
  89.         return head;
  90. }

  91. /* 查找节点 */
  92. BST* search_node(BST* t, int v)
  93. {
  94.     int level = 0;
  95.     
  96.     while (t) {
  97.         level++;        
  98.         if(v == t->data) {
  99.             printf("found it, deep level is %d\n", level);
  100.             break;
  101.         } else if(v < t->data)
  102.             t = t->lchild;
  103.         else
  104.             t = t->rchild;
  105.     }
  106.     
  107.     if(!t) {
  108.         printf("node %d is not exist.\n", v);
  109.         return NULL;
  110.     } else
  111.         return t;
  112. }

  113. /* 删除节点 */
  114. void delete_node(BST* t, int v)
  115. {
  116.     BST* pre = NULL;
  117.     BST* find = NULL;
  118.     BST* parent = NULL;
  119.     BST* most_left = NULL;
  120.     int l, r;
  121.     
  122.     while (t) {
  123.         if(v == t->data) {    //找到要删除的这个节点了
  124.             find = t;
  125.             if(t->lchild && t->rchild) {    //case 1:要删除的节点t即有左子树又有右子树,删除过程总3步

  126.                 //找到t的右子树里的最左节点 @1步
  127.                 t = t->rchild;
  128.                 while (t->lchild) {            
  129.                     parent = t;                //记录最左结点的父亲
  130.                     t = t->lchild;
  131.                 }
  132.                 most_left = t;
  133.                 
  134.                 //最左节点代替被删除节点t的位置 @2步
  135.                 find->data = most_left->data;
  136.                 
  137.                 //上面有人被删除带走,最左节点升职上去了,所以要重新调整下最左节点的上下关系,并删除其占用的空间 @3步
  138.                 if (most_left->rchild)
  139.                     parent->lchild = most_left->rchild;
  140.                 else
  141.                     parent->lchild = NULL;
  142.                 free(most_left);
  143.                 most_left = NULL;
  144.                 
  145.                 break;
  146.             }
  147.             else if(!t->lchild && !t->rchild)    //case 2:要删除的节点即没左子树又没右子树
  148.                 //l为真表示要删除的节点是父亲的左孩子,所以把左子树指针置空,否则置空右子树指针
  149.                 l ? (pre->lchild = NULL) : (pre->rchild = NULL);
  150.                 
  151.             else if(t->lchild)                    //case 3:要删除的节点有左子树
  152.                 //要删除的结点为t,t的父亲是pre,t有个左儿子是t->lchild
  153.                 //t被带走了,所以把t的孩子过继给t的父亲pre,也就是爷爷来带孙子
  154.                 //那么爷爷是左胳膊牵着孙子走还是右胳膊呢,那得看t是pre的左孩子还是右孩子
  155.                 //l为真表示要删除的节点t是父亲pre的左孩子,所以把t的孩子过继给父亲pre的左子树,否则就过继给右子树
  156.                 l ? (pre->lchild = t->lchild) : (pre->rchild = t->lchild);
  157.                 
  158.             else if(t->rchild)                    //case 4:要删除的节点有右子树
  159.                 //同case 3一样,都是过继孙子给爷爷的故事,只不过这个是右孩子,case 3是左孩子
  160.                 r ? (pre->rchild = t->rchild) : (pre->lchild = t->rchild);
  161.             
  162.             free(find);
  163.             find = NULL;
  164.             break;
  165.         } else if(v < t->data) {
  166.             pre = t;    //pre代表当前节点的父亲
  167.             l = 1;        //l变量为真表示当前节点是父亲节点的左子树
  168.             r = 0;
  169.             t = t->lchild;
  170.         } else {
  171.             pre = t;
  172.             r = 1;        //r变量为真表示当前节点是父亲节点的右子树
  173.             l = 0;
  174.             t = t->rchild;
  175.         }
  176.     }
  177. }

  178. /* 创建二叉查找树 */
  179. void create_bitree(BST** t, int *d, int len)
  180. {
  181.     int i;
  182.     
  183.     for(i = 0; i < len; i++)
  184. //        *t = insert_node_recursion(*t, d[i]);
  185.         *t = insert_node_normal(*t, d[i]);
  186. }

  187. void main(void)
  188. {
  189.     //T是整个树的根
  190.     BST* T = NULL;
  191.     int n = 0;
  192. //    int d[] = {4, 13, 3, 9, 28, 6};
  193.     int d[] = {4, 13, 3, 9};
  194.     
  195.     while(d[n++] != 0);

  196.     create_bitree(&T, d, n - 1);
  197. //    insert_node_recursion(T, 15);
  198.     insert_node_normal(T, 15);
  199.     traverse_tree(T);
  200.     printf("\n\n");
  201. //    search_node(T, 9);
  202.     delete_node(T, 4);
  203.     traverse_tree(T);
  204. }

阅读(797) | 评论(0) | 转发(0) |
0

上一篇:内存

下一篇:wakelock实现

给主人留下些什么吧!~~