9f68c0d6113711f2be4fd696311c9056_2b35f5e4f4734819aacb2e65ab6385a6.png

前言

本章将会详细讲解二叉树遍历的四种方式，分别为前序遍历、中序遍历、后续遍历和层序遍历。在学习遍历之前，会先带大家回顾一下二叉树的基本概念。学习二叉树的基本操作前，需要先创建一颗二叉树，然后才能学习其相关的基本操作，考虑到我们刚刚接触二叉树，为了能够先易后难地进行讲解，我们将暂时手动创建一颗简单的二叉树，用来方便大家学习。等二叉树结构了解的差不多后，后期我们会带大家研究二叉树地真正的创建方式。

Ⅰ. 定义二叉树

0x00 二叉树的概念（回顾）

我们之前讲过二叉树的概念了，这里我们简单的回顾下二叉树的概念。

🔗 复习链接：【数据结构】二叉树的概念 | 满二叉树和完全二叉树 | 二叉树的基本性质

❓ 二叉树是什么？① 空树 ② 非空：根节点、根节点的左子树与根节点的又子树组成的。

9af6bf50d55210eb04a3a9ab18f96a46_a88351a41a634cd49a90838974155d9d.png

🔑 解读：从概念中我们不难看出，二叉树的定义是递归式的。因此后续基本操作中，我们基本都是按照该概念来实现的！我们可以来看一下，我们不去看 A，我们来看 A 的左子树，把 B 看作为根节点，是不是一颗二叉树？

7dd049b43690925561c5531bdb1f37fc_45f4a3c35dc64d88bfb8fbe8886fd1b0.png

🔺 所以，我们可以通过采用递归的手法来玩二叉树。

0x01 定义二叉树

💬 BinaryTree.h：

typedef int BTDataType;              
typedef struct BinaryTreeNode {
  struct BinaryTreeNode* left;       // 记录左节点
  struct BinaryTreeNode* right;      // 记录右节点
  BTDataType data;                   // 存储数据
} BTNode;

🔑 解读：

① 还是老规矩，我们创建一个二叉树的数据类型 BTDataType 。

② 由于是链式二叉树，根据二叉树的概念我们定义出 left 和 right 来分别记录根节点的左子树与根节点的右子树，再创建一个变量来存储节点中的数据即可。

③ 最后为了方便表达，我们将这个结构体 typedef 为 BTNode，因为 "struct BinaryTreeNode" 比较麻烦。

0x02 手动创建二叉树

在学习二叉树的基本操作前，需要先创建一颗二叉树，然后才能学习其相关的基本操作。由于我们刚刚接触二叉树，为了能够先易后难地学习，我们手动创建一颗简单的二叉树来来方便大家学习。等二叉树结构了解后，后期我们会带着读者研究二叉树地真正的创建方式。

78018bf94d2c8d41384714facc766c8d_eb9db4cc81d141789bbc823b9cfab94c.png

💬 手动创建一颗二叉树（以上图为例来创建）

/* 创建新节点 */
BTNode* BuyNode(BTDataType x) {
  BTNode* new_node = (BTNode*)malloc(sizeof(BTNode));
  if (new_node == NULL) {
  printf("malloc failed!\n");
  exit(-1);
  }
  new_node->data = x;
  new_node->left = new_node->right = NULL;
  return new_node;
}
/* 手动创建二叉树 */
BTNode* CreateBinaryTree() {
  BTNode* nodeA = BuyNode('A');
  BTNode* nodeB = BuyNode('B');
  BTNode* nodeC = BuyNode('C');
  BTNode* nodeD = BuyNode('D');
  BTNode* nodeE = BuyNode('E');
  BTNode* nodeF = BuyNode('F');
  nodeA->left = nodeB;
  nodeA->right = nodeC;
  nodeB->left = nodeD;
  nodeC->left = nodeE;
  nodeC->right = nodeF;
  return nodeA;
}
int main(void)
{
  BTNode* root = CreateBinaryTree();
}

