Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1405140
  • 博文数量: 241
  • 博客积分: 10
  • 博客等级: 民兵
  • 技术积分: 2253
  • 用 户 组: 普通用户
  • 注册时间: 2012-04-11 22:27
个人简介

--

文章分类

全部博文(241)

文章存档

2021年(3)

2019年(6)

2018年(1)

2017年(9)

2016年(21)

2015年(50)

2014年(125)

2013年(26)

我的朋友

分类: C/C++

2013-12-26 13:09:26

摘要:二叉树的创建、删除、深、遍历(前序、中序、后序)等。

代码:

点击(此处)折叠或打开

  1. #include "string.h"
  2. #include "stdio.h"
  3. #include "stdlib.h"
  4. #include "io.h"
  5. #include "math.h"
  6. #include "time.h"

  7. #define OK 1
  8. #define ERROR 0
  9. #define TRUE 1
  10. #define FALSE 0

  11. #define MAXSIZE 100 /* 存储空间初始分配量 */

  12. typedef int Status;        /* Status是函数的类型,其值是函数结果状态代码,如OK等 */

  13. /* 用于构造二叉树********************************** */
  14. int index=1;
  15. typedef char String[24]; /* 0号单元存放串的长度 */
  16. String str;

  17. Status StrAssign(String T,char *chars)
  18. {
  19.     int i;
  20.     if(strlen(chars)>MAXSIZE)
  21.         return ERROR;
  22.     else
  23.     {
  24.         T[0]=strlen(chars);
  25.         for(i=1;i<=T[0];i++)
  26.             T[i]=*(chars+i-1);
  27.         return OK;
  28.     }
  29. }
  30. /* ************************************************ */

  31. typedef char TElemType;
  32. TElemType Nil=' '; /* 字符型以空格符为空 */

  33. Status visit(TElemType e)
  34. {
  35.     printf("%c ",e);
  36.     return OK;
  37. }

  38. typedef struct BiTNode /* 结点结构 */
  39. {
  40.    TElemType data;        /* 结点数据 */
  41.    struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
  42. }BiTNode,*BiTree;


  43. /* 构造空二叉树T */
  44. Status InitBiTree(BiTree *T)
  45. {
  46.     *T=NULL;
  47.     return OK;
  48. }

  49. /* 初始条件: 二叉树T存在。操作结果: 销毁二叉树T */
  50. void DestroyBiTree(BiTree *T)
  51. {
  52.     if(*T)
  53.     {
  54.         if((*T)->lchild) /* 有左孩子 */
  55.             DestroyBiTree(&(*T)->lchild); /* 销毁左孩子子树 */
  56.         if((*T)->rchild) /* 有右孩子 */
  57.             DestroyBiTree(&(*T)->rchild); /* 销毁右孩子子树 */
  58.         free(*T); /* 释放根结点 */
  59.         *T=NULL; /* 空指针赋0 */
  60.     }
  61. }

  62. /* 按前序输入二叉树中结点的值(一个字符) */
  63. /* #表示空树,构造二叉链表表示二叉树T。 */
  64. void CreateBiTree(BiTree *T)
  65. {
  66.     TElemType ch;
  67.     
  68.     /* scanf("%c",&ch); */
  69.     ch=str[index++];

  70.     if(ch=='#')
  71.         *T=NULL;
  72.     else
  73.     {
  74.         *T=(BiTree)malloc(sizeof(BiTNode));
  75.         if(!*T)
  76.             exit(OVERFLOW);
  77.         (*T)->data=ch; /* 生成根结点 */
  78.         CreateBiTree(&(*T)->lchild); /* 构造左子树 */
  79.         CreateBiTree(&(*T)->rchild); /* 构造右子树 */
  80.     }
  81.  }

  82. /* 初始条件: 二叉树T存在 */
  83. /* 操作结果: 若T为空二叉树,则返回TRUE,否则FALSE */
  84. Status BiTreeEmpty(BiTree T)
  85. {
  86.     if(T)
  87.         return FALSE;
  88.     else
  89.         return TRUE;
  90. }

  91. #define ClearBiTree DestroyBiTree

  92. /* 初始条件: 二叉树T存在。操作结果: 返回T的深度 */
  93. int BiTreeDepth(BiTree T)
  94. {
  95.     int i,j;
  96.     if(!T)
  97.         return 0;
  98.     if(T->lchild)
  99.          i=BiTreeDepth(T->lchild);
  100.     else
  101.         i=0;
  102.     if(T->rchild)
  103.         j=BiTreeDepth(T->rchild);
  104.     else
  105.         j=0;
  106.     return i>j?i+1:j+1;
  107. }

  108. /* 初始条件: 二叉树T存在。操作结果: 返回T的根 */
  109. TElemType Root(BiTree T)
  110. {
  111.     if(BiTreeEmpty(T))
  112.         return Nil;
  113.     else
  114.         return T->data;
  115. }

  116. /* 初始条件: 二叉树T存在,p指向T中某个结点 */
  117. /* 操作结果: 返回p所指结点的值 */
  118. TElemType Value(BiTree p)
  119. {
  120.     return p->data;
  121. }

  122. /* 给p所指结点赋值为value */
  123. void Assign(BiTree p,TElemType value)
  124. {
  125.     p->data=value;
  126. }

  127. /* 初始条件: 二叉树T存在 */
  128. /* 操作结果: 前序递归遍历T */
  129. void PreOrderTraverse(BiTree T)
  130. {
  131.     if(T==NULL)
  132.         return;
  133.     printf("%c",T->data);/* 显示结点数据,可以更改为其它对结点操作 */
  134.     PreOrderTraverse(T->lchild); /* 再先序遍历左子树 */
  135.     PreOrderTraverse(T->rchild); /* 最后先序遍历右子树 */
  136. }

  137. /* 初始条件: 二叉树T存在 */
  138. /* 操作结果: 中序递归遍历T */
  139. void InOrderTraverse(BiTree T)
  140. {
  141.     if(T==NULL)
  142.         return;
  143.     InOrderTraverse(T->lchild); /* 中序遍历左子树 */
  144.     printf("%c",T->data);/* 显示结点数据,可以更改为其它对结点操作 */
  145.     InOrderTraverse(T->rchild); /* 最后中序遍历右子树 */
  146. }

  147. /* 初始条件: 二叉树T存在 */
  148. /* 操作结果: 后序递归遍历T */
  149. void PostOrderTraverse(BiTree T)
  150. {
  151.     if(T==NULL)
  152.         return;
  153.     PostOrderTraverse(T->lchild); /* 先后序遍历左子树 */
  154.     PostOrderTraverse(T->rchild); /* 再后序遍历右子树 */
  155.     printf("%c",T->data);/* 显示结点数据,可以更改为其它对结点操作 */
  156. }


  157. int main()
  158. {
  159.     int i;
  160.     BiTree T;
  161.     TElemType e1;
  162.     InitBiTree(&T);

  163.     
  164.     StrAssign(str,"ABDH#K###E##CFI###G#J##");

  165.     CreateBiTree(&T);

  166.     printf("构造空二叉树后,树空否?%d(1:是 0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
  167.     e1=Root(T);
  168.     printf("二叉树的根为: %c\n",e1);

  169.     printf("\n前序遍历二叉树:");
  170.     PreOrderTraverse(T);
  171.     printf("\n中序遍历二叉树:");
  172.     InOrderTraverse(T);
  173.     printf("\n后序遍历二叉树:");
  174.     PostOrderTraverse(T);
  175.     ClearBiTree(&T);
  176.     printf("\n清除二叉树后,树空否?%d(1:是 0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
  177.     i=Root(T);
  178.     if(!i)
  179.         printf("树空,无根\n");
  180.     
  181.     return 0;
  182. }

阅读(594) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~