C语言_数据结构总结10：二叉树的递归/非递归遍历

 纯C语言实现，不涉及C++ 

遍历是二叉树各种操作的基础，例如对于一棵给定二叉树求结点的双亲/求结点的孩子/求二叉树的高度/求叶结点个数/判断两棵二叉树是否相等……所有这些操作都是在二叉树遍历的过程中进行的。因此必须掌握二叉树的各种遍历过程，并能灵活用以解决各种问题。

常见的遍历次序有：先序，中序，后序

->其中“序”是指根结点何时被访问。

先序：根结点->左子树->右子树

中序: 左子树->根结点->右子树

后序: 左子树->右子树->根结点

对于递归遍历还是很好实现的，如

1. 递归先序遍历

void preOrder(BiTNode* root) {
	if (root != NULL) {
		printf("%d ", root->data);// 访问当前节点（这里是打印节点的值）
		preOrder(root->lchild);
		preOrder(root->rchild);
	}
}

2. 递归中序遍历

void inOrder(BiTNode* root) {
	if (root != NULL)
	{
		inOrder(root->lchild);
		printf("%d ", root->data);
		inOrder(root->rchild);
	}
}

3. 递归后序遍历

void postOrder(BiTNode* root) {
	if (root != NULL)
	{
		postOrder(root->lchild);
		postOrder(root->rchild);
		printf("%d ", root->data);
	}
}

下面具体来说一下二叉树的非递归的先/中/后遍历：

栈的后进先出（LIFO）特性使得它非常适合模拟递归调用过程中系统栈的行为。在二叉树的非递归遍历中，使用栈可以保存待访问的节点和控制节点的访问顺序，从而实现与递归遍历相同的效果。故：使用栈来保存待访问的节点和控制节点的访问顺序。

下面结合代码模拟二叉树的非递归的先/中/后遍历的全过程：

首先，需要先声明一下基本结构和栈的基本操作：

typedef struct BiTNode {  //树结点
    ElemType data;
    struct BiTNode* lchild;
    struct BiTNode* rchild;
}BiTNode;

typedef struct stackNode {  //栈结点
    struct BiTNode* pBiTNode;  // 指向二叉树节点的指针
    struct stackNode* next;  // 指向下一个栈节点的指针
}stackNode;

typedef struct stack {  //栈结构
    struct stackNode* top;  //指向栈顶结点
}stack;

1. 初始化栈

void initStack(stack* s) {
    s->top = NULL;
}

2. 判空操作

若栈顶指针为 NULL，则栈为空，返回 1；否则返回 0

int isEmpty(stack* s) {
    return s->top == NULL;
}

3. 入栈

用于将一个二叉树节点压入栈中

void push(stack* s, BiTNode* node) {
	stackNode* newStackNode = (stackNode*)malloc(sizeof(stackNode));  
	if (newStackNode == NULL)
	{
		printf("内存分配失败!\n");
		return;
	}
	newStackNode->pBiTNode = node;  // 将新栈节点指向传入的二叉树节点
	newStackNode->next = s->top;  // 让新栈节点的 next 指针指向当前栈顶节点
	s->top = newStackNode;  // 更新栈顶指针为新栈节点
}

4. 出栈

用于从栈中弹出一个二叉树节点,便于后面遍历操作中进行访问

BiTNode* pop(stack* s) {
	if (isEmpty(s))
	{
		printf("栈空，无元素可出栈!\n");
		return NULL;
	}
	stackNode* temp = s->top;   // 临时保存栈顶节点
	BiTNode* node = temp->pBiTNode; // 取出栈顶节点所指向的二叉树节点
	s->top = temp->next;  // 更新栈顶指针为原栈顶节点的下一个节点
	free(temp);   // 释放原栈顶节点的内存
	return node;
}

5.销栈

在遍历结束之后，栈中不再有未处理的结点，栈已经完成了它辅助遍历的过程，此时需要销毁栈结构以释放栈中所占用的内存