🔑 画图解析：

894e477ad9605799b2c009972a0bb1b0_cdffd71f3cf847d5b252597770585aca.png

Ⅱ. 二叉树的遍历

0x00 关于遍历

学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历，就是按照某种特定的规则，一次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问节点所做的操作要看具体的应用问题。遍历是二叉树上最重要的运算之一，也是二叉树上进行其他运算的基础。

📚 二叉树遍历（Traversal）：沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。按照规则，二叉树的遍历有：前序 / 中序 / 后序的递归结构遍历。除了前序、中序和后续遍历外，我们还可以对二叉树进行层序遍历。

fdb475fb987f908446cb1ef27711f3f9_19b3f721321041729a71e3693e589f5a.png

0x01 二叉树前序遍历

75eaada590e7647b4bd8ac936b0805d7_1b4fffe09fb84c4cbcf939666aaaa553.png

📚 前序遍历（Preorder Traversal）：访问根节点的操作发生在遍历其右子树之前。

即，首先访问根结点，然后遍历左子树，最后遍历右子树。

💬 代码实现前序遍历：

（这里我们用 Ø 符号来表示 NULL）

/* 二叉树前序遍历 */
void PreOrder(BTNode* root) {
  /* 首先判断根是否为空，为空就返回 */
  if (root == NULL) {        
  printf("Ø "); // 暂时打印出来，便于观察    
  return;       
  }
  /* 走到这里说明不为空，根据前序遍历，先访问根节点 */
  printf("%c ", root->data);
  /* 然后遍历左子树（利用递归） */
  PreOrder(root->left);
  /* 最后遍历右子树（利用递归） */
  PreOrder(root->right);                   
}

🔑 解读：

① 首先判断根是否为空，如果根为空，则返回。这里为了表示，我们把空节点以 " Ø " 打印出来。

② 如果跟不为空，这说明有数据。由于是前序遍历（Preorder），前序遍历是先访问根节点，然后遍历左子树，最后再遍历右子树。所以，我们这里先要访问的是根节点，我们把根节点的数据打印出来。

③ 然后我们需要遍历左子树，这时我们利用递归就可以实现。将根节点 root 的左数 left 传入 PreOrder 函数（将其左树看作根），一直递归下去，直到碰到 root == NULL 则返回。

④ 最后，遍历完左子树后遍历右子树。利用递归，方法同上。

c61b137c4bbe893965689ec689ef8f33_cb21a9d21fdc47b78b9d1b866fd89b43.png

0x02 二叉树中序遍历

📚 中序遍历（Inorder Traversal）：访问根节点的操作发生在遍历其左右子树之中。

即，首先遍历左子树，然后访问根结点，最后遍历右子树。

/* 二叉树中序遍历 */
void InOrder(BTNode* root) {
  /* 首先判断根是否为空，为空就返回 */
  if (root == NULL) {
  printf("Ø ");  // 暂时打印出来，便于观察
  return;
  }
  /* 走到这里说明不为空，根据中序遍历，先遍历左子树 */
  InOrder(root->left);
  /* 然后访问根节点（利用递归） */
  printf("Ø ", root->data);
  /* 最后遍历右子树（利用递归） */
  InOrder(root->right);
}

🔑 解读：

① 首先判断根是否为空，如果根为空，则返回。

② 如果跟不为空，这说明有数据。由于是中序遍历（Inorder），中序遍历是先遍历左子树，然后访问根节点，最后遍历右子树。

0x03 二叉树后序遍历

📚 后序遍历（Postorder Traversal）：访问根节点的操作发生在遍历其左右子树之后。

即，首先遍历左子树，然后遍历右子树，最后访问根结点。

/* 二叉树后序遍历 */
void PostOrder(BTNode* root) {
  /* 首先判断根是否为空，为空就返回 */
  if (root == NULL) {
  printf("/ ");
  return;
  }
  /* 走到这里说明不为空，根据后序遍历，先遍历左子树（利用递归） */
  PostOrder(root->left);
  /* 然后遍历右子树（利用递归） */
  PostOrder(root->right);
  /* 最后访问根节点 */
  printf("%c ", root->data);
}

