现在的位置: 首页 > 综合 > 正文

二叉树的常用操作

2013年12月13日 ⁄ 综合 ⁄ 共 8513字 ⁄ 字号 小 中 大 ⁄ 评论关闭

      二叉树是每个节点至多有两颗子树的有序树。有以下特点：
      1、在二叉树的第i层至多有2^(i-1)个结点(i>=1)；
      2、深度为k的二叉树至多有2^k-1个结点；
      3、对任何一个二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2 + 1；
      分类
      满二叉树：一颗深度为k且有2^k-1个节点的二叉树称为满二叉树
      完全二叉树：深度为k的，有n个节点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树。特点：
          1、具有n个节点的完全二叉树的深度为log2n + 1
          2、如果对一颗有n个结点的完全二叉树(深度为log2n + 1)的结点按层序编号(从第1层到第og2n + 1层，每层从左到右)，则对任一结点i(1=<i<=n)，有：
              a、如果i = 1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲PARENT(i)是结点i/2。
              b、如果2i > n，则结点i无左孩子(结点i为叶子结点)；否则其左孩子LCHILD(i)是结点2i。
              c、若果2i + 1 > n，则结点i无右孩子；否则其右孩子RCHILD(i)是结点2i + 1。
      顺序存储结构在二叉树不是完全二叉树的情况下很浪费空间。所以，这里采用链式存储结构
接口：

Code:
  1. #ifndef _BITREE_H   
  2. #define _BITREE_H   
  3. #define TElemType char   
  4. #define Nil ' '   
  5. #define clear_bitree destory_bitree   
  6.   
  7. #ifdef _MSC_VER   
  8. #define bool int    
  9. #define true 1    
  10. #define false 0     
  11. #else   
  12. #include <stdbool.h>   
  13. #include <stdint.h>   
  14. #endif   
  15.   
  16. struct BiTNode;   
  17.   
  18. void init_bitree(struct BiTNode **T);   
  19. bool create_bitree(struct BiTNode **T);   
  20. void destory_bitree(struct BiTNode **T);   
  21.   
  22. bool bitree_empty(struct BiTNode *T);   
  23. int bitree_depth(struct BiTNode *T);   
  24.   
  25. TElemType root(struct BiTNode *T);   
  26. struct BiTNode *point(struct BiTNode *T, TElemType e);   
  27.   
  28. TElemType parent(struct BiTNode *T, TElemType e);   
  29. TElemType left_child(struct BiTNode *T, TElemType e);   
  30. TElemType right_child(struct BiTNode *T, TElemType e);   
  31.   
  32. TElemType left_sibling(struct BiTNode *T, TElemType e);   
  33. TElemType right_sibling(struct BiTNode *T, TElemType e);   
  34.   
  35. bool insert_child(struct BiTNode *p, int LR, struct BiTNode *c);   
  36. bool delete_child(struct BiTNode *p, int LR);   
  37.   
  38. TElemType value(struct BiTNode *p);   
  39. void assign(struct BiTNode *p, TElemType e);   
  40.   
  41. void pre_order(struct BiTNode *T, void (*visit)(TElemType e));   
  42. void in_order(struct BiTNode *T, void (*visit)(TElemType e));   
  43. void post_order(struct BiTNode *T, void (*visit)(TElemType e));   
  44.   
  45. #endif   

实现：

