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

【数据结构】--- 二叉树的递归遍历和非递归遍历【C语言实现】_c语言二叉树的非递归遍历

作者：Monodyee | 2024-03-01 00:02:49

赞

踩

c语言二叉树的非递归遍历

目录

1. 创建一颗二叉树

2.递归前序遍历二叉树

3.递归中序遍历二叉树

4.递归后序遍历二叉树

5. 测试递归打印二叉树代码

6. 非-递归前序遍历二叉树

7. 非-递归实现中序遍历二叉树

8. 非 - 递归实现后序遍历【较为复杂的方法】

9. 非 - 递归实现后序遍历【简单的方法】

10. 二叉树的层次遍历

11. 最后：附全部代码：

对于二叉树的非递归 深度优先遍历，使用的都是栈

对于二叉树的层次遍历，使用的是队列

1. 创建一颗二叉树

依据前序遍历创建二叉树：,树结构如上图所示

输入：  ABD##E##C##

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4.  
  5. // 二叉树的实现
  6.  
  7. // 定义 二叉树的 结构体
  8. typedef struct node{
  9. 	char data;
  10. 	struct node *left;
  11. 	struct node *right;
  12. }Node, *Tree;
  13.  
  14. // 依据前序遍历创建二叉树
  15. // 根左右： ABD##E##C##
  16.  
  17. Tree create_tree(){
  18. 	Node *root = NULL;
  19. 	char ch;
  20. 	scanf("%c", &ch); // 输入 ABD##E##C##
  21.  
  22. 	if (ch != '#'){
  23. 		root = (Node*)malloc(sizeof(Node));
  24. 		root->data = ch;
  25.  
  26. 		root->left = create_tree(); // 递归创建
  27. 		root->right = create_tree();
  28. 	}
  29. 	else{
  30. 		root = NULL;
  31. 	}
  32.  
  33. 	return root;
  34. }

2.递归前序遍历二叉树

  1. // 递归前序遍历二叉树
  2. void preOrderRec(Tree root){
  3. 	if (root != NULL){
  4. 		printf(" %c - ", root->data);
  5. 		preOrderRec(root->left);
  6. 		preOrderRec(root->right);
  7. 	}
  8. }

3.递归中序遍历二叉树

  1. // 递归中序遍历二叉树
  2. void inOrderRec(Tree root){
  3. 	if (root != NULL){
  4. 		inOrderRec(root->left);
  5. 		printf(" %c - ", root->data);
  6. 		inOrderRec(root->right);
  7. 	}
  8. }

4.递归后序遍历二叉树

  1. void backOrderRec(Tree root){
  2. 	if (root != NULL){
  3. 		backOrderRec(root->left);
  4. 		backOrderRec(root->right);
  5. 		printf(" %c - ", root->data);
  6. 		
  7. 	}
  8. }

5. 测试递归打印二叉树代码

  1. int main(){
  2.  
  3. 	printf("starting ------ \n");
  4.  
  5.  
  6. 	Tree root = create_tree();
  7. 	printf("递归前序遍历--- \n");
  8. 	preOrderRec(root);
  9. 	printf("\n");
  10. 	printf("递归中序遍历--- \n");
  11. 	inOrderRec(root);
  12. 	printf("\n");
  13. 	printf("递归后序遍历--- \n");
  14. 	backOrderRec(root);
  15. 	printf("\n");
  16.  
  17.  
  18.  
  19.  
  20. 	return 0;
  21. }

6. 非-递归前序遍历二叉树

前序遍历顺序是：根-左-右

先打印根节点的值，由于栈是先进后出，所以先将 右子树放进去，再将左子树放进去

  1. // 非-递归前序遍历二叉树
  2. void preOrderNRec(Tree root){
  3. 	Tree stack[MAXSIZE], node;
  4. 	int k = -1;
  5.  
  6. 	if (root == NULL){
  7. 		printf("tree is empty-- \n");
  8. 		return;
  9. 	}
  10. 	else{
  11. 		k++;
  12. 		// 仿照一个栈
  13. 		stack[k] = root; // 将根节点入栈
  14. 		while (k > -1){
  15. 			//出栈
  16. 			node = stack[k--];
  17. 			printf(" %c - ", node->data);
  18.  
  19. 			// 先把右子树放进去，栈是先进去后出，所以下面的左子树先出
  20. 			if (node->right != NULL){
  21. 				stack[++k] = node->right;
  22. 			}
  23. 			if (node->left != NULL){
  24. 				stack[++k] = node->left;
  25. 			}
  26.  
  27. 		}
  28.  
  29. 	}
  30. }

7. 非-递归实现中序遍历二叉树

中序遍历的非递归方式实现思想是：

1. 从根结点开始，遍历左孩子同时压栈，当遍历结束，说明当前遍历的结点没有左孩子，

