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

二叉树遍历的非递归算法_二叉树的遍历,非递归算法

作者：weixin_40725706 | 2024-08-05 18:57:37

赞

踩

二叉树的遍历,非递归算法

非递归的算法主要采用的是循环出栈入栈来实现对二叉树的遍历，下面是过程分析

以下列二叉树为例：（图片来自懒猫老师《数据结构》课程相关内容）

1.前序遍历

前序遍历的顺序为：根结点->左子树->右子树

基本过程：

（1）访问根结点，将根结点入栈

（2）循环逐个访问左子树，执行（1）中步骤；当访问到没有左子树的结点时，跳出循环

（3）栈不为空，根结点出栈，访问右子树

这里以A的左子树为例进行栈的变化过程说明：

可以总结成，没有左子树->出栈+右子树入栈；没有右子树->出栈

代码实现：

  1. void PreOrder(BiNode *bt) { //树的前序遍历
  2. 	SqStack s;
  3. 	s = InitStack();
  4. 	BiNode *p = bt;
  5. 	while (p != NULL || StackEmpty(&s) != 1) { //当p为空，栈也为空时退出循环
  6. 		while (p != NULL) {
  7. 			visit(p->data);//访问根结点
  8. 			Push(&s, p); //将指针p的节点压入栈中
  9. 			p = p->Lchild; //遍历左子树
  10. 		}
  11. 		if (StackEmpty(&s) != 1) { //栈不为空
  12. 			p = Pop(&s); //根结点出栈,相当于回退
  13. 			p = p->rchild; //遍历右子树
  14. 		}
  15. 	}
  16. 	DestroyStack(&s);
  17. }

2.中序遍历

中序遍历的顺序为：左子树->根结点>右子树

基本过程：

（1）将根结点入栈

（2）循环逐个访问左子树，执行（1）中步骤；当访问到没有左子树的结点时，跳出循环

（3）栈不为空，根结点出栈，访问根结点，再访问右子树

其实就是将访问根结点的位置换了

代码实现： 

  1. void MidOrder(BiNode *bt) { //树的中序遍历
  2. 	SqStack s;
  3. 	s = InitStack();
  4. 	BiNode *p = bt;
  5. 	while (p != NULL || StackEmpty(&s) != 1) { //当p为空，栈也为空时退出循环
  6. 		while (p != NULL) {
  7. 			Push(&s, p); //将指针p的节点压入栈中
  8. 			p = p->Lchild; //遍历左子树
  9. 		}
  10. 		if (StackEmpty(&s) != 1) { //栈不为空
  11. 			p = Pop(&s); //根结点出栈,相当于回退
  12. 			visit(p->data);//访问根结点
  13. 			p = p->rchild; //遍历右子树
  14. 		}
  15. 	}
  16. 	DestroyStack(&s);
  17. }

3.后序遍历

 前两种遍历的栈数据类型都是BiNode *，但后序遍历的栈的数据类型要进行重新定义，因为后序遍历的顺序是左子树->右子树>根结点，结点要进入两次栈，出两次栈，为什么会有两次呢？

（1）第一次出栈：只遍历完左子树，该结点不能出栈，需要第二次入栈；找到右子树并遍历

（2）第二次出栈：遍历完左右子树，该结点出栈，并访问

需要注意的是，第二次出栈并访问之后，需要将p指针置空，这样才能在下一次循环的时候，重新从栈中取到一个元素（或者理解成二叉树中的回退操作）

这里设置一个flag标志来区分两次出入栈，并进行不同的操作

栈元素类型定义如下：

  1. typedef struct element {
  2. 	BiNode *ptr;
  3. 	int flag;
  4. } element;

代码实现：

（因为后序遍历和前两种数据类型不一样，这里定义了两套栈函数分别来用，用_1下标区分）

  1. void PostOrder(BiNode *bt) { //树的后序遍历
  2. 	SqStack s;
  3. 	s = InitStack_1();
  4. 	BiNode *p = bt;
  5. 	element elem;
  6. 	while (p != NULL || StackEmpty_1(&s) != 1) { //当p为空，栈也为空时退出循环
  7. 		if (p != NULL) {//第一次入栈，访问左子树
  8. 			elem.ptr = p;
  9. 			elem.flag = 1; //标记flag为1，表示即将第一次入栈
  10. 			Push_1(&s, elem); //将指针p的结点第一次压入栈中
  11. 			p = p->Lchild;
  12. 		} else {
  13. 			elem = Pop_1(&s); //出栈
  14. 			p = elem.ptr; //p指向当前要处理的结点
  15. 			if (elem.flag == 1) {
  16. 				//flag==1时，说明只访问过左子树，还要访问右子树
  17. 				elem.flag = 2;
  18. 				Push_1(&s, elem); //结点第二次压入栈中
  19. 				p = p->rchild;
  20. 			} else {
  21. 				//flag==2时，左右子树都已经访问过了
  22. 				visit(p->data);
  23. 				p = NULL; //访问后，p赋为空，确保下次循环时继续出栈（相当于回退）
  24. 			}
  25. 		}
  26. 	}
  27. 	DestroyStack_1(&s);
  28. }

