树的抽象数据类型表示ADT

  1. ADT Tree{
  2.     数据对象D：D是具有相同特性的元素的集合
  3.     数据关系R：若D为空集，则称为空树；若D仅含有一个数据元素，则R为空集，否则R={H}，H是如下二元关系
  5.         (1).在D中存在唯一称为根的数据元素root，它在关系H下无前驱；
  6.         (2).若D-{root}!=φ，则存在D-{root}的一个划分D_1,D_2,...,D_m(m>0),对任意j!=k
  7.         (1<=k<=j,k<=m)有D_j并D_k=φ，且对任意的i(1<=i<=m)，唯一存在数据元素x_i属于D_i,有<root,x_i>属于H；
  8.         (3).对应于D-{root}的划分，H-{<root,x_i>,...,<root,x_m>}有唯一的一个划分H_1,H_2,...,H_m(m>0)
  9.         对任意j!=k(1<=j,k<=m)有H_j并H_k=φ，且对任意i(1<=i<=m)，H_i是D_i上的二元关系，(D_i,{H_i})是一颗符合本定义的树，称为根root的子树。
  11.         基本操作：
  12.         InitTree(&T)
  13.             操作结果：构造空树T
  14.         DestroyTree(&T)
  15.             初始条件：树T存在
  16.             操作结果：销毁树T
  17.         CreateTree(&T,definition)
  18.             初始条件：definition给出树的定义
  19.             操作结果：按definition构造树T
  20.         TreeEmpty(T)
  21.             初始条件：树T存在
  22.             操作结果：若T为空树，则返回TURE，否则返回FALSRE
  23.         TreeDepth(T)
  24.             初始条件：树T存在
  25.             操作结果：返回T的深度
  26.         Root(T)
  27.             初始条件：树T存在
  28.             操作结果：返回T的根
  29.         Value(T,cur_e)
  30.             初始条件：树T存在,cur_e是T的某个结点
  31.             操作结果：返回cur_e的值
  32.         Assign(T,cur_e,value)
  33.             初始条件：树T存在,cur_e是T的某个结点
  34.             操作结果：结点cur_e赋值尾value
  35.         Parent(T,cur_e)
  36.             初始条件：树T存在,cur_e是T的某个结点
  37.             操作结果：若cur_e是T的非根结点，则返回他的双亲，否则函数值为"空"
  38.         LeftChild(T,cur_e)
  39.             初始条件：树T存在,cur_e是T的某个结点
  40.             操作结果：若cur_e是T的非叶子结点，则返回他的最左孩子，否则函数值为"空"
  41.         RightSibling(T,cur_e)
  42.             初始条件：树T存在,cur_e是T的某个结点
  43.             操作结果：若cur_e有右兄弟，则返回他的右兄弟，否则函数值为"空"
  44.         InsertChild(&T,&p,i,c)
  45.             初始条件：树T存在,p指向T中的某个结点，1<=i<=p所指的结点的度+1，非空树c与T不相交
  46.             操作结果：插入c为T中p所指结点的第i棵子树
  47.         DeleteChild(&T,&p,i)
  48.             初始条件：树T存在,p指向T中的某个结点，1<=i<=p所指的结点的度
  49.             操作结果：删除T中p所指结点的第i棵子树
  50.         TraverseTree(T,Visit())
  51.             初始条件：树T存在，Visit函数是对结点操作的应用函数
  52.             操作结果：按某种次序对T的每个结点调用函数Visit()一次且至多一次，一旦Visit()失败，则操作失败。
  53. }ADT Tree