2. 从栈中取出来调用操作函数，然后访问该结点的右孩子，继续以上重复性的操作。

  1. // 非-递归实现中序遍历二叉树
  2. void inOrderNRec(Tree root){
  3. 	Tree stack[MAXSIZE], node;
  4. 	int top = 0;
  5. 	// 判断树是否为空
  6. 	if (root == NULL){
  7. 		printf("tree is empty-- \n");
  8. 		return;
  9. 	}
  10. 	node = root;
  11.  
  12. 	while (node != NULL || top > 0){
  13.  
  14. 		// 将所有的左子树节点入栈
  15. 		while (node != NULL){
  16. 			stack[++top] = node;
  17. 			node = node->left;
  18. 		}
  19. 		//  如果右节点为空的话，执行下列语句
  20. 		node = stack[top--];
  21. 		printf(" %c - ", node->data);
  22.  
  23. 		// 扫描右节点
  24. 		node = node->right;
  25. 	}
  26.  
  27. }

8. 非 - 递归实现后序遍历【较为复杂的方法】

  1. void backOrderNRec(Tree root){
  2.  
  3. 	Node *p = root;
  4. 	Node *stack[MAXSIZE];
  5. 	int num = 0;
  6. 	Node *have_visited = NULL;
  7.  
  8. 	while (NULL != p || num>0)
  9. 	{
  10. 		while (NULL != p)
  11. 		{
  12. 			stack[num++] = p;
  13. 			p = p->left;
  14. 		}
  15. 		p = stack[num - 1];
  16. 		if (NULL == p->right || have_visited == p->right)
  17. 		{
  18. 			printf(" %c - ", p->data);
  19. 			num--;
  20. 			have_visited = p;
  21. 			p = NULL;
  22. 		}
  23. 		else
  24. 		{
  25. 			p = p->right;
  26. 		}
  27. 	}
  28. 	
  29. }

9. 非 - 递归实现后序遍历【简单的方法】

非递归实现后序遍历还是很复杂的，变来变去，指来指去的

但是，我发现一种简单的方法

我们知道 后序遍历的顺序为： 

后序：左->右->根

那么可以把后序当作：根->右->左，最后再反转回来即可。

由于我们是使用的栈，所以先保存根节点， 然后先放进去 左节点，再放 进去 右节点

  1.  
  2. void backOrderNRecSimple(Tree root){
  3. 	Tree stack[MAXSIZE], node;
  4. 	int top = 0;
  5. 	int count = 0;
  6. 	char array[MAXSIZE]; // 使用一个数组来保存数据，方便最后数组的反转
  7.  
  8. 	if (root == NULL){
  9. 		printf("tree is empty-- \n");
  10. 		return;
  11. 	}
  12. 	else{
  13. 		top++;
  14. 		// 仿照一个栈
  15. 		stack[top] = root; // 将根节点入栈
  16. 		while (top > 0){
  17. 			//出栈
  18. 			node = stack[top--];
  19. 			array[count++] = node->data; // 将其保存在一个数组当中
  20.  
  21. 			// 先把右子树放进去，栈是先进去后出，所以下面的左子树先出
  22. 			if (node->left != NULL){
  23. 				stack[++top] = node->left;  // 入栈
  24. 			}
  25. 			if (node->right != NULL){
  26. 				stack[++top] = node->right;
  27. 			}
  28.  
  29. 		}
  30.  
  31. 	}
  32. 	// 反转数组，输出
  33. 	for (int i = count-1; i >= 0; i--){
  34. 		printf(" %c - ", array[i]);
  35. 	}
  36.  
  37. }

附上java代码，更为简单：

  1. ArrayList<Integer> postOrder(TreeNode root) {
  2.     ArrayList<Integer> list = new ArrayList<Integer>();
  3.     if (root != null) {
  4.         Stack<TreeNode> stack = new Stack<TreeNode>();
  5.         stack.push(root);
  6.         while (!stack.isEmpty()) {
  7.             TreeNode node = stack.pop();
  8.             list.add(node.val);
  9.             if (node.left != null) {
  10.                 stack.push(node.left);
  11.             }
  12.             if (node.right != null) {
  13.                 stack.push(node.right);
  14.             }
  15.         }
  16.         //反转
  17.         Collections.reverse(list);
  18.     }
  19.     return list;
  20. }

10. 二叉树的层次遍历