4. 完整代码

分为三个文件包，一个是存放栈的操作函数，一个是存放二叉树的非递归遍历函数，一个是对二叉树的非递归遍历功能进行的测试，第三个文件调用前两个头文件就可以测试完整功能

（1）数组堆栈_二叉树非递归.h

  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4. #define STACK_INIT_SIZE 100
  5. #define STACKINCREMENT 10
  6. typedef char Datatype;
  7.  
  8. typedef struct BiNode {
  9. 	Datatype data;//数据内容
  10. 	struct BiNode  *Lchild;//指向左孩子结点
  11. 	struct BiNode  *rchild;//指向右孩子结点
  12. } BiNode;
  13.  
  14. typedef BiNode *Elemtype;
  15. typedef struct element {
  16. 	BiNode *ptr;
  17. 	int flag;
  18. } element;
  19.  
  20. typedef element Elemtype_1;
  21. typedef struct {
  22. 	Elemtype *data;//用于前序和中序遍历
  23. 	Elemtype_1 *data_1;//用于后序遍历
  24. 	int top;//栈顶指针，这里用int类型表示指针的下标
  25. 	int stacksize;
  26. } SqStack;
  27. Elemtype Pop(SqStack *s);
  28.  
  29. SqStack InitStack() {//空栈构造函数
  30. 	SqStack s;
  31. 	s.data = (Elemtype *)malloc(STACK_INIT_SIZE * sizeof(Elemtype));
  32. 	s.top = -1; //表示栈空
  33. 	s.stacksize = STACK_INIT_SIZE;
  34. 	if (s.data != NULL)
  35. 	{}
  36. 	else
  37. 		printf("Init error!\n");
  38. 	return s;
  39. }
  40.  
  41. void DestroyStack(SqStack *s) {//销毁栈函数
  42. 	free(s->data);
  43. }
  44.  
  45. int StackEmpty(SqStack *s) {//判断是否为空栈,是返回1，否 返回0
  46. 	if (s->top == -1)
  47. 		return 1;
  48. 	else
  49. 		return 0;
  50. }
  51.  
  52. void Push(SqStack *s, Elemtype e) {//添加元素入栈
  53. 	if (s->top >= s->stacksize) {
  54. 		s->data = (Elemtype *)malloc((STACK_INIT_SIZE + STACKINCREMENT) * sizeof(Elemtype));
  55. 		s->stacksize += STACKINCREMENT;
  56. 		if (s->data != NULL) {}
  57. 		else
  58. 			printf("Push error!\n");
  59. 	} else {
  60. 		s->top++;
  61. 		s->data[s->top] = e;
  62. 	}
  63. }
  64.  
  65. Elemtype Pop(SqStack *s) {
  66. 	if (StackEmpty(s) != 1 && s->top >= 0) {
  67. 		Elemtype e = s->data[s->top];
  68. 		s->top--;
  69. 		return e;
  70. 	}
  71. 	printf("Pop error!\n");
  72. }
  73.  
  74. SqStack InitStack_1() {//空栈构造函数
  75. 	SqStack s;
  76. 	s.data_1 = (Elemtype_1 *)malloc(STACK_INIT_SIZE * sizeof(Elemtype_1));
  77. 	s.top = -1; //表示栈空
  78. 	s.stacksize = STACK_INIT_SIZE;
  79. 	if (s.data != NULL)
  80. 	{}
  81. 	else
  82. 		printf("Init error!\n");
  83. 	return s;
  84. }
  85.  
  86. void DestroyStack_1(SqStack *s) {//销毁栈函数
  87. 	free(s->data_1);
  88. }
  89.  
  90. int StackEmpty_1(SqStack *s) {//判断是否为空栈,是返回1，否 返回0
  91. 	if (s->top == -1)
  92. 		return 1;
  93. 	else
  94. 		return 0;
  95. }
  96.  
  97. void Push_1(SqStack *s, Elemtype_1 e) {//添加元素入栈
  98. 	if (s->top >= s->stacksize) {
  99. 		s->data_1 = (Elemtype_1 *)malloc((STACK_INIT_SIZE + STACKINCREMENT) * sizeof(Elemtype_1));
  100. 		s->stacksize += STACKINCREMENT;
  101. 		if (s->data_1 != NULL) {}
  102. 		else
  103. 			printf("Push error!\n");
  104. 	} else {
  105. 		s->top++;
  106. 		s->data_1[s->top] = e;
  107. 	}
  108. }
  109.  
  110. Elemtype_1 Pop_1(SqStack *s) {
  111. 	if (StackEmpty(s) != 1 && s->top >= 0) {
  112. 		Elemtype_1 e = s->data_1[s->top];
  113. 		s->top--;
  114. 		return e;
  115. 	}
  116. 	printf("Pop error!\n");
  117. }

 （2）二叉树遍历（非递归）.h

  1. #include "数组堆栈_二叉树非递归.h"
  2.  
  3. BiNode *Creat(char *str, int *i, int len) { //树的创建
  4. 	struct BiNode *bt = NULL;
  5. 	char ch = str[(*i)++];
  6. 	if (ch == '#' || *i >= len) {
  7. 		bt = NULL;
  8. 	} else {
  9. 		bt = (struct BiNode *)malloc(sizeof(BiNode));
  10. 		if (bt != NULL) {
  11. 			bt->data = ch;
  12. 			bt->Lchild = Creat(str, i, len); //这里的递归要赋值，这样才能建立不同域中的连接关系
  13. 			bt->rchild = Creat(str, i, len);
  14. 		}
  15. 	}
  16. 	return bt;//返回的一直是根结点
  17. }
  18.  
  19. void visit(Datatype e) {
  20. 	printf("%c ", e);
  21. }
  22.  
  23. void PreOrder(BiNode *bt) { //树的前序遍历
  24. 	SqStack s;
  25. 	s = InitStack();
  26. 	BiNode *p = bt;
  27. 	while (p != NULL || StackEmpty(&s) != 1) { //当p为空，栈也为空时退出循环
  28. 		while (p != NULL) {
  29. 			visit(p->data);//访问根结点
  30. 			Push(&s, p); //将指针p的节点压入栈中
  31. 			p = p->Lchild; //遍历左子树
  32. 		}
  33. 		if (StackEmpty(&s) != 1) { //栈不为空
  34. 			p = Pop(&s); //根结点出栈,相当于回退
  35. 			p = p->rchild; //遍历右子树
  36. 		}
  37. 	}
  38. 	DestroyStack(&s);
  39. }
  40.  
  41. void MidOrder(BiNode *bt) { //树的中序遍历
  42. 	SqStack s;
  43. 	s = InitStack();
  44. 	BiNode *p = bt;
  45. 	while (p != NULL || StackEmpty(&s) != 1) { //当p为空，栈也为空时退出循环
  46. 		while (p != NULL) {
  47. 			Push(&s, p); //将指针p的节点压入栈中
  48. 			p = p->Lchild; //遍历左子树
  49. 		}
  50. 		if (StackEmpty(&s) != 1) { //栈不为空
  51. 			p = Pop(&s); //根结点出栈,相当于回退
  52. 			visit(p->data);//访问根结点
  53. 			p = p->rchild; //遍历右子树
  54. 		}
  55. 	}
  56. 	DestroyStack(&s);
  57. }
  58.  
  59. void PostOrder(BiNode *bt) { //树的后序遍历
  60. 	SqStack s;
  61. 	s = InitStack_1();
  62. 	BiNode *p = bt;
  63. 	element elem;
  64. 	while (p != NULL || StackEmpty_1(&s) != 1) { //当p为空，栈也为空时退出循环
  65. 		if (p != NULL) {//第一次入栈，访问左子树
  66. 			elem.ptr = p;
  67. 			elem.flag = 1; //标记flag为1，表示即将第一次入栈
  68. 			Push_1(&s, elem); //将指针p的结点第一次压入栈中
  69. 			p = p->Lchild;
  70. 		} else {
  71. 			elem = Pop_1(&s); //出栈
  72. 			p = elem.ptr; //p指向当前要处理的结点
  73. 			if (elem.flag == 1) {
  74. 				//flag==1时，说明只访问过左子树，还要访问右子树
  75. 				elem.flag = 2;
  76. 				Push_1(&s, elem); //结点第二次压入栈中
  77. 				p = p->rchild;
  78. 			} else {
  79. 				//flag==2时，左右子树都已经访问过了
  80. 				visit(p->data);
  81. 				p = NULL; //访问后，p赋为空，确保下次循环时继续出栈（相当于回退）
  82. 			}
  83. 		}
  84. 	}
  85. 	DestroyStack_1(&s);
  86. }

 （3）二叉树遍历（非递归）.c

  1. #include "二叉树遍历（非递归）.h"
  2.  
  3. main() {
  4. 	printf("测试二叉树遍历（非递归）算法\n");
  5. 	printf("建立一个二叉树-->");
  6. 	BiNode *bt;
  7. 	int i = 0, len;
  8. 	char str[50];
  9. 	printf("输入一个字符串用于建立二叉树:");
  10. 	scanf("%s", str);
  11. 	len = strlen(str);
  12. 	bt = Creat(str, &i, len);
  13. 	printf("测试遍历操作:\n");
  14. 	printf("测试树的前序遍历:");
  15. 	PreOrder(bt);
  16. 	printf("\n");
  17. 	printf("测试树的中序遍历:");
  18. 	MidOrder(bt);
  19. 	printf("\n");
  20. 	printf("测试树的后序遍历:");
  21. 	PostOrder(bt);
  22. 	printf("\n");
  23. }

5.测试输出

 初学小白，有错误的话欢迎指正喔！~

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

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

  

闽ICP备14008679号