void destroyStack(stack* s) {
	while (!isEmpty(s)) {  // 当栈不为空时，不断弹出栈顶节点
		pop(s);
	}
}

好的，有了上面的基本辅助操作后，我们来开始正式对树进行操作

1. 创建新的树结点

BiTNode* createNewBiTNode(ElemType value) {
	BiTNode* newBiTNode = (BiTNode*)malloc(sizeof(BiTNode));
	if (newBiTNode == NULL)
	{
		printf("内存分配失败!\n");
		return NULL;
	}
	newBiTNode->data = value;
	newBiTNode->lchild = NULL;
	newBiTNode->rchild = NULL;
	return newBiTNode;
}

2. 销毁树结构

void destroyTree(BiTNode* root) {
	if (root == NULL)
	{
		return;
	}
	destroyTree(root->lchild);
	destroyTree(root->rchild);
	free(root);
}

3. 非递归先序遍历

 具体思路 ：是先将根节点入栈，然后循环处理栈中的节点，每次弹出栈顶节点并访问，接着将其右子节点和左子节点依次入栈（注意顺序，因为栈是后进先出，所以先入右子结点）

void preOrderTraversal(BiTNode* root) {
	if (root == NULL)
	{
		return;
	}
	stack s;
	initStack(&s);
	push(&s, root);
	while (!isEmpty(&s)) {
		BiTNode* p = pop(&s);
		printf("%d ", p->data);
		if (p->rchild != NULL)
		{
			push(&s, p->rchild);
		}
		if (p->lchild != NULL)
		{
			push(&s, p->lchild);
		}
	}
	printf("\n");
	destroyStack(&s);//遍历完记得销毁栈
}

4. 非递归中序遍历

 具体思路 ：先将根节点及左子树的所有节点依次入栈，然后出栈访问节点，再让指针指向该节点的右子树，重复上述入栈、出栈访问、指向右子树的操作直至栈空且指针为空。

void inOrderTraversal(BiTNode* root) {
	stack s;
	initStack(&s);
	BiTNode* p = root;
	while (p != NULL || !isEmpty(&s)) {
		while (p != NULL) {
			push(&s, p);
			p = p->lchild;
		}
		p = pop(&s);
		printf("%d ", p->data);
		p = p->rchild;
	}
	printf("\n");
	destroyStack(&s);遍历完记得销毁栈
}

5. 非递归后序遍历

相对复杂一些，需要使用两个栈来完成。

 具体思路 ：先将根节点压入第一个栈，然后循环处理第一个栈，每次弹出栈顶节点并压入第二个栈，接着将其左子节点和右子节点依次压入第一个栈。最后，依次弹出第二个栈的节点并访问。

void postOrderTraversal(BiTNode* root) {
	if (root == NULL)
	{
		return;
	}
	stack s1, s2;
	initStack(&s1);
	initStack(&s2);

	push(&s1, root);
	while (!isEmpty(&s1)) {
		BiTNode* p = pop(&s1);
		push(&s2, p);
		if (p->lchild != NULL)
		{
			push(&s1, p->lchild);
		}
		if (p->rchild != NULL)
		{
			push(&s1, p->rchild);
		}
	}
	while (!isEmpty(&s2)) {
		BiTNode* p = pop(&s2);
		printf("%d ", p->data);
	}
	printf("\n");
	destroyStack(&s1);//遍历完记得销毁栈
	destroyStack(&s2);
}

6. 建一棵树测试遍历

int main() {
	//创建一棵树
	BiTNode* root = createNewBiTNode(1);
	root->lchild = createNewBiTNode(2);
	root->rchild = createNewBiTNode(3);
	root->lchild->lchild = createNewBiTNode(4);
	root->lchild->rchild = createNewBiTNode(5);
	root->rchild->lchild = createNewBiTNode(6);

	printf("递归先序遍历的结果：");
	preOrder(root);
	printf("\n");

	printf("递归中序遍历的结果：");
	inOrder(root);
	printf("\n");

	printf("递归后序遍历的结果：");
	postOrder(root);
	printf("\n\n");

	printf("非递归先序遍历的结果：");
	preOrderTraversal(root);

	printf("非递归中序遍历的结果：");
	inOrderTraversal(root);

	printf("非递归后序遍历的结果：");
	postOrderTraversal(root);

	destroyTree(root);
	return 0;
}