层次遍历使用的是  队列来实现

  1. void Level_traversal(Tree root){
  2.  
  3. 	if (root == NULL){
  4. 		printf("tree is empty-- \n");
  5. 		return;
  6. 	}
  7.  
  8. 	Tree stack[MAXSIZE], node;
  9. 	node = root;
  10. 	int front = 0;  // 使用 front， rear模拟队列
  11. 	int rear = 0;
  12.  
  13. 	stack[rear++] = node;
  14.  
  15. 	while (front != rear){
  16.  
  17. 		node = stack[front++]; // 模拟队列，先获取front当前元素，然后在指向 front ++ 位元素
  18. 		printf(" %c - ", node->data);
  19. 		
  20. 		// 左右子树入队列
  21. 		if (node->left != NULL){
  22. 			stack[rear++] = node->left;
  23. 		}
  24.  
  25. 		if (node->right != NULL){
  26. 			stack[rear++] = node->right;
  27. 		}
  28. 	}
  29.  
  30. }

11. 最后：附全部代码：

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define MAXSIZE 100
  5.  
  6.  
  7. // 二叉树的实现
  8.  
  9. // 定义 二叉树的 结构体
  10. typedef struct node{
  11. 	char data;
  12. 	struct node *left;
  13. 	struct node *right;
  14. }Node, *Tree;
  15.  
  16. // 依据前序遍历创建二叉树
  17. // 根左右： ABD##E##C##
  18.  
  19. Tree create_tree(){
  20. 	Node *root = NULL;
  21. 	char ch;
  22. 	scanf("%c", &ch); // 输入 ABD##E##C##
  23.  
  24. 	if (ch != '#'){
  25. 		root = (Node*)malloc(sizeof(Node));
  26. 		root->data = ch;
  27.  
  28. 		root->left = create_tree(); // 递归创建
  29. 		root->right = create_tree();
  30. 	}
  31. 	else{
  32. 		root = NULL;
  33. 	}
  34.  
  35. 	return root;
  36. }
  37.  
  38.  
  39. // 递归前序遍历二叉树
  40. void preOrderRec(Tree root){
  41. 	if (root != NULL){
  42. 		printf(" %c - ", root->data);
  43. 		preOrderRec(root->left);
  44. 		preOrderRec(root->right);
  45. 	}
  46. }
  47.  
  48. // 非-递归前序遍历二叉树
  49. void preOrderNRec(Tree root){
  50. 	Tree stack[MAXSIZE], node;
  51. 	int top = 0;
  52.  
  53. 	if (root == NULL){
  54. 		printf("tree is empty-- \n");
  55. 		return;
  56. 	}
  57. 	else{
  58. 		top++;
  59. 		// 仿照一个栈
  60. 		stack[top] = root; // 将根节点入栈
  61. 		while (top > 0){
  62. 			//出栈
  63. 			node = stack[top--];
  64. 			printf(" %c - ", node->data);
  65.  
  66. 			// 先把右子树放进去，栈是先进去后出，所以下面的左子树先出
  67. 			if (node->right != NULL){
  68. 				stack[++top] = node->right;  // 入栈
  69. 			}
  70. 			if (node->left != NULL){
  71. 				stack[++top] = node->left;
  72. 			}
  73.  
  74. 		}
  75.  
  76. 	}
  77. }
  78.  
  79.  
  80. // 递归中序遍历二叉树
  81. void inOrderRec(Tree root){
  82. 	if (root != NULL){
  83. 		inOrderRec(root->left);
  84. 		printf(" %c - ", root->data);
  85. 		inOrderRec(root->right);
  86. 	}
  87. }
  88.  
  89. // 非-递归实现中序遍历二叉树
  90. void inOrderNRec(Tree root){
  91. 	Tree stack[MAXSIZE], node;
  92. 	int top = 0;
  93. 	// 判断树是否为空
  94. 	if (root == NULL){
  95. 		printf("tree is empty-- \n");
  96. 		return;
  97. 	}
  98. 	node = root;
  99.  
  100. 	while (node != NULL || top > 0){
  101.  
  102. 		// 将所有的左子树节点入栈
  103. 		while (node != NULL){
  104. 			stack[++top] = node;
  105. 			node = node->left;
  106. 		}
  107. 		//  如果右节点为空的话，执行下列语句
  108. 		node = stack[top--];
  109. 		printf(" %c - ", node->data);
  110.  
  111. 		// 扫描右节点
  112. 		node = node->right;
  113. 	}
  114.  
  115. }
  116.  
  117.  
  118. // 递归后序遍历二叉树
  119. void backOrderRec(Tree root){
  120. 	if (root != NULL){
  121. 		backOrderRec(root->left);
  122. 		backOrderRec(root->right);
  123. 		printf(" %c - ", root->data);
  124. 		
  125. 	}
  126. }
  127.  
  128. // 非 - 递归实现后序遍历
  129. void backOrderNRec(Tree root){
  130.  
  131. 	Node *p = root;
  132. 	Node *stack[MAXSIZE];
  133. 	int num = 0;
  134. 	Node *have_visited = NULL;
  135.  
  136. 	while (NULL != p || num>0)
  137. 	{
  138. 		while (NULL != p)
  139. 		{
  140. 			stack[num++] = p;
  141. 			p = p->left;
  142. 		}
  143. 		p = stack[num - 1];
  144. 		if (NULL == p->right || have_visited == p->right)
  145. 		{
  146. 			printf(" %c - ", p->data);
  147. 			num--;
  148. 			have_visited = p;
  149. 			p = NULL;
  150. 		}
  151. 		else
  152. 		{
  153. 			p = p->right;
  154. 		}
  155. 	}
  156. 	
  157. }
  158.  
  159. void backOrderNRecSimple(Tree root){
  160. 	Tree stack[MAXSIZE], node;
  161. 	int top = 0;
  162. 	int count = 0;
  163. 	char array[MAXSIZE]; // 使用一个数组来保存数据，方便最后数组的反转
  164.  
  165. 	if (root == NULL){
  166. 		printf("tree is empty-- \n");
  167. 		return;
  168. 	}
  169. 	else{
  170. 		top++;
  171. 		// 仿照一个栈
  172. 		stack[top] = root; // 将根节点入栈
  173. 		while (top > 0){
  174. 			//出栈
  175. 			node = stack[top--];
  176. 			array[count++] = node->data; // 将其保存在一个数组当中
  177.  
  178. 			// 先把右子树放进去，栈是先进去后出，所以下面的左子树先出
  179. 			if (node->left != NULL){
  180. 				stack[++top] = node->left;  // 入栈
  181. 			}
  182. 			if (node->right != NULL){
  183. 				stack[++top] = node->right;
  184. 			}
  185.  
  186. 		}
  187.  
  188. 	}
  189. 	// 反转数组，输出
  190. 	for (int i = count-1; i >= 0; i--){
  191. 		printf(" %c - ", array[i]);
  192. 	}
  193.  
  194. }
  195.  
  196. // 层次遍历，打印出二叉树的值
  197. void Level_traversal(Tree root){
  198.  
  199. 	if (root == NULL){
  200. 		printf("tree is empty-- \n");
  201. 		return;
  202. 	}
  203.  
  204. 	Tree stack[MAXSIZE], node;
  205. 	node = root;
  206. 	int front = 0;  // 使用 front， rear模拟队列
  207. 	int rear = 0;
  208.  
  209. 	stack[rear++] = node;
  210.  
  211. 	while (front != rear){
  212.  
  213. 		node = stack[front++]; // 模拟队列，先获取front当前元素，然后在指向 front ++ 位元素
  214. 		printf(" %c - ", node->data);
  215. 		
  216. 		// 左右子树入队列
  217. 		if (node->left != NULL){
  218. 			stack[rear++] = node->left;
  219. 		}
  220.  
  221. 		if (node->right != NULL){
  222. 			stack[rear++] = node->right;
  223. 		}
  224. 	}
  225.  
  226. }
  227.  
  228.  
  229. int main(){
  230.  
  231. 	printf("starting ------ \n");
  232.  
  233.  
  234. 	Tree root = create_tree();
  235. 	printf("递归前序遍历--- \n");
  236. 	preOrderRec(root);
  237. 	printf("\n");
  238. 	printf("递归中序遍历--- \n");
  239. 	inOrderRec(root);
  240. 	printf("\n");
  241. 	printf("递归后序遍历--- \n");
  242. 	backOrderRec(root);
  243. 	printf("\n");
  244. 	printf("------------------\n");
  245.  
  246. 	printf("非递归实现前序遍历--- \n");
  247. 	preOrderNRec(root);
  248. 	printf("\n");
  249.  
  250. 	printf("非递归实现中序遍历--- \n");
  251. 	inOrderNRec(root);
  252. 	printf("\n");
  253.  
  254. 	printf("非递归实现后序遍历--- \n");
  255. 	backOrderNRec(root);
  256. 	printf("\n");
  257.  
  258. 	printf("非递归实现后序遍历  简单的方法 --- \n");
  259. 	backOrderNRecSimple(root);
  260. 	printf("\n");
  261.  
  262. 	printf("层次遍历 --- \n");
  263. 	Level_traversal(root);
  264. 	printf("\n");
  265.  
  266. 	
  267.  
  268. 	// ABD##E##C##
  269.  
  270.  
  271. 	return 0;
  272. }

项目推荐：

2000多G的计算机各行业电子资源分享（持续更新）

2020年微信小程序全栈项目之喵喵交友【附课件和源码】

Spring Boot开发小而美的个人博客【附课件和源码】

Java微服务实战296集大型视频-谷粒商城【附代码和课件】

Java开发微服务畅购商城实战【全357集大项目】-附代码和课件

最全最详细数据结构与算法视频-【附课件和源码】

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

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

  

闽ICP备14008679号