WHCSRL 技术网

二叉链表(C语言实现)——递归和非递归遍历_Mr

 

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<stdbool.h>
  4. #define QueueSize 100 // 借助队列实现层序遍历
  5. #define StackSize 100 // 借助栈实现非递归遍历
  6. typedef char DataType;
  7. typedef struct BiTNode
  8. {
  9. DataType data;
  10. struct BiTNode * lchild;
  11. struct BiTNode * rchild;
  12. }BiTNode,*BiTree;
  13. // 栈元素类型
  14. typedef struct SNode
  15. {
  16. BiTNode * bt; // 结点域
  17. int flag; // 标志域
  18. }ElemType;
  19. void Creat_BiTree(BiTree* T); // 建立树
  20. int Depth_BiTree(BiTree T); // 树深度
  21. int Count_BiTree(BiTree T); // 树结点个数
  22. int LeafCount_BiTree(BiTree T); // 树叶子结点个数
  23. bool Destroy_BiTree(BiTree T); // 销毁树
  24. void PreOrder_Traverse(BiTree T); // 前序遍历递归算法
  25. void InOrder_Traverse(BiTree T); // 中序遍历递归算法
  26. void PostOrder_Traverse(BiTree T); // 后序遍历递归算法
  27. void Level_Traverse(BiTree T); // 层序遍历
  28. void Pre_Traverse(BiTree T); // 前序遍历非递归算法
  29. void In_Traverse(BiTree T); // 中序遍历非递归算法
  30. void Post_Traverse(BiTree T); // 后序遍历非递归算法
  31. int main()
  32. {
  33. BiTree T;
  34. printf("请输入根结点:");
  35. Creat_BiTree(&T);
  36. printf(" ");
  37. printf("树深度:%%d ",Depth_BiTree(T)) ;
  38. printf("树结点个数:%%d ",Count_BiTree(T));
  39. printf("树叶子结点个数:%%d ",LeafCount_BiTree(T));
  40. printf(" ————————层序遍历算法———————— ");
  41. printf("层序遍历:");
  42. Level_Traverse(T);
  43. printf(" ");
  44. printf(" ————————递归遍历算法———————— ");
  45. printf("递归前序遍历:");
  46. PreOrder_Traverse(T);
  47. printf(" ");
  48. printf("递归中序遍历:");
  49. InOrder_Traverse(T);
  50. printf(" ");
  51. printf("递归后序遍历:");
  52. PostOrder_Traverse(T);
  53. printf(" ");
  54. printf(" ————————非递归遍历算法———————— ");
  55. printf("非递归前序遍历:");
  56. Pre_Traverse(T);
  57. printf(" ");
  58. printf("非递归中序遍历:");
  59. In_Traverse(T);
  60. printf(" ");
  61. printf("非递归后序遍历:");
  62. Post_Traverse(T);
  63. printf(" ");
  64. return 0;
  65. }
  66. // 注意产生空指针
  67. void Creat_BiTree(BiTree* T)
  68. {
  69. char ch;
  70. fflush(stdin);
  71. scanf("%%c",&ch);
  72. if(ch == '#')
  73. {
  74. *T = NULL;
  75. return;
  76. }
  77. else
  78. {
  79. *T = (BiTree)malloc(sizeof(BiTNode));
  80. (*T)->data = ch;
  81. printf("请输入%%c的左子树结点:", ch);
  82. Creat_BiTree(&(*T)->lchild);
  83. printf("请输入%%c的右子树结点:", ch);
  84. Creat_BiTree(&(*T)->rchild);
  85. }
  86. }
  87. int Depth_BiTree(BiTree T)
  88. {
  89. if(!T)
  90. return;
  91. // 递归求树深度
  92. return Depth_BiTree(T->lchild) > Depth_BiTree(T->rchild) ? Depth_BiTree(T->lchild)+1 : Depth_BiTree(T->rchild)+1;// 深度=最大层数+1
  93. }
  94. int Count_BiTree(BiTree T)
  95. {
  96. if(!T)
  97. return;
  98. // 递归求树结点数
  99. return Count_BiTree(T->lchild) + Count_BiTree(T->rchild) + 1; // 树结点:左子树结点+右子树结点+根结点
  100. }
  101. int LeafCount_BiTree(BiTree T)
  102. {
  103. if(!T)
  104. return;
  105. if(T->lchild==NULL && T->rchild==NULL) // 左、右孩子指针域均为空时为叶子结点
  106. return 1;
  107. else
  108. return LeafCount_BiTree(T->lchild) + LeafCount_BiTree(T->rchild);
  109. }
  110. bool Destroy_BiTree(BiTree T)
  111. {
  112. if(!T)
  113. return false;
  114. Destroy_BiTree(T->lchild);
  115. Destroy_BiTree(T->rchild);
  116. free(T);
  117. T = NULL; // 防止产生野指针
  118. return true;
  119. }
  120. void PreOrder_Traverse(BiTree T)
  121. {
  122. if(!T)
  123. return;
  124. printf("%%3c",T->data);
  125. PreOrder_Traverse(T->lchild);
  126. PreOrder_Traverse(T->rchild);
  127. }
  128. void InOrder_Traverse(BiTree T)
  129. {
  130. if(!T)
  131. return;
  132. InOrder_Traverse(T->lchild);
  133. printf("%%3c",T->data);
  134. InOrder_Traverse(T->rchild);
  135. }
  136. void PostOrder_Traverse(BiTree T)
  137. {
  138. if(!T)
  139. return;
  140. PostOrder_Traverse(T->lchild);
  141. PostOrder_Traverse(T->rchild);
  142. printf("%%3c",T->data);
  143. }
  144. void Level_Traverse(BiTree T)
  145. {
  146. // 初始化队列
  147. BiTree Q[QueueSize];
  148. int front = 0;
  149. int rear = 0;
  150. if(!T)
  151. return;
  152. Q[rear++] = T;
  153. while(front != rear)
  154. {
  155. BiTree p = Q[front++];
  156. printf("%%3c",p->data);
  157. if(p->lchild!=NULL)
  158. Q[rear++] = p->lchild;
  159. if(p->rchild!=NULL)
  160. Q[rear++] = p->rchild;
  161. }
  162. return;
  163. }
  164. void Pre_Traverse(BiTree T)
  165. {
  166. BiTree p = T; // 初始化工作指针
  167. // 将栈初始化
  168. BiTree Stack[StackSize];
  169. int top = -1;
  170. while(p!=NULL || top!=-1) // 两个条件都不成立时,才能退出循环
  171. {
  172. if(p!=NULL)
  173. {
  174. printf("%%3c",p->data); // 访问输出结点后,将其入栈
  175. Stack[++top] = p;
  176. p = p->lchild;
  177. }
  178. else
  179. {
  180. p = Stack[top--];
  181. p = p->rchild;
  182. }
  183. }
  184. }
  185. void In_Traverse(BiTree T)
  186. {
  187. BiTree p = T; // 初始化工作指针
  188. // 栈初始化
  189. BiTree Stack[StackSize];
  190. int top = -1;
  191. while(p!=NULL || top!=-1)
  192. {
  193. if(p!=NULL)
  194. {
  195. Stack[++top] = p;
  196. p = p->lchild;
  197. }
  198. else
  199. {
  200. p = Stack[top--];
  201. printf("%%3c",p->data); // 出栈后,访问输出结点
  202. p = p->rchild;
  203. }
  204. }
  205. }
  206. void Post_Traverse(BiTree T)
  207. {
  208. BiTree p = T;
  209. ElemType Stack[StackSize];
  210. int top = -1;
  211. while(p!=NULL || top!=-1 )
  212. {
  213. if(p!=NULL)
  214. {
  215. ++top;
  216. Stack[top].bt = p;
  217. Stack[top].flag = 1;
  218. p = p->lchild;
  219. }
  220. else
  221. {
  222. if(Stack[top].flag==1)// 左子树遍历完,访问栈顶元素但不出栈,随后将标志域设为2,并遍历右子树
  223. {
  224. p = Stack[top].bt;
  225. Stack[top].flag = 2;
  226. p = p->rchild;
  227. }
  228. else
  229. {
  230. p = Stack[top--].bt;
  231. printf("%%3c",p->data);
  232. p = NULL; // p置空,以便继续退栈
  233. }
  234. }
  235. }
  236. }

 ①前序遍历

②中序遍历

 

 

③后序遍历

 

④层序遍历

 

推荐阅读