7. 完整代码

#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;

typedef struct BiTNode {  //树结点
	ElemType data;
	struct BiTNode* lchild;
	struct BiTNode* rchild;
}BiTNode;

typedef struct stackNode {  //栈结点
	struct BiTNode* pBiTNode;  // 指向二叉树节点的指针
	struct stackNode* next;  // 指向下一个栈节点的指针
}stackNode;

typedef struct stack {  //栈结构
	struct stackNode* top;  //指向栈顶结点
}stack;

//1.1 初始化栈
void initStack(stack* s) {
	s->top = NULL;
}

//2.1判空
// 该函数用于判断栈是否为空，若栈顶指针为 NULL，则栈为空，返回 1；
// 否则返回 0
int isEmpty(stack* s) {
	return s->top == NULL;
}

//3.1 入栈
 该函数用于将一个二叉树节点压入栈中
void push(stack* s, BiTNode* node) {
	stackNode* newStackNode = (stackNode*)malloc(sizeof(stackNode));  
	if (newStackNode == NULL)
	{
		printf("内存分配失败!\n");
		return;
	}
	newStackNode->pBiTNode = node;  // 将新栈节点指向传入的二叉树节点
	newStackNode->next = s->top;  // 让新栈节点的 next 指针指向当前栈顶节点
	s->top = newStackNode;  // 更新栈顶指针为新栈节点
}

//4.1 出栈，返回出栈的树结点
// 该函数用于从栈中弹出一个二叉树节点
BiTNode* pop(stack* s) {
	if (isEmpty(s))
	{
		printf("栈空，无元素可出栈!\n");
		return NULL;
	}
	stackNode* temp = s->top;   // 临时保存栈顶节点
	BiTNode* node = temp->pBiTNode; // 取出栈顶节点所指向的二叉树节点
	s->top = temp->next;  // 更新栈顶指针为原栈顶节点的下一个节点
	free(temp);   // 释放原栈顶节点的内存
	return node;
}

//5.1 销栈，在遍历结束之后，栈中不再有未处理的结点，栈已经完成了它辅助遍历的过程，此时需要销毁栈结构以释放栈中所占用的内存
void destroyStack(stack* s) {
	while (!isEmpty(s)) {  // 当栈不为空时，不断弹出栈顶节点
		pop(s);
	}
}

//1.1 创建新的树结点
BiTNode* createNewBiTNode(ElemType value) {
	BiTNode* newBiTNode = (BiTNode*)malloc(sizeof(BiTNode));
	if (newBiTNode == NULL)
	{
		printf("内存分配失败!\n");
		return NULL;
	}
	newBiTNode->data = value;
	newBiTNode->lchild = NULL;
	newBiTNode->rchild = NULL;
	return newBiTNode;
}

//2.1 销毁树结构
void destroyTree(BiTNode* root) {
	if (root == NULL)
	{
		return;
	}
	destroyTree(root->lchild);
	destroyTree(root->rchild);
	free(root);
}

//3.1 递归先序遍历
void preOrder(BiTNode* root) {
	if (root != NULL) {
		printf("%d ", root->data);// 访问当前节点（这里是打印节点的值）
		preOrder(root->lchild);
		preOrder(root->rchild);
	}
}

//4.1 递归中序遍历
void inOrder(BiTNode* root) {
	if (root != NULL)
	{
		inOrder(root->lchild);
		printf("%d ", root->data);
		inOrder(root->rchild);
	}
}

//5.1 递归后序遍历
void postOrder(BiTNode* root) {
	if (root != NULL)
	{
		postOrder(root->lchild);
		postOrder(root->rchild);
		printf("%d ", root->data);
	}
}