🔑 解读：

① 首先判断根是否为空，如果根为空，则返回。

② 如果跟不为空，这说明有数据。由于是后序遍历（Postorder），后序遍历是先遍历左子树，然后遍历右子树，最后访问根节点。

0x04 层序遍历

📚 层序遍历（Level Traversal）：设二叉树的根节点所在的层数为1的情况下，从二叉树的根节点出发，首先访问第1层的树根节点，然后再从左到右访问第2层上的节点。接着是第3层的节点……以此类推，自上而下、从左向右地逐层访问树的节点。

d157f0cdb501d0bfdb6a5cdf33241b6a_6b0cbbb4c26b49a3a4e3d29b6313a31c.png

❓ 该如何实现层序遍历呢？

💡 我们可以利用队列的性质来实现！

我们之前再讲过队列，这里你可以选择自己实现一个队列。如果不想实现就直接 CV 即可，因为我们这里重点要学的是层序遍历！

🔗 链接：【数据结构】队列的基本概念 | 从零开始实现队列

💬 Queue.h：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef int QueueDataType;
typedef struct QueueNode {
  struct QueueNode* next;
  QueueDataType data;
} QueueNode;
typedef struct Queue {
  QueueNode* pHead;
  QueueNode* pTail;
} Queue;
void QueueInit(Queue* pQ);                    //队列初始化
void QueueDestroy(Queue* pQ);                 //销毁队列
bool QueueIfEmpty(Queue* pQ);                 //判断队列是否为空
void QueuePush(Queue* pQ, QueueDataType x);   //入队
void QueuePop(Queue* pQ);                     //出队
QueueDataType QueueFront(Queue* pQ);          //返回队头数据
QueueDataType QueueBack(Queue* pQ);           //返回队尾数据
int QueueSize(Queue* pQ);                     //求队列大小

💬 Queue.c：

#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
/* 队列初始化 */
void QueueInit(Queue* pQ) {
  assert(pQ);
  pQ->pHead = pQ->pTail = NULL;
}
/* 销毁队列 */
void QueueDestroy(Queue* pQ) {
  assert(pQ);
  QueueNode* cur = pQ->pHead;
  while (cur != NULL) {
  QueueNode* cur_next = cur->next;
  free(cur);
  cur = cur_next;
  }
  pQ->pHead = pQ->pTail = NULL;
}
/* 判断队列是否为空 */
bool QueueIfEmpty(Queue* pQ) {
  assert(pQ);
  return pQ->pHead == NULL;
}
/* 入队 */
QueueNode* CreateNewNode(QueueDataType x) {
  QueueNode* new_node = (QueueNode*)malloc(sizeof(QueueNode));
  if (new_node == NULL) {
  printf("malloc failed!\n");
  exit(-1);
  }
  new_node->data = x;
  new_node->next = NULL;
  return new_node;
}
void QueuePush(Queue* pQ, QueueDataType x) {
  assert(pQ);
  QueueNode* new_node = CreateNewNode(x);
  if (pQ->pHead == NULL) {
  pQ->pHead = pQ->pTail = new_node;
  }
  else {
  pQ->pTail->next = new_node;
  pQ->pTail = new_node;
  }
}
/* 出队 */
void QueuePop(Queue* pQ) {
  assert(pQ);
  assert(!QueueIfEmpty(pQ));
  QueueNode* save_next = pQ->pHead->next;
  free(pQ->pHead);
  pQ->pHead = save_next;
  if (pQ->pHead == NULL) {
  pQ->pTail = NULL;
  }
}
/* 返回队头数据 */
QueueDataType QueueFront(Queue* pQ) {
  assert(pQ);
  assert(!QueueIfEmpty(pQ));
  return pQ->pHead->data;
}
/* 返回队尾数据 */
QueueDataType QueueBack(Queue* pQ) {
  assert(pQ);
  assert(!QueueIfEmpty(pQ));
  return pQ->pTail->data;
}
/* 求队列大小 */
int QueueSize(Queue* pQ) {
  assert(pQ);
  int count = 0;
  QueueNode* cur = pQ->pHead;
  while (cur != NULL) {
  count++;
  cur = cur->next;
  }
  return count;
}

