【数据结构初阶】新学期带你领跑二叉树，二叉树的迭代遍历，递归遍历详解，建议收藏

---

前言

首先我们这里所讲述的二叉树是最为常见的，本章主要带大家了解这种二叉树，并且学会它常见的遍历方式（递归，迭代），由于普通的二叉树没有插入删除的意义，到了AVL，红黑树这种平衡二叉搜索树才有插入删除的意义，所以我们在本章节主要是带大家先简要理解这种结构，对于二叉树有一个初步的认识。

---

一、二叉树的结构介绍

// 对int typedef 是因为二叉树的节点可以存放任意的值，这里是为了方便后续有需要方便调整
typedef int BTDataType;
// 二叉树
typedef struct BinaryTreeNode
{
	//二叉树的每一个节点都有一个值
	BTDataType val;
	//二叉树的每一个节点都有指向左孩子（右孩子）的指针
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;
1
2
3
4
5
6
7
8
9
10
11

这就是一个常见的二叉树

二、二叉树的遍历（递归）（易）

1.前序遍历

对于一棵树，树的本身性质让他非常适合递归，当我们想要递归一颗树的时候，我们可以访问它的根，左子树，右子树，注意是左子树不是左孩子，左子树又可以分成根，左子树，右子树

前序遍历也是标准的深度优先搜索模式：遍历当前节点，再往深处走，走到底就回来尝试新的方法❗️❗️❗️❗️

❗️❗️❗️接下来我们尝试创建这样上图所示的树

// 创建节点并进行初始化
BTNode* BuyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	newnode->left = NULL;
	newnode->right = NULL;
	newnode->val = x;
	return newnode;
}
//手动创建一棵树
BTNode* CreateTree()
{
	BTNode* nodeA = BuyNode('A');
	BTNode* nodeB = BuyNode('B');
	BTNode* nodeC = BuyNode('C');
	BTNode* nodeD = BuyNode('D');
	BTNode* nodeE = BuyNode('E');
	BTNode* nodeF = BuyNode('F');
	BTNode* nodeG = BuyNode('G');

	nodeA->left = nodeB;
	nodeA->right = nodeC;
	nodeB->left = nodeD;
	nodeB->right = nodeE;
	nodeC->left = nodeF;
	nodeC->right = nodeG;
	nodeD->left = NULL;
	nodeD->right = NULL;
	nodeE->left = NULL;
	nodeE->right = NULL;
	nodeF->left = NULL;
	nodeF->right = NULL;
	nodeG->left = NULL;
	nodeG->right = NULL;
	return nodeA;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

❗️❗️❗️我们可以先预测结果，如果将NULL也打印出来的话，上面得到的前序遍历的结果应该是
A B D NULL NULL E NULL NULL C F NULL NULL G NULL NULL

void PreOrder(BTNode* root)
{
	//我们这里用打印的方式表示遍历这个节点的值
	if (root == NULL)
	{
		//如果这棵树本身是空，或者递归到空的位置我们打印NULL
		//再返回上一层
		printf("NULL ");
		return;
	}
	//访问当前节点
	printf("%c ", root->val);
	//访问当前节点的左子树
	PreOrder(root->left);
	//访问当前节点的右子树
	PreOrder(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

看不懂的同学可以按照上面来那张图片想一想

---

2.中序遍历

❗️❗️❗️
对于中序遍历我们先走左子树，根，右子树
例子：ABCDEFG（层序）
我们也可以预测中序遍历的结果：
NULL D NULL B NULL E NULL A NULL F NULL C NULL G NULL

void Inorder(BTNode* root)
{
	if (root ==  NULL)
	{
		printf("NULL ");
		return;
	}
	//访问左子树
	Inorder(root->left);
	//根
	printf("%c ", root->val);
	//右子树
	Inorder(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

3.后序遍历

❗️❗️❗️
后序遍历：左右根
例子：ABCDEFG（层序）
我们也可以预测中序遍历的结果：
NULL NULL D NULL NULL E B NULL NULL F NULL NULL G C A

void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	//左子树
	PostOrder(root->left);
	//右子树
	PostOrder(root->right);
	//根
	printf("%c ", root->val);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

其实到这里大家应该都差不多会了，我们接下来讲讲迭代方式走二叉树

三、二叉树的遍历（迭代）（偏难）

1.利用队列进行迭代 (易)

❗️❗️❗️❗️❗️❗️
建议不会队列的同学看看这一篇：【数据结构】栈和队列，看完这一篇就够了（万字配动图配习题）
队列的代码：有需要的自取

#define  _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
struct BinaryTreeNode;
// 链式结构：表示队列 
typedef struct BinaryTreeNode* QDataType;
typedef struct QListNode
{
	struct QListNode* _next;
	QDataType _data;
}QNode;//队列中结点的结构

// 队列的结构 
typedef struct Queue
{
	QNode* _front;
	QNode* _rear;
}Queue;

// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);

void QueueInit(Queue* q)
{
	assert(q);
	q->_front = NULL;
	q->_rear = NULL;
}
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* tmp = (QNode*)malloc(sizeof(QNode));
	tmp->_next = NULL;
	tmp->_data = data;

	if (q->_rear == NULL)
	{
		q->_front = q->_rear = tmp;
	}
	else
	{
		q->_rear->_next = tmp;
		q->_rear = tmp;
	}
}
void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	QNode* first = q->_front->_next;
	if (first == NULL)
		q->_rear = NULL;//处理这一步
	free(q->_front);
	q->_front = first;
}
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));

	return q->_front->_data;
}
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));

	return q->_rear->_data;
}
int QueueSize(Queue* q)
{
	assert(q);
	int n = 0;
	QNode* cur = q->_front;
	while (cur)
	{
		n++;
		cur = cur->_next;
	}
	return n;
}
int QueueEmpty(Queue* q)
{
	assert(q);
	return q->_front == NULL;
}
void QueueDestroy(Queue* q)
{
	assert(q);
	while (!QueueEmpty(q))
	{
		QNode* tmp = q->_front->_next;
		free(q->_front);
		q->_front = tmp;
	}
	q->_front = q->_rear = NULL;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

我们走层序遍历需要怎么做呢？其实很简单，我们先入头结点入队列，然后每次在出队头元素之前把他的左孩子和右孩子带入节点，遍历队列直到队列为空。❗️❗️❗️❗️

//层序遍历
void LevelOrder(BTNode* root)
{
	//我们借用之前写过的队列
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* first = QueueFront(&q);
		//访问元素
		if (first)
			printf("%c ", first->val);
		else
			printf("NULL ");
		//入下一个元素
		if (first)
		{
			QueuePush(&q, first->left);
			QueuePush(&q, first->right);
		}
		QueuePop(&q);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

2.非递归实现前中后序（难）

❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️
其实这三道题是非常类似的，我们先给大家讲最简单的前序遍历！！

2.1前序遍历

leetcode. 二叉树的前序遍历

前提提示：
一.这里的NULL我们不用访问，访问在这里相当于入一个数组（vector），不懂的同学先把他当成数组！
二. 以及这里所说的最左列为当前节点一直递归它的左子树，即上图的1 , 2，4

分析：我们想要利用栈对我们的二叉树进行前序遍历，我们可以观察前序遍历的时候会先遍历
1–>2–>4，我们一边遍历一边将遍历的值放入栈中看看。发现这棵树的话只剩下4，2，1的右子树就可以走完了！！！！

如何遍历右子树呢？ 实际上我们观察**（3）这颗子树我们可以发现什么，我们没有办法通过一次操作遍历完右子树，但是我们可以把3这颗子树进行拆分，我们入它的最左列节点访问再进行入栈**，就相当于遍历了（3）的左子树与每个节点的根（细品），这个时候我们遍历（7）是不是就是一次操作就能解决了？其实还可以再分一次，分到像（5）的时候，当节点的右子树为空树的时候，我们就访问他！！！

---

重要：
一棵树一定能分到没有右子树的时候，这时访问当前节点相当于访问上一个根节点的右子树
一棵树一定能分到没有右子树的时候，这时访问当前节点相当于访问上一个根节点的右子树
一棵树一定能分到没有右子树的时候，这时访问当前节点相当于访问上一个根节点的右子树
就像访问5的时候是不是相当于访问了2的右子树？是的！

---

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】