Code:
  1. #include "queue.h"   
  2. #include "bitree.h"   
  3. #include <stdio.h>   
  4. #include <stdlib.h>   
  5. #include <assert.h>   
  6.   
  7. struct BiTNode {   
  8.     TElemType data;   
  9.     struct BiTNode *lchild, *rchild;   
  10. };   
  11.   
  12. /* init the binary tree with NULL */  
  13. void init_bitree(struct BiTNode **T)   
  14. {   
  15.     *T = NULL;   
  16. }   
  17.   
  18. /* create binary tree by previous order input */  
  19. bool create_bitree(struct BiTNode **T)   
  20. {   
  21.     TElemType ch;   
  22.     scanf("%c", &ch);   
  23.     if (ch == Nil)   
  24.         *T = NULL;   
  25.     else {   
  26.         *T = (struct BiTNode *)malloc(sizeof(struct BiTNode));   
  27.         if (*T == NULL)   
  28.             return false;   
  29.         (*T)->data = ch;   
  30.         create_bitree(&(*T)->lchild);   
  31.         create_bitree(&(*T)->rchild);   
  32.     }   
  33.     return true;   
  34. }   
  35.   
  36.   
  37. void destory_bitree(struct BiTNode **T)   
  38. {   
  39.     if (*T != NULL) {   
  40.         if ((*T)->lchild != NULL)   
  41.             destory_bitree(&(*T)->lchild);   
  42.         if ((*T)->rchild != NULL)   
  43.             destory_bitree(&(*T)->rchild);   
  44.         free(*T);   
  45.         *T = NULL;   
  46.     }   
  47. }   
  48.   
  49. bool bitree_empty(struct BiTNode *T)   
  50. {   
  51.     if (T != NULL)   
  52.         return false;   
  53.     else  
  54.         return true;   
  55. }   
  56.   
  57. int bitree_depth(struct BiTNode *T)   
  58. {   
  59.     int i, j;   
  60.     if (T == NULL)   
  61.         return 0;   
  62.            
  63.     if (T->lchild != NULL)   
  64.         i = bitree_depth(T->lchild);   
  65.     else  
  66.         i = 0;   
  67.   
  68.     if (T->rchild != NULL)   
  69.         j = bitree_depth(T->rchild);   
  70.     else  
  71.         j = 0;   
  72.            
  73.     return i > j ? i+1 : j+1;   
  74. }   
  75.   
  76. TElemType root(struct BiTNode *T)   
  77. {   
  78.     if (bitree_empty(T))   
  79.         return Nil;   
  80.     else  
  81.         return T->data;   
  82. }   
  83.   
  84. /* return the pointer of node whose data is e */  
  85. struct BiTNode * point(struct BiTNode *T, TElemType e)   
  86. {   
  87.     QElemType a;   
  88.     struct queue *q = NULL;   
  89.       
  90.     if (T != NULL) {   
  91.         q = init_queue();   
  92.         en_queue(q, T);   
  93.            
  94.         while (! queue_empty(q)) {   
  95.             a = gethead(q);   
  96.             de_queue(q);   
  97.                
  98.             if (a->data == e) {   
  99.                 destory_queue(q);   
  100.                 return a;   
  101.             }   
  102.             if (a->lchild != NULL)   
  103.                 en_queue(q, a->lchild);   
  104.             if (a->rchild != NULL)   
  105.                 en_queue(q, a->rchild);   
  106.         }   
  107.     }   
  108.     return NULL;   
  109. }   
  110.   
  111. /* return the data of parent of node whose data is e */  
  112. TElemType parent(struct BiTNode *T, TElemType e)   
  113. {   
  114.     struct queue *q = NULL;   
  115.     if (T != NULL) {   
  116.         q = init_queue();   
  117.         en_queue(q, T);   
  118.         while (! queue_empty(q)) {   
  119.             QElemType a = gethead(q);   
  120.             de_queue(q);   
  121.                
  122.             /* find the node whose data is e */  
  123.             if ((a->lchild != NULL && a->lchild->data == e) ||    
  124.                 (a->rchild != NULL && a->rchild->data == e)) {   
  125.                 destory_queue(q);   
  126.                 return a->data;   
  127.             } else {   
  128.                 if (a->lchild != NULL)   
  129.                     en_queue(q, a->lchild);   
  130.                 if (a->rchild != NULL)   
  131.                     en_queue(q, a->rchild);   
  132.             }   
  133.         }   
  134.     }   
  135.     return Nil;   
  136. }   
  137.   
  138. /* return the data of left child of node whose data is e */  
  139. TElemType  left_child(struct BiTNode *T, TElemType e)   
  140. {   
  141.     struct BiTNode *a;   
  142.     if (T != NULL) {   
  143.         a = point(T, e);   
  144.         if (a != NULL && a->lchild != NULL)   
  145.             return a->lchild->data;   
  146.     }   
  147.     return Nil;   
  148. }   
  149.   
  150. /* return the data of right child of node whose data is e */  
  151. TElemType right_child(struct BiTNode *T, TElemType e)   
  152. {   
  153.     struct BiTNode *a;   
  154.     if (T != NULL) {   
  155.         a = point(T, e);   
  156.         if (a != NULL && a->rchild != NULL)   
  157.             return a->rchild->data;   
  158.     }   
  159.     return Nil;   
  160. }   
  161.   
  162. /* assume the node whose data is e names A, then return the data of left   
  163.  * brother of A, if A is the left child of T, or A hasn't left brother,  
  164.  * return Nil  
  165.  */  
  166. TElemType left_sibling(struct BiTNode *T, TElemType e)   
  167. {   
  168.     TElemType a;   
  169.     struct BiTNode *p;   
  170.        
  171.     if (T != NULL) {   
  172.         a = parent(T, e);   
  173.         if (a != Nil) {   
  174.             p = point (T, a);   
  175.             if (p->lchild != NULL && p->rchild != NULL && p->rchild->data == e)   
  176.                 return p->lchild->data;   
  177.         }   
  178.     }   
  179.     return Nil;   
  180. }   
  181.   
  182. TElemType right_sibling(struct BiTNode *T, TElemType e)   
  183. {   
  184.     TElemType a;   
  185.     struct BiTNode *p;   
  186.        
  187.     if (T != NULL) {   
  188.         a = parent(T, e);   
  189.         if (a != Nil) {   
  190.             p = point(T, a);   
  191.             if (p->rchild != NULL && p->lchild != NULL && p->lchild->data == e)   
  192.                 return p->rchild->data;   
  193.         }   
  194.     }   
  195.     return Nil;   
  196. }   
  197.   
  198. /* according to the value of LR, insert c into the left or right child of p.  
  199.  * the former left or right tree be the right tree of c.  
  200.  */  
  201. bool insert_child(struct BiTNode *p, int LR, struct BiTNode *c)   
  202. {   
  203.     if (p != NULL) {   
  204.         if (LR == 0) {   
  205.             c->rchild = p->lchild;   
  206.             p->lchild = c;   
  207.         } else {   
  208.             c->rchild = p->rchild;   
  209.             p->rchild = c;   
  210.         }   
  211.         return true;   
  212.     }   
  213.     return false;   
  214. }   
  215. /* delete the left or right child tree of p, by the value of LR */  
  216. bool delete_child(struct BiTNode *p, int LR)   
  217. {   
  218.     if (p != NULL) {   
  219.         if (LR == 0)   
  220.             clear_bitree(&p->lchild);   
  221.         else  
  222.             clear_bitree(&p->rchild);   
  223.         return true;   
  224.     }   
  225.     return false;   
  226. }   
  227.   
  228. TElemType value(struct BiTNode *p)   
  229. {   
  230.     assert(p != NULL);   
  231.     return p->data;   
  232. }   
  233.   
  234. void assign(struct BiTNode *p, TElemType e)   
  235. {   
  236.     assert(p != NULL);   
  237.     p->data = e;   
  238. }   
  239.   
  240. void pre_order(struct BiTNode *T, void (*visit)(TElemType e))   
  241. {   
  242.     if (T != NULL) {   
  243.         visit(T->data);   
  244.         pre_order(T->lchild, visit);   
  245.         pre_order(T->rchild, visit);   
  246.     }   
  247. }   
  248.   
  249. void in_order(struct BiTNode *T, void (*visit)(TElemType e))   
  250. {   
  251.     if (T != NULL) {   
  252.         in_order(T->lchild, visit);   
  253.         visit(T->data);   
  254.         in_order(T->rchild, visit);   
  255.     }   
  256. }   
  257.   
  258. void post_order(struct BiTNode *T, void (*visit)(TElemType e))   
  259. {   
  260.     if (T != NULL) {   
  261.         post_order(T->lchild, visit);   
  262.         post_order(T->rchild, visit);   
  263.         visit(T->data);   
  264.     }   
  265. }   
  266.   

 接口看起来不太美观，个人不喜欢匈牙利命名法，更喜欢unix风格的命名，但采用下划线的方式有时又导致名称太长！矛盾中...后面给出非递归遍历的实现。测试代码：

Code:
  1. #include "bitree.h"   
  2. #include <stdio.h>   
  3.   
  4. void print(TElemType e)   
  5. {   
  6.     printf("%c", e);   
  7. }   
  8.   
  9. int main()   
  10. {   
  11.     struct BTNode *p = NULL;   
  12.        
  13.     create_bitree(&p);   
  14.     pre_order(p, print);   
  15.        
  16.     printf("/n");   
  17.     in_order(p, print);   
  18.        
  19.     printf("/n");   
  20.     post_order(p, print);   
  21.        
  22.     printf("/n");   
  23.     char ch = parent(p, 'E');   
  24.     printf("%c", ch);   
  25.     destory_bitree(&p);   
  26.     return 0;   
  27. }   

 

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