这里为了方便讲解 #include "展开" 的特点，我们把树的定义放到 test.c 中，并且在 test.c 里完成层序遍历。

7e1ff992765de90ce0166087b7ba11b2_a37e45047a944d69933fcca8d24ef7f6.png

💬 test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
typedef char BTDataType;
typedef struct BinaryTreeNode {
  struct BinaryTreeNode* left;
  struct BinaryTreeNode* right;
  BTDataType data;
} BTNode;
//#include "Queue.h"  解决方案？
/* 创建新节点 */
BTNode* BuyNode(BTDataType x) {
  BTNode* new_node = (BTNode*)malloc(sizeof(BTNode));
  if (new_node == NULL) {
  printf("malloc failed!\n");
  exit(-1);
  }
  new_node->data = x;
  new_node->left = new_node->right = NULL;
  return new_node;
}
/* 手动创建二叉树 */
BTNode* CreateBinaryTree() {
  BTNode* nodeA = BuyNode('A');
  BTNode* nodeB = BuyNode('B');
  BTNode* nodeC = BuyNode('C');
  BTNode* nodeD = BuyNode('D');
  BTNode* nodeE = BuyNode('E');
  BTNode* nodeF = BuyNode('F');
  nodeA->left = nodeB;
  nodeA->right = nodeC;
  nodeB->left = nodeD;
  nodeC->left = nodeE;
  nodeC->right = nodeF;
  return nodeA;
}

由于是我们的数据类型是 BTNode，我们需要修改一下 Queue.h 的 QueueDataType，我们之前一直强调的 typedef 的好处，这里就显现出来了。我们只需要把 int 改成 BTNode 就可以了，而不需要改很多地方。

💬 Queue.h：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef BTNode* QueueDataType;
typedef struct QueueNode {
  struct QueueNode* next;
  QueueDataType data;
} QueueNode;
typedef struct Queue {
  QueueNode* pHead;
  QueueNode* pTail;
} Queue;
void QueueInit(Queue* pQ);                    //队列初始化
void QueueDestroy(Queue* pQ);                 //销毁队列
bool QueueIfEmpty(Queue* pQ);                 //判断队列是否为空
void QueuePush(Queue* pQ, QueueDataType x);   //入队
void QueuePop(Queue* pQ);                     //出队
QueueDataType QueueFront(Queue* pQ);          //返回队头数据
QueueDataType QueueBack(Queue* pQ);           //返回队尾数据
int QueueSize(Queue* pQ);                     //求队列大小

这时我们运行一下代码会出现一个问题，我们发现它报错了：

4050b7d239749fe3019f8f73db503edd_a814ccdc9d584b168e7acb3cf7945482.png

它说，缺少 " { " ，这明显是胡说八道的，咱编译器也没有那么只能，毕竟是也不是VS2077。

❓ 这里产生问题的原因是什么呢？

💡 编译器原则：编译器认识 int，因为 int 是一个内置类型。但是 BTNode* 编译器并不认识，就需要 "往上面" 去找这个类型。这里显然往上找，是找不到它的定义的，所以编译器会报错。

f459574abaa2f7ac55b717ba867b9eb7_d703fafe4b8241d2aa1108899b16d56b.png

如果你要用这个类型，你就需要先定义这个类型。test.c文件中 #include "Queue.h" ，相当于把这里的代码拷贝过去了。这时，由于BTNode*会在上面展开，导致找不到 BTNode* 。

❓ 我把 #include 移到定义类型的代码的后面，可以解决问题吗？