二叉树的抽象数据类型表示ADT

  1. ADT BinaryTree{
  2.     数据对象D：D是具有相同特性的元素的集合
  3.     数据关系R：
  4.         若D=φ,则R=φ，BinaryTree称为空树；
  5.         若D!=φ,则R={H}，H是如下二元关系
  6.         (1).在D中存在唯一称为根的数据元素root，它在关系H下无前驱；
  7.         (2).若D-{root}!=φ，则存在D-{root}={D_1,D_r}(m>0),且D_1并D_r=φ
  8.         (3).若D_1!=φ,则D_1中存在唯一的元素x_1，<root,x_1>属于H，且在D_1上的关系H_1包含于H；若
  9.         D_r!=φ,则D_r中存在唯一的元素x_r，<root,x_r>属于H，且在D_r上的关系H_r包含于H；H={<root,x_1>,<root,x_r>,H_1,H_r}
  10.         (4).(D_1,{H_1})是一棵符合本定义的二叉树，称为根的左子树，(D_r,{H_r})是一棵符合本定义的二叉树，称为根的右子树。
  12.         基本操作：
  13.         InitBiTree(&T)
  14.             操作结果：构造空二叉树T
  15.         DestroyBiTree(&T)
  16.             初始条件：二叉树T存在
  17.             操作结果：销毁二叉树T
  18.         CreateBiTree(&T,definition)
  19.             初始条件：definition给出二叉树的定义
  20.             操作结果：按definition构造二叉树T
  21.         ClerarBiTree(&T)
  22.             初始条件：二叉树T存在
  23.             操作结果：将二叉树T清为空树
  24.         BiTreeEmpty(T)
  25.             初始条件：二叉树T存在
  26.             操作结果：若T为空二叉树，则返回TURE，否则返回FALSRE
  27.         BiTreeDepth(T)
  28.             初始条件：二叉树T存在
  29.             操作结果：返回二叉树T的深度
  30.         Root(T)
  31.             初始条件：二叉树T存在
  32.             操作结果：返回二叉树T的根
  33.         Value(T,e)
  34.             初始条件：树T存在,e是T的某个结点
  35.             操作结果：返回e的值
  36.         Assign(T,e,value)
  37.             初始条件：二叉树T存在,e是T的某个结点
  38.             操作结果：结点e赋值尾value
  39.         Parent(T,e)
  40.             初始条件：二叉树T存在,e是T的某个结点
  41.             操作结果：若e是T的非根结点，则返回他的双亲，否则函数值为"空"
  42.         LeftChild(T,e)
  43.             初始条件：二叉树T存在,e是T的某个结点
  44.             操作结果：若e是T的非叶子结点，则返回他的最左孩子，否则函数值为"空"
  45.         RightChild(T,e)
  46.             初始条件：二叉树T存在,e是T的某个结点
  47.             操作结果：若e是T的非叶子结点，则返回他的最右孩子，否则函数值为"空"
  48.         LeftSibling(T,e)
  49.             初始条件：二叉树T存在,e是T的某个结点
  50.             操作结果：若e有右兄弟，则返回他的右兄弟，否则函数值为"空"
  51.         RightSibling(T,e)
  52.             初始条件：二叉树T存在,e是T的某个结点
  53.             操作结果：若e有右兄弟，则返回他的右兄弟，否则函数值为"空"
  54.         InsertChild(T,p,LLR,c)
  55.             初始条件：二叉树T存在,p指向T中的某个结点，LR为0或1，非空二叉树c与T不相交且右子树为空
  56.             操作结果：根据LR为0或1，插入c为T中p所指结点的左或右子树
  57.         DeleteChild(T,p,LR)
  58.             初始条件：二叉树T存在,p指向T中的某个结点，LR为0或1
  59.             操作结果：根据LR为0或1，删除T中p所指结点的左或右子树
  60.         PreTraverse(T,Visit())
  61.             初始条件：二叉树T存在，Visit函数是对结点操作的应用函数
  62.             操作结果：先序遍历T，对T的每个结点调用函数Visit()一次且至多一次，一旦Visit()失败，则操作失败。
  63.         InTraverse(T,Visit())
  64.             初始条件：二叉树T存在，Visit函数是对结点操作的应用函数
  65.             操作结果：中序遍历T，对T的每个结点调用函数Visit()一次且至多一次，一旦Visit()失败，则操作失败。
  66.         PostTraverse(T,Visit())
  67.             初始条件：二叉树T存在，Visit函数是对结点操作的应用函数
  68.             操作结果：后序遍历T，对T的每个结点调用函数Visit()一次且至多一次，一旦Visit()失败，则操作失败。
  69.         LevelTraverse(T,Visit())
  70.             初始条件：二叉树T存在，Visit函数是对结点操作的应用函数
  71.             操作结果：层序遍历T，对T的每个结点调用函数Visit()一次且至多一次，一旦Visit()失败，则操作失败。
  72. }ADT BinaryTree

