devbox
你好赵伟
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

二叉树的遍历方法（C语言）_二叉树的遍历c语言

作者：你好赵伟 | 2024-06-14 03:04:30

赞

踩

二叉树的遍历c语言

前言：二叉树是一种基础的数据模型，学会遍历二叉树可以帮助我们解决很多问题，所以今天和大家讨论的是有关二叉树如何遍历的问题。

题目要求：完成二叉树的先序遍历，中序遍历，后序遍历的递归，非递归遍历，以及层次遍历，并计算树的高度。（从文件中读取，并以文件的形式输出）

二叉树示例（“#”代表空树）

 1.准备工作

#include<stdio.h>
#include<stdlib.h>
typedef struct BiTNode {
    char data;
    struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;                //BiTNode为结构体变量   BiTree为结构体指针

2.创建二叉树

BiTree CreateTree(FILE*fp_1) {
    BiTree T;
    char ch, trmp;
    fscanf(fp_1,"%c",&ch);
    if(ch=='#')
        T=NULL;
    else {
        T=(BiTNode*)malloc(sizeof(BiTNode));
        T->data=ch;
        T->lchild=CreateTree(fp_1);
        T->rchild=CreateTree(fp_1);
    }
    return T;
}

3.前序遍历（递归）

  1. void PreOrderTraverse(BiTree T) {
  2. 	if(T) {
  3. 		FILE*fp;
  4. 		fp=fopen("test_1.txt","a");
  5. 		fprintf(fp,"%c ",T->data);
  6. 		fclose(fp);
  7. 		PreOrderTraverse(T->lchild);
  8. 		PreOrderTraverse(T->rchild);
  9. 	}
  10. }

4.前序遍历（非递归）

  1. void PreOrderTraverse_1(BiTree T) {
  2. 	FILE*fp;
  3. 	BiTree stack[100],node;
  4. 	int top=0;
  5. 	if(T==NULL) {
  6. 		printf("tree is empty--\n");
  7. 		return ;
  8. 	} else {
  9. 		top++;
  10. 		stack[top]=T;
  11. 		while(top>0) {
  12. 			node=stack[top--];
  13. 			fp=fopen("test_1.txt","a");
  14. 			fprintf(fp,"%c ",node->data);
  15. 			fclose(fp);
  16. 			if(node->rchild!=NULL)
  17. 				stack[++top]=node->rchild;
  18. 			if(node->lchild!=NULL)
  19. 				stack[++top]=node->lchild;
  20. 		}
  21. 	}
  22. }

5.中序遍历（递归）

  1. void InOrderTraverse(BiTree T) {
  2. 	if(T) {
  3. 		FILE*fp;
  4. 		InOrderTraverse(T->lchild);
  5. 		fp=fopen("test_1.txt","a");
  6. 		fprintf(fp,"%c ",T->data);
  7. 		fclose(fp);
  8. 		InOrderTraverse(T->rchild);
  9. 		
  10. 	}
  11. }

6.中序遍历（非递归）

  1. void InOrderTraverse_1(BiTree T) {
  2. 	BiTree stack[100],node;
  3. 	int top=0;
  4. 	FILE*fp;
  5. 	if(T==NULL) {
  6. 		printf("tree is empty--\n");
  7. 		return ;
  8. 	}
  9. 	node=T;
  10. 	while(node!=NULL||top>0) {
  11. 		while(node!=NULL) {
  12. 			stack[++top]=node;
  13. 			node=node->lchild;
  14. 		}
  15. 		node=stack[top--];					//出栈 
  16. 		fp=fopen("test_1.txt","a");
  17. 		fprintf(fp,"%c ",node->data);
  18. 		fclose(fp);
  19. 		node=node->rchild;
  20. 	}
  21. }

7.后序遍历（递归）

  1. void PostOrderTraverse(BiTree T) {
  2. 	if(T) {
  3. 		FILE*fp;
  4. 		PostOrderTraverse(T->lchild);
  5. 		PostOrderTraverse(T->rchild);
  6. 		fp=fopen("test_1.txt","a");
  7. 		fprintf(fp,"%c ",T->data);
  8. 		fclose(fp);
  9. 	}
  10. }

8.后序遍历（非递归）

  1. void PostOrderTraverse_1(BiTree T) {
  2. 	BiTree p=T,stack[100],have_visited=NULL;
  3. 	int num=0;
  4. 	FILE*fp;
  5. 	while(p!=NULL||num>0){
  6. 		while(p!=NULL){
  7. 			stack[num++]=p;
  8. 			p=p->lchild;
  9. 		}
  10. 		p=stack[num-1];
  11. 		if(p->rchild==NULL||p->rchild==have_visited){	//要么右子树为空，要么右子树已经被访问 
  12. 			fp=fopen("test_1.txt","a");
  13. 			fprintf(fp,"%c ",p->data);
  14. 			fclose(fp);
  15. 			num--;
  16. 			have_visited=p;
  17. 			p=NULL; 
  18. 		}
  19. 		else
  20. 		p=p->rchild;
  21. 	}
  22. }

9.层次遍历 

  1. void level(BiTree T) {
  2. 	FILE*fp;
  3. 	BiTree queue[20],pTemp;
  4. 	int cur=0,pre=0;						//队列中cur是队尾，pre是队头 
  5. 	queue[cur++]=T;
  6. 	while(cur!=pre) {
  7. 		pTemp=queue[pre++];					//出队列 
  8. 		fp=fopen("test_1.txt","a");
  9. 		fprintf(fp,"%c ",pTemp->data);
  10. 		fclose(fp);
  11. 		if(pTemp->lchild!=NULL)
  12. 			queue[cur++]=pTemp->lchild;		//入队列 
  13. 		if(pTemp->rchild!=NULL)
  14. 			queue[cur++]=pTemp->rchild;		//入队列 
  15. 	}	
  16. }

10.树的高度

  1. int height(BiTree T) {						//树的高度
  2. 	int ld,rd;
  3. 	if(T==NULL)
  4. 		return 0;
  5. 	else {
  6. 		ld=height(T->lchild);
  7. 		rd=height(T->rchild);
  8. 		return 1+(ld>rd?ld:rd);
  9. 	}
  10. }

总代码

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. typedef struct BiTNode {
  4. 	char data;
  5. 	struct BiTNode *lchild,*rchild;
  6. } BiTNode,*BiTree;				//BiTNode为结构体变量   BiTree为结构体指针
  7.  
  8. BiTree CreateTree(FILE*fp_1) {
  9. 	BiTree T;
  10. 	char ch, trmp;
  11. 	fscanf(fp_1,"%c",&ch);
  12. 	if(ch=='#')
  13. 		T=NULL;
  14. 	else {
  15. 		T=(BiTNode*)malloc(sizeof(BiTNode));
  16. 		T->data=ch;
  17. 		T->lchild=CreateTree(fp_1);
  18. 		T->rchild=CreateTree(fp_1);
  19. 	}
  20. 	return T;
  21. }
  22.  
  23. void InOrderTraverse(BiTree T) {
  24. 	if(T) {
  25. 		FILE*fp;
  26. 		InOrderTraverse(T->lchild);
  27. 		fp=fopen("test_1.txt","a");
  28. 		fprintf(fp,"%c ",T->data);
  29. 		fclose(fp);
  30. 		InOrderTraverse(T->rchild);
  31. 		
  32. 	}
  33. }
  34.  
  35. void PreOrderTraverse(BiTree T) {
  36. 	if(T) {
  37. 		FILE*fp;
  38. 		fp=fopen("test_1.txt","a");
  39. 		fprintf(fp,"%c ",T->data);
  40. 		fclose(fp);
  41. 		PreOrderTraverse(T->lchild);
  42. 		PreOrderTraverse(T->rchild);
  43. 	}
  44. }
  45.  
  46. void PostOrderTraverse(BiTree T) {
  47. 	if(T) {
  48. 		FILE*fp;
  49. 		
  50. 		PostOrderTraverse(T->lchild);
  51. 		PostOrderTraverse(T->rchild);
  52. 		fp=fopen("test_1.txt","a");
  53. 		fprintf(fp,"%c ",T->data);
  54. 		fclose(fp);
  55. 	}
  56. }
  57.  
  58. void InOrderTraverse_1(BiTree T) {
  59. 	BiTree stack[100],node;
  60. 	int top=0;
  61. 	FILE*fp;
  62. 	if(T==NULL) {
  63. 		printf("tree is empty--\n");
  64. 		return ;
  65. 	}
  66. 	node=T;
  67. 	while(node!=NULL||top>0) {
  68. 		while(node!=NULL) {
  69. 			stack[++top]=node;
  70. 			node=node->lchild;
  71. 		}
  72. 		node=stack[top--];					//出栈 
  73. 		fp=fopen("test_1.txt","a");
  74. 		fprintf(fp,"%c ",node->data);
  75. 		fclose(fp);
  76. 		node=node->rchild;
  77. 	}
  78. }
  79.  
  80. void PreOrderTraverse_1(BiTree T) {
  81. 	FILE*fp;
  82. 	BiTree stack[100],node;
  83. 	int top=0;
  84. 	if(T==NULL) {
  85. 		printf("tree is empty--\n");
  86. 		return ;
  87. 	} else {
  88. 		top++;
  89. 		stack[top]=T;
  90. 		while(top>0) {
  91. 			node=stack[top--];
  92. 			fp=fopen("test_1.txt","a");
  93. 			fprintf(fp,"%c ",node->data);
  94. 			fclose(fp);
  95. 			if(node->rchild!=NULL)
  96. 				stack[++top]=node->rchild;
  97. 			if(node->lchild!=NULL)
  98. 				stack[++top]=node->lchild;
  99. 		}
  100. 	}
  101. }
  102.  
  103. void PostOrderTraverse_1(BiTree T) {
  104. 	BiTree p=T,stack[100],have_visited=NULL;
  105. 	int num=0;
  106. 	FILE*fp;
  107. 	while(p!=NULL||num>0){
  108. 		while(p!=NULL){
  109. 			stack[num++]=p;
  110. 			p=p->lchild;
  111. 		}
  112. 		p=stack[num-1];
  113. 		if(p->rchild==NULL||p->rchild==have_visited){	//要么右子树为空，要么右子树已经被访问 
  114. 			fp=fopen("test_1.txt","a");
  115. 			fprintf(fp,"%c ",p->data);
  116. 			fclose(fp);
  117. 			num--;
  118. 			have_visited=p;
  119. 			p=NULL; 
  120. 		}
  121. 		else
  122. 		p=p->rchild;
  123. 	}
  124. }
  125.  
  126. void level(BiTree T) {
  127. 	FILE*fp;
  128. 	BiTree queue[20],pTemp;
  129. 	int cur=0,pre=0;						//队列中cur是队尾，pre是队头 
  130. 	queue[cur++]=T;
  131. 	while(cur!=pre) {
  132. 		pTemp=queue[pre++];					//出队列 
  133. 		fp=fopen("test_1.txt","a");
  134. 		fprintf(fp,"%c ",pTemp->data);
  135. 		fclose(fp);
  136. 		if(pTemp->lchild!=NULL)
  137. 			queue[cur++]=pTemp->lchild;		//入队列 
  138. 		if(pTemp->rchild!=NULL)
  139. 			queue[cur++]=pTemp->rchild;		//入队列 
  140. 	}	
  141. }
  142.  
  143. int height(BiTree T) {						//树的高度
  144. 	int ld,rd;
  145. 	if(T==NULL)
  146. 		return 0;
  147. 	else {
  148. 		ld=height(T->lchild);
  149. 		rd=height(T->rchild);
  150. 		return 1+(ld>rd?ld:rd);
  151. 	}
  152. }
  153.  
  154. int main() {
  155. 	BiTree T;
  156. 	FILE*fp_1;
  157. 	fp_1=fopen("test_2.txt","r");
  158. 	T=CreateTree(fp_1);
  159. 	fclose(fp_1);
  160. 	FILE*fp;
  161. 	fp=fopen("test_1.txt","w");
  162. 	fprintf(fp,"先序遍历：");
  163. 	fclose(fp);
  164. 	PreOrderTraverse(T);
  165. 	fp=fopen("test_1.txt","a");
  166. 	fprintf(fp,"\n");
  167. 	fclose(fp);
  168. 	
  169. 	fp=fopen("test_1.txt","a");
  170. 	fprintf(fp,"中序遍历：");
  171. 	fclose(fp);
  172. 	InOrderTraverse(T);
  173. 	fp=fopen("test_1.txt","a");
  174. 	fprintf(fp,"\n");
  175. 	fclose(fp);
  176. 	
  177. 	fp=fopen("test_1.txt","a");
  178. 	fprintf(fp,"后序遍历：");
  179. 	fclose(fp);
  180. 	PostOrderTraverse(T);
  181. 	fp=fopen("test_1.txt","a");
  182. 	fprintf(fp,"\n");
  183. 	fclose(fp);
  184. 	
  185. 	fp=fopen("test_1.txt","a");
  186. 	fprintf(fp,"非递归先序遍历：");
  187. 	fclose(fp);
  188. 	PreOrderTraverse_1(T);
  189. 	fp=fopen("test_1.txt","a");
  190. 	fprintf(fp,"\n");
  191. 	fclose(fp);
  192.  
  193. 	fp=fopen("test_1.txt","a");
  194. 	fprintf(fp,"非递归中序遍历：");
  195. 	fclose(fp);
  196. 	InOrderTraverse_1(T);
  197. 	fp=fopen("test_1.txt","a");
  198. 	fprintf(fp,"\n");
  199. 	fclose(fp);
  200.  
  201. 	fp=fopen("test_1.txt","a");
  202. 	fprintf(fp,"非递归后序遍历：");
  203. 	fclose(fp);
  204. 	PostOrderTraverse_1(T);
  205. 	fp=fopen("test_1.txt","a");
  206. 	fprintf(fp,"\n");
  207. 	fclose(fp);
  208. 	
  209. 	fp=fopen("test_1.txt","a");
  210. 	fprintf(fp,"层次遍历：");
  211. 	fclose(fp);
  212. 	level(T);
  213. 	fp=fopen("test_1.txt","a");
  214. 	fprintf(fp,"\n二叉树的高度为：%d\n",height(T));
  215. 	fclose(fp);
  216. 	return 0;
  217. }

输入样例

 输出样例

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/716008
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号