//6.1 非递归先序遍历
//先序遍历的顺序是：根节点->左子树->右子树。
// 非递归实现可以借助栈来模拟递归调用的过程。
// 具体思路是先将根节点入栈，然后循环处理栈中的节点，每次弹出栈顶节点并访问，接着将其右子节点和左子节点依次入栈
// （注意顺序，因为栈是后进先出，所以先入右子节点）。
void preOrderTraversal(BiTNode* root) {
	if (root == NULL)
	{
		return;
	}
	stack s;
	initStack(&s);
	push(&s, root);
	while (!isEmpty(&s)) {
		BiTNode* p = pop(&s);
		printf("%d ", p->data);
		if (p->rchild != NULL)
		{
			push(&s, p->rchild);
		}
		if (p->lchild != NULL)
		{
			push(&s, p->lchild);
		}
	}
	printf("\n");
	destroyStack(&s);//遍历完记得销毁栈
}

//7.1 非递归中序遍历
//非递归中序遍历的核心思路是利用栈来模拟递归调用的过程，
// 先将根节点及左子树的所有节点依次入栈，然后出栈访问节点，再让指针指向该节点的右子树，重复上述入栈、出栈访问、指向右子树的操作直至栈空且指针为空。
void inOrderTraversal(BiTNode* root) {
	stack s;
	initStack(&s);
	BiTNode* p = root;
	while (p != NULL || !isEmpty(&s)) {
		while (p != NULL) {
			push(&s, p);
			p = p->lchild;
		}
		p = pop(&s);
		printf("%d ", p->data);
		p = p->rchild;
	}
	printf("\n");
	destroyStack(&s);遍历完记得销毁栈
}

//8.1 非递归后序遍历
//后序遍历的顺序是：左子树 -> 右子树 -> 根节点。
// 非递归实现相对复杂一些，需要使用两个栈来完成。
// 具体思路是先将根节点压入第一个栈，然后循环处理第一个栈，每次弹出栈顶节点并压入第二个栈，接着将其左子节点和右子节点依次压入第一个栈。
// 最后，依次弹出第二个栈的节点并访问。
void postOrderTraversal(BiTNode* root) {
	if (root == NULL)
	{
		return;
	}
	stack s1, s2;
	initStack(&s1);
	initStack(&s2);

	push(&s1, root);
	while (!isEmpty(&s1)) {
		BiTNode* p = pop(&s1);
		push(&s2, p);
		if (p->lchild != NULL)
		{
			push(&s1, p->lchild);
		}
		if (p->rchild != NULL)
		{
			push(&s1, p->rchild);
		}
	}
	while (!isEmpty(&s2)) {
		BiTNode* p = pop(&s2);
		printf("%d ", p->data);
	}
	printf("\n");
	destroyStack(&s1);//遍历完记得销毁栈
	destroyStack(&s2);
}

int main() {
	//创建一棵树
	BiTNode* root = createNewBiTNode(1);
	root->lchild = createNewBiTNode(2);
	root->rchild = createNewBiTNode(3);
	root->lchild->lchild = createNewBiTNode(4);
	root->lchild->rchild = createNewBiTNode(5);
	root->rchild->lchild = createNewBiTNode(6);

	printf("递归先序遍历的结果：");
	preOrder(root);
	printf("\n");

	printf("递归中序遍历的结果：");
	inOrder(root);
	printf("\n");

	printf("递归后序遍历的结果：");
	postOrder(root);
	printf("\n\n");

	printf("非递归先序遍历的结果：");
	preOrderTraversal(root);

	printf("非递归中序遍历的结果：");
	inOrderTraversal(root);

	printf("非递归后序遍历的结果：");
	postOrderTraversal(root);

	destroyTree(root);
	return 0;
}

8. 运行截图

 分享个小妙招 ：有什么不明白的，复制完整代码，然后问AI:“请给出以上代码中的xx操作的详细过程”。

文章如有出错不足处，欢迎评论区指出，如果觉得文章不错，就给我点个赞吧，谢谢！