浅学一下二叉树链式存储结构的遍历

二叉树的链式结构

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。由于这里讨论的是二叉树，所以只有左右两个节点，事实上二叉树的链式结构不止于此，比如红黑树就是用的三叉链。

代码声明：

// 二叉链
struct BinaryTreeNode {
    struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
}

// 三叉链
struct BinaryTreeNode {
    struct BinTreeNode* _pParent; // 指向当前节点的双亲
    struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
}；
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

实现二叉树的链式结构遍历

所谓遍历 (Traversal) 是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。

由于被访问的结点必是某子树的根，所以 N(Node）、L(Left subtree）和 R(Right subtree）又可解释为根、根的左子树和根的右子树。所以 NLR、LNR 和 LRN 分别又称为先根遍历、中根遍历和后根遍历。

前序遍历

NLR：前序遍历( Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前 。

通俗来讲就是先根后左再右。

以上图为例，以前序的方式遍历，

首先读到的是 A 节点，

然后再读 A 节点的左子树，

对 A 的左子树再进行前序遍历，

所以第二读到的就是 B ，

对 B 的左子树再进行前序遍历，

所以第三读到的就是 D ，

对 D 的左子树再进行前序遍历，

所以第四读到的是 ∅ ，

遍历完 D 的左树再去遍历右树，

对 D 的右子树再进行前序遍历，

所以第五读到的是 ∅ ，

此时完成了对 B 的左子树的遍历，

开始对 B 的右子树进行前序遍历，

所以第六读到的是 ∅ ，

此时完成了对 B 的右子树的遍历，

也就完成了对 A 的左子树的遍历，

下一步开始遍历 A 的右子树，

所以第七读到的是 C ，

对 C 的左子树进行前序遍历，

所以第八读到的是 E ，

对 E 的左子树进行前序遍历，

所以第九读到的是 ∅ ，

对 E 的右子树进行前序遍历，

所以第十读到的是 ∅ ，

此时完成了对 C 的左子树的遍历，

下一步开始遍历 C 的右子树，

所以第十一读到的是 F ，

对 F 的左子树进行前序遍历，

所以第十二读到的是 ∅ ，

对 F 的右子树进行前序遍历，

所以第十三读到的是 ∅ ，

至此完成了对 C 的右子树的遍历，

和对 A 的右子树的遍历。

由遍历过程可见遍历是通过递归完成的，

代码如下：

void PrevOrder(BTNode* root) {
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->val);
	PrevOrder(root->left);
	PrevOrder(root->right);
}
1
2
3
4
5
6
7
8
9
10

---

中序遍历

LNR：中序遍历 (Inorder Traversal) ——访问根结点的操作发生在遍历其左右子树之中（间） 。

通俗来讲就是先左后中再右。

还是以该图为例。

先对 A 的左子树进行中序遍历，

由于 B 不是空树，

所以要先对 B 的左子树进行中序遍历，

由于 D 不是空树，

所以要先对 D 的左子树进行中序遍历，

所以第一个读到的是 ∅ ，

然后返回，

第二个读到的就是 D ，

再对 D 的右树进行遍历，

第三个读到的就是 ∅ ，

此时也就完成了对 B 的左子树的遍历，

所以第四个读到的就是 B ，

再对 B 的右树进行遍历，

所以第五个读到的就是 ∅ ，

此时也就完成了对 A 的左子树的遍历，

所以第六个读到的就是 A ，

接下来遍历 A 的右子树，

由于 C 不是空树，

所以要先对 C 的左子树进行中序遍历，

由于 E 不是空树，

所以要先对 E 的左子树进行中序遍历，

所以第七个读到的是 ∅ ，

然后返回，

第八个读到的就是 E ，

再对 E 的右树进行遍历，

所以第九个读到的就是 ∅ ，

此时也就完成了对 C 的左子树的遍历，

所以第十个读到的就是 C ，

接下来对 C 的右子树进行遍历，

由于 F 不是空树，

所以要先对 F 的左子树进行遍历，

所以第十一个读到的就是 ∅ ，

然后返回，

所以第十二个读到的就是 F ，

接下来对 F 的右子树进行遍历，

所以第十三个读到的就是 ∅ ，

至此完成了对 C 的右树的遍历，

也就完成了对 A 的右树的遍历。

代码与前序相似：

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

---

后序遍历

LRN：后序遍历 (Postorder Traversal) ——访问根结点的操作发生在遍历其左右子树之后。

通俗来讲就是先左后右再中间。

下面就不具体讲解遍历过程了，

给出遍历顺序：

代码如下：

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

---

层序遍历

除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为 1 ，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第 2 层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

层序遍历实现起来是比较麻烦的。因为要一层一层遍历，这一层有多少个元素？如何判断进入这一层？所以简单的遍历是做不到的，这里需要借助队列这一数据结构实现。

下边遍历过程就忽略空节点了，比如 D 的两个左右节点。

大体思路如下：

先将根节点入队列，

然后读取队列头的数据，

同时出队列的头，并把它的子节点入队列。

以上图为例，

首先 A 节点入队列，

然后读取 A 节点存放的数据，

同时 A 节点出队列，并把 B 、C 节点入队列，

此时队列中有 B 、C 两节点；

读取队列头 B 的数据，

同时 B 节点出队列，并把 D 、E 节点入队列，

此时队列中有 C、D、E 三节点；

读取队列头 C 的数据，

同时 C 节点出队列，并把 F、G 节点入队列，

此时队列中有 D、E、F、G 四节点；

读取队列头 D 的数据，

同时 D 节点出队列，此时没有子节点可以入队列，

此时队列中有 E、F、G 三节点；

读取队列头 E 的数据，

同时 E 节点出队列，并把 H 节点入队列，

此时队列中有 F、G、H 三节点；

读取队列头 F 的数据，

同时 F 节点出队列，此时没有子节点可以入队列，

此时队列中有 G、H 两节点；

读取队列头 G 的数据，

同时 G 节点出队列，此时没有子节点可以入队列，

此时队列中只有 H 节点；

读取队列头 H 的数据，

同时 H 节点出队列，此时没有子节点可以入队列，

此时队列中没有节点，队列为空；

至此，就完成了整棵树的层序遍历。

很明显，层序遍历是通过循环控制的，当队列为空时循环结束。

链表模拟实现

借助链表模拟队列的话代码如下：

void LevelOrder(BTNode* root) {
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);
	while (!QueueEmpty(&q)) {
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%c ", front->val);
		if (front->left)
			QueuePush(&q, front->left);
		if (front->right)
			QueuePush(&q, front->right);
	}
	QueueDestroy(&q);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

其中与队列有关的函数声明放在下面，具体实现可参照文章栈和队列。

typedef struct BinaryTreeNode* QDataType;
//队列初始化
void QueueInit(Queue* pq);
//销毁队列
void QueueDestroy(Queue* pq);
//队尾入队列
void QueuePush(Queue* pq, QDataType x);
//队头出队列
void QueuePop(Queue* pq);
//取队头的数据
QDataType QueueFront(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);
1
2
3
4
5
6
7
8
9
10
11
12
13

数组模拟实现

当然，也可以使用数组模拟队列。

使用数组的话出队列头的数据直接移动下标即可。

代码如下：

void LevelOrder(BTNode* root) {
    struct TreeNode* Queue[10000] = { 0 };
    int head = 0, tail = 0;
    Queue[tail++] = root;
    while (head < tail) {
        printf("%c", Queue[head]->val);
        if (Queue[head]->left)
            Queue[tail++] = Queue[head]->left;
        if (Queue[head]->right)
            Queue[tail++] = Queue[head]->right;
        ++head;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13