二叉树顺序结构实现

  1. #include "stdio.h"    
  2. #include "stdlib.h"   
  4. #include "math.h"  
  5. #include "time.h"
  6. /**
  7. * @brief 
  8. * 二叉树顺序结构实现.c
  9. */
  10. #define OK 1
  11. #define ERROR 0
  12. #define TRUE 1
  13. #define FALSE 0
  15. #define MAXSIZE 100 /* 存储空间初始分配量 */
  16. #define MAX_TREE_SIZE 100 /* 二叉树的最大结点数 */
  18. typedef int Status;        /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
  19. typedef int TElemType;  /* 树结点的数据类型，目前暂定为整型 */
  20. typedef TElemType SqBiTree[MAX_TREE_SIZE]; /* 0号单元存储根结点  */
  22. typedef struct
  23. {
  24.     int level,order; /* 结点的层,本层序号(按满二叉树计算) */
  25. }Position;
  27. TElemType Nil=0; /*  设整型以0为空 */
  29. Status visit(TElemType c)
  30. {
  31.     printf("%d ",c);
  32.     return OK;
  33. }
  35. /* 构造空二叉树T。因为T是固定数组，不会改变，故不需要& */
  36. Status InitBiTree(SqBiTree T)
  37. {
  38.     int i;
  39.     for(i=0;i<MAX_TREE_SIZE;i++)
  40.         T[i]=Nil; /* 初值为空 */
  41.     return OK;
  42. }
  44. /* 按层序次序输入二叉树中结点的值(字符型或整型), 构造顺序存储的二叉树T */
  45. Status CreateBiTree(SqBiTree T)
  46. { 
  47.     int i=0;
  48.     printf("请按层序输入结点的值(整型)，0表示空结点，输999结束。结点数≤%d:\n",MAX_TREE_SIZE);
  49.     while(i<10)
  50.     {
  51.         T[i]=i+1;
  53.         if(i!=0&&T[(i+1)/2-1]==Nil&&T[i]!=Nil) /* 此结点(不空)无双亲且不是根 */
  54.         {
  55.             printf("出现无双亲的非根结点%d\n",T[i]);
  56.             exit(ERROR);
  57.         }
  58.         i++;
  59.     }
  60.     while(i<MAX_TREE_SIZE)
  61.     {
  62.         T[i]=Nil; /* 将空赋值给T的后面的结点 */
  63.         i++;
  64.     }
  66.     return OK;
  67. }
  69. #define ClearBiTree InitBiTree /* 在顺序存储结构中，两函数完全一样 */
  71. /* 初始条件: 二叉树T存在 */
  72. /* 操作结果: 若T为空二叉树,则返回TRUE,否则FALSE */
  73. Status BiTreeEmpty(SqBiTree T)
  74. { 
  75.     if(T[0]==Nil) /* 根结点为空,则树空 */
  76.         return TRUE;
  77.     else
  78.         return FALSE;
  79. }
  81. /* 初始条件: 二叉树T存在。操作结果: 返回T的深度 */
  82. int BiTreeDepth(SqBiTree T)
  83. { 
  84.     int i,j=-1;
  85.     for(i=MAX_TREE_SIZE-1;i>=0;i--) /* 找到最后一个结点 */
  86.         if(T[i]!=Nil)
  87.             break;
  88.     i++; 
  89.     do
  90.         j++;
  91.     while(i>=powl(2,j));/* 计算2的j次幂。 */
  92.     return j;
  93. }
  95. /* 初始条件: 二叉树T存在 */
  96. /* 操作结果:  当T不空,用e返回T的根,返回OK;否则返回ERROR,e无定义 */
  97. Status Root(SqBiTree T,TElemType *e)
  98. { 
  99.     if(BiTreeEmpty(T)) /* T空 */
  100.         return ERROR;
  101.     else
  102.     {    
  103.         *e=T[0];
  104.         return OK;
  105.     }
  106. }
  108. /* 初始条件: 二叉树T存在,e是T中某个结点(的位置) */
  109. /* 操作结果: 返回处于位置e(层,本层序号)的结点的值 */
  110. TElemType Value(SqBiTree T,Position e)
  111. { 
  112.     return T[(int)powl(2,e.level-1)+e.order-2];
  113. }
  115. /* 初始条件: 二叉树T存在,e是T中某个结点(的位置) */
  116. /* 操作结果: 给处于位置e(层,本层序号)的结点赋新值value */
  117. Status Assign(SqBiTree T,Position e,TElemType value)
  118. { 
  119.     int i=(int)powl(2,e.level-1)+e.order-2; /* 将层、本层序号转为矩阵的序号 */
  120.     if(value!=Nil&&T[(i+1)/2-1]==Nil) /* 给叶子赋非空值但双亲为空 */
  121.         return ERROR;
  122.     else if(value==Nil&&(T[i*2+1]!=Nil||T[i*2+2]!=Nil)) /*  给双亲赋空值但有叶子（不空） */
  123.         return ERROR;
  124.     T[i]=value;
  125.     return OK;
  126. }
  128. /* 初始条件: 二叉树T存在,e是T中某个结点 */
  129. /* 操作结果: 若e是T的非根结点,则返回它的双亲,否则返回＂空＂ */
  130. TElemType Parent(SqBiTree T,TElemType e)
  131. { 
  132.     int i;
  133.     if(T[0]==Nil) /* 空树 */
  134.         return Nil;
  135.     for(i=1;i<=MAX_TREE_SIZE-1;i++)
  136.         if(T[i]==e) /* 找到e */
  137.             return T[(i+1)/2-1];
  138.     return Nil; /* 没找到e */
  139. }
  142. /* 初始条件: 二叉树T存在,e是T中某个结点 */
  143. /* 操作结果: 返回e的左孩子。若e无左孩子,则返回＂空＂ */
  144. TElemType LeftChild(SqBiTree T,TElemType e)
  145. { 
  146.     int i;
  147.     if(T[0]==Nil) /* 空树 */
  148.         return Nil;
  149.     for(i=0;i<=MAX_TREE_SIZE-1;i++)
  150.         if(T[i]==e) /* 找到e */
  151.             return T[i*2+1];
  152.     return Nil; /* 没找到e */
  153. }
  155. /* 初始条件: 二叉树T存在,e是T中某个结点 */
  156. /* 操作结果: 返回e的右孩子。若e无右孩子,则返回＂空＂ */
  157. TElemType RightChild(SqBiTree T,TElemType e)
  158. { 
  159.     int i;
  160.     if(T[0]==Nil) /* 空树 */
  161.         return Nil;
  162.     for(i=0;i<=MAX_TREE_SIZE-1;i++)
  163.         if(T[i]==e) /* 找到e */
  164.             return T[i*2+2];
  165.     return Nil; /* 没找到e */
  166. }
  168. /* 初始条件: 二叉树T存在,e是T中某个结点 */
  169. /* 操作结果: 返回e的左兄弟。若e是T的左孩子或无左兄弟,则返回＂空＂ */
  170. TElemType LeftSibling(SqBiTree T,TElemType e)
  171. { 
  172.     int i;
  173.     if(T[0]==Nil) /* 空树 */
  174.         return Nil;
  175.     for(i=1;i<=MAX_TREE_SIZE-1;i++)
  176.         if(T[i]==e&&i%2==0) /* 找到e且其序号为偶数(是右孩子) */
  177.             return T[i-1];
  178.     return Nil; /* 没找到e */
  179. }
  181. /* 初始条件: 二叉树T存在,e是T中某个结点 */
  182. /* 操作结果: 返回e的右兄弟。若e是T的右孩子或无右兄弟,则返回＂空＂ */
  183. TElemType RightSibling(SqBiTree T,TElemType e)
  184. { 
  185.     int i;
  186.     if(T[0]==Nil) /* 空树 */
  187.         return Nil;
  188.     for(i=1;i<=MAX_TREE_SIZE-1;i++)
  189.         if(T[i]==e&&i%2) /* 找到e且其序号为奇数(是左孩子) */
  190.             return T[i+1];
  191.     return Nil; /* 没找到e */
  192. }
  194. /* PreOrderTraverse()调用 */
  195. void PreTraverse(SqBiTree T,int e)
  196. { 
  197.     visit(T[e]);
  198.     if(T[2*e+1]!=Nil) /* 左子树不空 */
  199.         PreTraverse(T,2*e+1);
  200.     if(T[2*e+2]!=Nil) /* 右子树不空 */
  201.         PreTraverse(T,2*e+2);
  202. }
  204. /* 初始条件: 二叉树存在 */
  205. /* 操作结果: 先序遍历T。 */
  206. Status PreOrderTraverse(SqBiTree T)
  207. { 
  208.     if(!BiTreeEmpty(T)) /* 树不空 */
  209.         PreTraverse(T,0);
  210.     printf("\n");
  211.     return OK;
  212. }
  214. /* InOrderTraverse()调用 */
  215. void InTraverse(SqBiTree T,int e)
  216. { 
  217.     if(T[2*e+1]!=Nil) /* 左子树不空 */
  218.         InTraverse(T,2*e+1);
  219.     visit(T[e]);
  220.     if(T[2*e+2]!=Nil) /* 右子树不空 */
  221.         InTraverse(T,2*e+2);
  222. }
  224. /* 初始条件: 二叉树存在 */
  225. /* 操作结果: 中序遍历T。 */
  226. Status InOrderTraverse(SqBiTree T)
  227. { 
  228.     if(!BiTreeEmpty(T)) /* 树不空 */
  229.         InTraverse(T,0);
  230.     printf("\n");
  231.     return OK;
  232. }
  234. /* PostOrderTraverse()调用 */
  235. void PostTraverse(SqBiTree T,int e)
  236. { 
  237.     if(T[2*e+1]!=Nil) /* 左子树不空 */
  238.         PostTraverse(T,2*e+1);
  239.     if(T[2*e+2]!=Nil) /* 右子树不空 */
  240.         PostTraverse(T,2*e+2);
  241.     visit(T[e]);
  242. }
  244. /* 初始条件: 二叉树T存在 */
  245. /* 操作结果: 后序遍历T。 */
  246. Status PostOrderTraverse(SqBiTree T)
  247. { 
  248.     if(!BiTreeEmpty(T)) /* 树不空 */
  249.         PostTraverse(T,0);
  250.     printf("\n");
  251.     return OK;
  252. }
  254. /* 层序遍历二叉树 */
  255. void LevelOrderTraverse(SqBiTree T)
  256. { 
  257.     int i=MAX_TREE_SIZE-1,j;
  258.     while(T[i]==Nil)
  259.         i--; /* 找到最后一个非空结点的序号 */
  260.     for(j=0;j<=i;j++)  /* 从根结点起,按层序遍历二叉树 */
  261.         if(T[j]!=Nil)
  262.             visit(T[j]); /* 只遍历非空的结点 */
  263.     printf("\n");
  264. }
  266. /* 逐层、按本层序号输出二叉树 */
  267. void Print(SqBiTree T)
  268. { 
  269.     int j,k;
  270.     Position p;
  271.     TElemType e;
  272.     for(j=1;j<=BiTreeDepth(T);j++)
  273.     {
  274.         printf("第%d层: ",j);
  275.         for(k=1;k<=powl(2,j-1);k++)
  276.         {
  277.             p.level=j;
  278.             p.order=k;
  279.             e=Value(T,p);
  280.             if(e!=Nil)
  281.                 printf("%d:%d ",k,e);
  282.         }
  283.         printf("\n");
  284.     }
  285. }
  288. int main()
  289. {
  290.     Status i;
  291.     Position p;
  292.     TElemType e;
  293.     SqBiTree T;
  294.     InitBiTree(T);
  295.     CreateBiTree(T);
  296.     printf("建立二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
  297.     i=Root(T,&e);
  298.     if(i)
  299.         printf("二叉树的根为：%d\n",e);
  300.     else
  301.         printf("树空，无根\n");
  302.     printf("层序遍历二叉树:\n");
  303.     LevelOrderTraverse(T);
  304.     printf("前序遍历二叉树:\n");
  305.     PreOrderTraverse(T);
  306.     printf("中序遍历二叉树:\n");
  307.     InOrderTraverse(T);
  308.     printf("后序遍历二叉树:\n");
  309.     PostOrderTraverse(T);
  310.     printf("修改结点的层号3本层序号2。");
  311.     p.level=3;
  312.     p.order=2;
  313.     e=Value(T,p);
  314.     printf("待修改结点的原值为%d请输入新值:50 ",e);
  315.     e=50;
  316.     Assign(T,p,e);
  317.     printf("前序遍历二叉树:\n");
  318.     PreOrderTraverse(T);
  319.     printf("结点%d的双亲为%d,左右孩子分别为",e,Parent(T,e));
  320.     printf("%d,%d,左右兄弟分别为",LeftChild(T,e),RightChild(T,e));
  321.     printf("%d,%d\n",LeftSibling(T,e),RightSibling(T,e));
  322.     ClearBiTree(T);
  323.     printf("清除二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
  324.     i=Root(T,&e);
  325.     if(i)
  326.         printf("二叉树的根为：%d\n",e);
  327.     else
  328.         printf("树空，无根\n");
  330.     return 0;
  331. }

测试输出

  1. 请按层序输入结点的值(整型)，0表示空结点，输999结束。结点数≤100:
  2. 建立二叉树后,树空否？0(1:是 0:否) 树的深度=4
  3. 二叉树的根为：1
  4. 层序遍历二叉树:
  5. 1 2 3 4 5 6 7 8 9 10
  6. 前序遍历二叉树:
  7. 1 2 4 8 9 5 10 3 6 7
  8. 中序遍历二叉树:
  9. 8 4 9 2 10 5 1 6 3 7
  10. 后序遍历二叉树:
  11. 8 9 4 10 5 2 6 7 3 1
  12. 修改结点的层号3本层序号2。待修改结点的原值为5请输入新值:50 前序遍历二叉树:
  13. 1 2 4 8 9 50 10 3 6 7
  14. 结点50的双亲为2,左右孩子分别为10,0,左右兄弟分别为4,0
  15. 清除二叉树后,树空否？1(1:是 0:否) 树的深度=0
  16. 树空，无根

二叉树链式结构实现

  1. #include "string.h"
  2. #include "stdio.h"    
  3. #include "stdlib.h"   
  5. #include "math.h"  
  6. #include "time.h"
  8. /*
  9. 二叉树链式结构实现
  10. */
  12. #define OK 1
  13. #define ERROR 0
  14. #define TRUE 1
  15. #define FALSE 0
  17. #define MAXSIZE 100 /* 存储空间初始分配量 */
  19. typedef int Status;        /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
  21. /* 用于构造二叉树********************************** */
  22. int treeIndex=1;
  23. typedef char String[24]; /*  0号单元存放串的长度 */
  24. String str;
  26. Status StrAssign(String T,char *chars)
  27. { 
  28.     int i;
  29.     if(strlen(chars)>MAXSIZE)
  30.         return ERROR;
  31.     else
  32.     {
  33.         T[0]=strlen(chars);
  34.         for(i=1;i<=T[0];i++)
  35.             T[i]=*(chars+i-1);
  36.         return OK;
  37.     }
  38. }
  39. /* ************************************************ */
  41. typedef char TElemType;
  42. TElemType Nil=' '; /* 字符型以空格符为空 */
  44. Status visit(TElemType e)
  45. {
  46.     printf("%c ",e);
  47.     return OK;
  48. }
  50. typedef struct BiTNode  /* 结点结构 */
  51. {
  52.     TElemType data;        /* 结点数据 */
  53.     struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
  54. }BiTNode,*BiTree;
  57. /* 构造空二叉树T */
  58. Status InitBiTree(BiTree *T)
  59. { 
  60.     *T=NULL;
  61.     return OK;
  62. }
  64. /* 初始条件: 二叉树T存在。操作结果: 销毁二叉树T */
  65. void DestroyBiTree(BiTree *T)
  66. { 
  67.     if(*T) 
  68.     {
  69.         if((*T)->lchild) /* 有左孩子 */
  70.             DestroyBiTree(&(*T)->lchild); /* 销毁左孩子子树 */
  71.         if((*T)->rchild) /* 有右孩子 */
  72.             DestroyBiTree(&(*T)->rchild); /* 销毁右孩子子树 */
  73.         free(*T); /* 释放根结点 */
  74.         *T=NULL; /* 空指针赋0 */
  75.     }
  76. }
  78. /* 按前序输入二叉树中结点的值（一个字符） */
  79. /* #表示空树，构造二叉链表表示二叉树T。 */
  80. void CreateBiTree(BiTree *T)
  81. { 
  82.     TElemType ch;
  84.     /* scanf("%c",&ch); */
  85.     ch=str[treeIndex++];
  87.     if(ch=='#') 
  88.         *T=NULL;
  89.     else
  90.     {
  91.         *T=(BiTree)malloc(sizeof(BiTNode));
  92.         if(!*T)
  93.             exit(OVERFLOW);
  94.         (*T)->data=ch; /* 生成根结点 */
  95.         CreateBiTree(&(*T)->lchild); /* 构造左子树 */
  96.         CreateBiTree(&(*T)->rchild); /* 构造右子树 */
  97.     }
  98. }
  100. /* 初始条件: 二叉树T存在 */
  101. /* 操作结果: 若T为空二叉树,则返回TRUE,否则FALSE */
  102. Status BiTreeEmpty(BiTree T)
  103. { 
  104.     if(T)
  105.         return FALSE;
  106.     else
  107.         return TRUE;
  108. }
  110. #define ClearBiTree DestroyBiTree
  112. /* 初始条件: 二叉树T存在。操作结果: 返回T的深度 */
  113. int BiTreeDepth(BiTree T)
  114. {
  115.     int i,j;
  116.     if(!T)
  117.         return 0;
  118.     if(T->lchild)
  119.         i=BiTreeDepth(T->lchild);
  120.     else
  121.         i=0;
  122.     if(T->rchild)
  123.         j=BiTreeDepth(T->rchild);
  124.     else
  125.         j=0;
  126.     return i>j?i+1:j+1;
  127. }
  129. /* 初始条件: 二叉树T存在。操作结果: 返回T的根 */
  130. TElemType Root(BiTree T)
  131. { 
  132.     if(BiTreeEmpty(T))
  133.         return Nil;
  134.     else
  135.         return T->data;
  136. }
  138. /* 初始条件: 二叉树T存在，p指向T中某个结点 */
  139. /* 操作结果: 返回p所指结点的值 */
  140. TElemType Value(BiTree p)
  141. {
  142.     return p->data;
  143. }
  145. /* 给p所指结点赋值为value */
  146. void Assign(BiTree p,TElemType value)
  147. {
  148.     p->data=value;
  149. }
  151. /* 初始条件: 二叉树T存在 */
  152. /* 操作结果: 前序递归遍历T */
  153. void PreOrderTraverse(BiTree T)
  154. { 
  155.     if(T==NULL)
  156.         return;
  157.     printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
  158.     PreOrderTraverse(T->lchild); /* 再先序遍历左子树 */
  159.     PreOrderTraverse(T->rchild); /* 最后先序遍历右子树 */
  160. }
  162. /* 初始条件: 二叉树T存在 */
  163. /* 操作结果: 中序递归遍历T */
  164. void InOrderTraverse(BiTree T)
  165. { 
  166.     if(T==NULL)
  167.         return;
  168.     InOrderTraverse(T->lchild); /* 中序遍历左子树 */
  169.     printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
  170.     InOrderTraverse(T->rchild); /* 最后中序遍历右子树 */
  171. }
  173. /* 初始条件: 二叉树T存在 */
  174. /* 操作结果: 后序递归遍历T */
  175. void PostOrderTraverse(BiTree T)
  176. {
  177.     if(T==NULL)
  178.         return;
  179.     PostOrderTraverse(T->lchild); /* 先后序遍历左子树  */
  180.     PostOrderTraverse(T->rchild); /* 再后序遍历右子树  */
  181.     printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
  182. }
  185. int main()
  186. {
  187.     int i;
  188.     BiTree T;
  189.     TElemType e1;
  190.     InitBiTree(&T);
  193.     StrAssign(str,"ABDH#K###E##CFI###G#J##");
  195.     CreateBiTree(&T);
  197.     printf("构造空二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
  198.     e1=Root(T);
  199.     printf("二叉树的根为: %c\n",e1);
  201.     printf("\n前序遍历二叉树:");
  202.     PreOrderTraverse(T);
  203.     printf("\n中序遍历二叉树:");
  204.     InOrderTraverse(T);
  205.     printf("\n后序遍历二叉树:");
  206.     PostOrderTraverse(T);
  207.     ClearBiTree(&T);
  208.     printf("\n清除二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
  209.     i=Root(T);
  210.     if(!i)
  211.         printf("树空，无根\n");
  213.     return 0;
  214. }

测试输出

  1. 构造空二叉树后,树空否？0(1:是 0:否) 树的深度=5
  2. 二叉树的根为: A
  4. 前序遍历二叉树:ABDHKECFIGJ
  5. 中序遍历二叉树:HKDBEAIFCGJ
  6. 后序遍历二叉树:KHDEBIFJGCA
  7. 清除二叉树后,树空否？1(1:是 0:否) 树的深度=0

线索二叉树

  1. #include "string.h"
  2. #include "stdio.h"    
  3. #include "stdlib.h"   
  5. #include "math.h"  
  6. #include "time.h"
  7. /**
  8. * @brief 
  9. * 线索二叉树
  10. */
  11. #define OK 1
  12. #define ERROR 0
  13. #define TRUE 1
  14. #define FALSE 0
  16. #define MAXSIZE 100 /* 存储空间初始分配量 */
  18. typedef int Status;    /* Status是函数的类型,其值是函数结果状态代码,如OK等 */
  19. typedef char TElemType;
  20. typedef enum {Link,Thread} PointerTag;    /* Link=0表示指向左右孩子指针, */
  21. /* Thread=1表示指向前驱或后继的线索 */
  22. typedef  struct BiThrNode    /* 二叉线索存储结点结构 */
  23. {
  24.     TElemType data;    /* 结点数据 */
  25.     struct BiThrNode *lchild, *rchild;    /* 左右孩子指针 */
  26.     PointerTag LTag;
  27.     PointerTag RTag;        /* 左右标志 */
  28. } BiThrNode, *BiThrTree;
  30. TElemType Nil='#'; /* 字符型以空格符为空 */
  32. Status visit(TElemType e)
  33. {
  34.     printf("%c ",e);
  35.     return OK;
  36. }
  38. /* 按前序输入二叉线索树中结点的值,构造二叉线索树T */
  39. /* 0(整型)/空格(字符型)表示空结点 */
  40. Status CreateBiThrTree(BiThrTree *T)
  41. { 
  42.     TElemType h;
  43.     scanf("%c",&h);
  45.     if(h==Nil)
  46.         *T=NULL;
  47.     else
  48.     {
  49.         *T=(BiThrTree)malloc(sizeof(BiThrNode));
  50.         if(!*T)
  51.             exit(OVERFLOW);
  52.         (*T)->data=h; /* 生成根结点(前序) */
  53.         CreateBiThrTree(&(*T)->lchild); /* 递归构造左子树 */
  54.         if((*T)->lchild) /* 有左孩子 */
  55.             (*T)->LTag=Link;
  56.         CreateBiThrTree(&(*T)->rchild); /* 递归构造右子树 */
  57.         if((*T)->rchild) /* 有右孩子 */
  58.             (*T)->RTag=Link;
  59.     }
  60.     return OK;
  61. }
  63. BiThrTree pre; /* 全局变量,始终指向刚刚访问过的结点 */
  64. /* 中序遍历进行中序线索化 */
  65. void InThreading(BiThrTree p)
  66. { 
  67.     if(p)
  68.     {
  69.         InThreading(p->lchild); /* 递归左子树线索化 */
  70.         if(!p->lchild) /* 没有左孩子 */
  71.         {
  72.             p->LTag=Thread; /* 前驱线索 */
  73.             p->lchild=pre; /* 左孩子指针指向前驱 */
  74.         }
  75.         if(!pre->rchild) /* 前驱没有右孩子 */
  76.         {
  77.             pre->RTag=Thread; /* 后继线索 */
  78.             pre->rchild=p; /* 前驱右孩子指针指向后继(当前结点p) */
  79.         }
  80.         pre=p; /* 保持pre指向p的前驱 */
  81.         InThreading(p->rchild); /* 递归右子树线索化 */
  82.     }
  83. }
  85. /* 中序遍历二叉树T,并将其中序线索化,Thrt指向头结点 */
  86. Status InOrderThreading(BiThrTree *Thrt,BiThrTree T)
  87. { 
  88.     *Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
  89.     if(!*Thrt)
  90.         exit(OVERFLOW);
  91.     (*Thrt)->LTag=Link; /* 建头结点 */
  92.     (*Thrt)->RTag=Thread;
  93.     (*Thrt)->rchild=(*Thrt); /* 右指针回指 */
  94.     if(!T) /* 若二叉树空,则左指针回指 */
  95.         (*Thrt)->lchild=*Thrt;
  96.     else
  97.     {
  98.         (*Thrt)->lchild=T;
  99.         pre=(*Thrt);
  100.         InThreading(T); /* 中序遍历进行中序线索化 */
  101.         pre->rchild=*Thrt;
  102.         pre->RTag=Thread; /* 最后一个结点线索化 */
  103.         (*Thrt)->rchild=pre;
  104.     }
  105.     return OK;
  106. }
  108. /* 中序遍历二叉线索树T(头结点)的非递归算法 */
  109. Status InOrderTraverse_Thr(BiThrTree T)
  110. { 
  111.     BiThrTree p;
  112.     p=T->lchild; /* p指向根结点 */
  113.     while(p!=T)
  114.     { /* 空树或遍历结束时,p==T */
  115.         while(p->LTag==Link)
  116.             p=p->lchild;
  117.         if(!visit(p->data)) /* 访问其左子树为空的结点 */
  118.             return ERROR;
  119.         while(p->RTag==Thread&&p->rchild!=T)
  120.         {
  121.             p=p->rchild;
  122.             visit(p->data); /* 访问后继结点 */
  123.         }
  124.         p=p->rchild;
  125.     }
  126.     return OK;
  127. }
  129. int main()
  130. {
  131.     BiThrTree H,T;
  132.     printf("请按前序输入二叉树(如:'ABDH##I##EJ###CF##G##')\n");
  133.     CreateBiThrTree(&T); /* 按前序产生二叉树 */
  134.     InOrderThreading(&H,T); /* 中序遍历,并中序线索化二叉树 */
  135.     printf("中序遍历(输出)二叉线索树:\n");
  136.     InOrderTraverse_Thr(H); /* 中序遍历(输出)二叉线索树 */
  137.     printf("\n");
  139.     return 0;
  140. }

测试输出

  1. 请按前序输入二叉树(如:'ABDH##I##EJ###CF##G##')
  2. ABDH##I##EJ###CF##G##
  3. 中序遍历(输出)二叉线索树:
  4. H D I B J E A F C G