【数据结构指南】深入二叉树遍历

前言：

        在前文中，我们探讨了完全二叉树和满二叉树的概念与性质，并基于完全二叉树实现了堆这一数据结构。然而，对于普通二叉树的认识仍有待深入，本文将系统性地介绍普通二叉树的遍历相关内容。

一、前置说明

一般而言，对于一棵普通二叉树是通过链式结构定义，即每个节点包含三个部分：

1.数据域（data）：用于存储节点的值

        

2.左指针（left）：用于指向左子节点

        

3.右指针（right）：用于指向右子节点        

typedef int BTDataType;//此处将 （int）整形 作为节点存储的内容 typedef struct BinaryTree { BTDataType data; struct BinaryTree* left; struct BinaryTree* right; }BTNode;

        在学习二叉树的基本操作前，需先要先创建一棵二叉树，然后才能学习其相关的基本操作，但是由于我们对二叉树结构掌握还不够深入，为此我们可以通过手动快速创建一棵简单的二叉树。

如下图所示：

代码实现如下：        

BTNode* BuyNode(int x) { BTNode* root = (BTNode *)malloc(sizeof(BTNode)); if (root == NULL) { perror("malloc fail"); return NULL; } root->data = x; root->left = NULL; root->right = NULL; return root; } BTNode* TreeCreate() { BTNode* node1 = BuyNode(1); BTNode* node2 = BuyNode(2); BTNode* node3 = BuyNode(3); BTNode* node4 = BuyNode(4); BTNode* node5 = BuyNode(5); BTNode* node6 = BuyNode(6); node1->left = node2; node1->right = node4; node2->left = node3; node2->right = node6; node4->left = node5; return node1; }

二、二叉树前序遍历

1. 前序遍历的操作

   A、若此棵树为空树，即根节点为NULL，不进行任何操作。

   B、若此棵树不为空，即根节点不为NULL，进行如下操作：

        ①访问根节点

        ②先序遍历左子树

        ③先序遍历右节点

所以先序遍历也可简记为： 根   左   右  的顺序进行遍历，具体如何进行遍历，请帅观众耐心往下看。

现在有如下一棵二叉树：

由根节点 -> 左子树 -> 右子树 这个顺序：

        

那么肯定有帅观众问，直接访问根节点好理解，那么如何理解访问左子树和右子树呢？

       

其实我们可以把左子树再看成一棵树，这样就又可以看成：        根节点    左子树     右子树

        

其实我们也可以把右子树也看成一棵树，这样就也可以看成：     根节点   左子树      右子树

        

如上图所示：根节点1  左子树（以2为根节点）  右子树（以4为根节点）           

                        

                      左子树： 根节点2  左子树（以3为根节点）   右子树（空）

                        

                      右子树： 根节点4  左子树（以5为根节点）  右子树（以6为根节点）

        

这样是不是将一个大问题分成若干个小问题，这不就是递归的思想，所以我们可以通过递归函数的形式，对先序遍历的代码编写。

前序遍历的结果如下图所示：

如果不省略空节点的打印即为：1    2    3    NULL   NULL   NULL   4   5   NULL    NULL    6   NULL   NULL

如果省略空节点的打印即为：1    2    3    4    5    6

2.前序遍历代码实现

//前序遍历 void PrevOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } printf("%d ", root->data); PrevOrder(root->left); PrevOrder(root->right); } 

打印结果如下图所示：        

3.递归调用图

三、二叉树中序遍历

1.中序遍历的操作

   A、若此棵树为空树，即根节点为NULL，不进行任何操作。

   B、若此棵树不为空，即根节点不为NULL，进行如下操作：

        ①中序访问左子树

        ②访问根节点

        ③中序遍历右节点

所以先序遍历也可简记为：左    根   右  的顺序进行遍历。

现有如下一棵二叉树：

中序遍历的结果如下图所示：

如果不省略空节点的打印即为：NULL 3 NULL 2 NULL 1 NULL 5 NULL 4 NULL 6 NULL

如果省略空节点的打印即为： 3     2       1      5      4     6

2.中序遍历代码实现