e3fb029a61cdda89a1a4d681f2cbd296_97809d1d78e94c02a7a25f5682563fce.png

可以！遗憾的是只能解决这里 typedef BTNode* 的问题，还有 Queue.c 里的问题……

那我们该怎么做，能彻底解决呢？

🔑 解决方案：前置声明。这样就不会带来问题了，满足了先声明后使用。

e68ae29e10d7aa9336673b959feb2a3e_781043da67d74c10aa19c8a45452d587.png

💬 Queue.h （修改后）：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
// 前置声明
struct BinaryTreeNode;
typedef struct BinaryTreeNode* QueueDataType;
typedef struct QueueNode {
  struct QueueNode* next;
  QueueDataType data;
} QueueNode;
typedef struct Queue {
  QueueNode* pHead;
  QueueNode* pTail;
} Queue;
void QueueInit(Queue* pQ);                    //队列初始化
void QueueDestroy(Queue* pQ);                 //销毁队列
bool QueueIfEmpty(Queue* pQ);                 //判断队列是否为空
void QueuePush(Queue* pQ, QueueDataType x);   //入队
void QueuePop(Queue* pQ);                     //出队
QueueDataType QueueFront(Queue* pQ);          //返回队头数据
QueueDataType QueueBack(Queue* pQ);           //返回队尾数据
int QueueSize(Queue* pQ);                     //求队列大小

似乎有些扯远了，这块在《维生素C语言》中没有详细的说，所以这里还是需要说一下的。解决了这个报错的问题后，我们就可以正式开始写层序遍历了。

💡 思路如下：

① 让根节点先入队。

② 记录当前队头后打印，并让队头出队，然后检测，如过孩子不为空就把孩子带进去。

（上一层节点出队时带入下一层节点入队）

③ 只要队列不为空就说明还没完。如果队列为空，说明下面最后一层没有节点，遍历结束。

📌 注意事项：使用完队列后别忘了要销毁！

💬 代码实现：

void BinaryTreeLevelOrder(BTNode* root) {
  if (root == NULL) {  // 判断根是否为空
  return;
  }
  Queue pQ;   // 建立队列
  QueueInit(&pQ);  // 初始化队列
  QueuePush(&pQ, root); // 先让根进入队列
  while (!QueueIfEmpty(&pQ)) {  // 只要队列内还有元素，就进入循环
  BTNode* front = QueueFront(&pQ);  // 记录当前对头数据
  printf("%c ", front->data);  // 打印队头数据
  QueuePop(&pQ);  // 当队头出队
  if (front->left != NULL) {  // 如果队头元素的左子树不为空
    QueuePush(&pQ, front->left);  // 让左子树进入队列
  }
  if (front->right != NULL) {  // 如果对头元素的右子树不为空
    QueuePush(&pQ, front->right); // 让右子树进入队列
  }
  }
  QueueDestroy(&pQ);  // 销毁队列
}

🔑 解读：

① 首先判断根是否为空，如果为空就没有必要往下走了。

② 建立和初始化队列后，首先让根节点进入队列。只要队列内还有元素存在（说明还没遍历完）就进入循环。每次循环进入后都记录一下当前队头，这里使用 QueueFront 取队头数据即可。之后打印对头的数据。

③ 打印完后让队头出队，随后判断它的左子树和右子树，如果不为空就允许它们进队。我们先判断 left，再判断 right，这样就可以做到一层一层从左往右走的效果了。

④ 最后使用完队列后，别忘了销毁队列！

【数据结构】二叉树的遍历

前言

Ⅰ. 定义二叉树

0x00 二叉树的概念（回顾）

0x01 定义二叉树

0x02 手动创建二叉树

Ⅱ. 二叉树的遍历

0x00 关于遍历

0x01 二叉树前序遍历

0x02 二叉树中序遍历

0x03 二叉树后序遍历

0x04 层序遍历

热门文章

最新文章

相关课程

相关电子书