//中序遍历 void InOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } InOrder(root->left); printf("%d ", root->data); InOrder(root->right); }

四、二叉树后序遍历

1.后序遍历的操作

 A、若此棵树为空树，即根节点为NULL，不进行任何操作。

   B、若此棵树不为空，即根节点不为NULL，进行如下操作：

        ①后序访问左子树

        ②访问根节点

        ③后序遍历右节点

所以先序遍历也可简记为：左    右   根  的顺序进行遍历。

现有如下一棵二叉树：

后序遍历的结果如下图所示：

如果不省略空节点的打印即为：NULL    NULL    3    NULL    2    NULL    NULL    5    NULL    NULL    6    4    1

如果省略空节点的打印即为： 3     2       5      6      4     1

2.后序的遍历代码实现

//后序遍历 void PostOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } PostOrder(root->left); PostOrder(root->right); printf("%d ", root->data); }

五、二叉树层序遍历

1.层次遍历的操作

进行层次遍历时需要借助一个队列，层次遍历的核心思想为：上一层的节点出队，带入下一层的节点入队

如下图所示：

① 将二叉树的根结点入队；

② 若队列非空，则队头结点出队并访问该结点，若它有左孩子，则将其左孩子入队；若它有右孩子，则将其右孩子入队；

下图为二叉树的层次遍历，即按照箭头所指的方向，按照自上而下，自左向右的顺序对二叉树的各个结点进行逐层访问.

可以得到下图二叉树的层次遍历序列为：1   2   3   4   5    6

2.层序遍历代码实现

// 层序遍历 // 上一层节点出队，带入下一层节点入队 void TreeLevelOrder(BTNode* root) { //创建一个队列 Queue q; //初始化队列 QueueInit(&q); //如果根节点指针不为空入队 if (root) QueuePush(&q, root); while (!QueueEmpty(&q)) { //获取队头元素，获取的是QNode节点中存储的值 BTNode* front = QueueFront(&q); //出队头，这里是销毁了QNode节点，而存储在QNode节点中的BTNode节点并未删除 QueuePop(&q); //打印队头信息 printf("%d ", front->data); //并访问该节点，如果该节点的左孩子存在则入队，如果该节点的右孩子存在则入队 if (front->left) QueuePush(&q, front->left); if (front->right) QueuePush(&q, front->right); } //销毁队列 QueueDestroy(&q); }

六、小试牛刀

1.练习一   

二叉树的前序（先序）遍历为：EFHIGJK，二叉树的中序遍历：HFIEJKG，则二叉树为?

核心思路：由前序遍历确定根，中序遍历确定左右子树

        

前序遍历的特点：根  左子树  右子树         中序遍历的特点： 左子树     根      右子树

        

所以对于前序遍历而言，从左往右进行的过程就是相当于对根的遍历

        

而通过根的确定，对中序序列进行分割左右子树。

        

        

二叉树如下图所示：

        

2.练习二

二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树的形状为?

核心思路：由后序遍历确定根，中序遍历确定左右子树

        

后序遍历的特点：  左子树  右子树   根         中序遍历的特点： 左子树     根      右子树

        

对于后序序列从右往左的过程，就相当于对根进行确定

        

 而通过根的确定，对中序序列进行分割左右子树。      

        

        

 二叉树如下图所示：        

        

3.练习三

二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出（同一层从左到右）的序列  

核心思路：由后序遍历确定根，中序遍历确定左右子树

        

后序遍历的特点：  左子树  右子树   根         中序遍历的特点： 左子树     根      右子树

        

对于后序序列从右往左的过程，就相当于对根进行确定

        

 而通过根的确定，对中序序列进行分割左右子树。

        

        

二叉树如下图所示：

        

  故而：层序遍历的结果为：FEDCBA

4.练习四

完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH ，则该完全二叉树的前序序列为?

由层序遍历的特性：自上而下，自左到右

        

二叉树如下图所示：

        

故而前序遍历的结果为：ABDHECFG

 既然看到这里了，不妨关注+点赞+收藏，感谢大家，若有问题请指正。