数据结构:二叉树的遍历(锁定八点智慧树)

云惠网小编 2022年1月15日21:18:34
评论
8697字阅读28分59秒
摘要

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

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

💬 代码实现前序遍历:

#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);                     //求队列大小

0x04 层序遍历

0x00 二叉树的概念(回顾)

0x01 二叉树前序遍历

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

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

🔑 解读:

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

0x01 手动创建二叉树

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

/* 创建新节点 */
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();
}

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

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

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);	 // 销毁队列
}

④ 最后使用完队列后,别忘了销毁队列!

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

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

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

#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;
}

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

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

0x03 二叉树后序遍历

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

🔑 解读:

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

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

🔑 解读:

💬 Queue.c:

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

  

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

0x00 定义二叉树

Ⅱ.  二叉树的遍历

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

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

💬 Queue.h:

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

💬 test.c

📌 笔者:王亦优

📃 更新: 2022.1.12

❌ 勘误: 无

📜 声明: 由于作者水平有限,本文有错误和不准确之处在所难免,本人也很想知道这些错误,恳望读者批评指正!

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

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

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

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

可以!遗憾的是只能解决这里 typedefBTNode* 的问题,还有 Queue.c 里的问题……

0x00 关于遍历

那我们该怎么做,能彻底解决呢?

          (上一层节点出队时带入下一层节点入队)

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

🔑 解读:

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

💬 Queue.h (修改后):

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

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

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

🔑 画图解析:

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


💬 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);                     //求队列大小

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

前言:

参考资料:

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

        ① 让根节点先入队。

似乎有些扯远了,这块在《维生素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;
}

(这里我们用 Ø 符号来表示 NULL)

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

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

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

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

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

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

  

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

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

💬 BinaryTree.h:

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

本篇完。

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

Microsoft. MSDN(Microsoft Developer Network)[EB/OL]. []. .

💬 代码实现:

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

百度百科[EB/OL]. []. https://baike.baidu.com/.

🔑 解读:

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

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

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

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

0x02 二叉树中序遍历

#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);                     //求队列大小

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

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

本文转自 https://blog.csdn.net/weixin_50502862/article/details/122398940

腾讯云618
云惠网小编
SpringCloud -- Config、Bus解析 java

SpringCloud — Config、Bus解析

1、Config1.1、概述简介1. 分布式面临的问题微服务意味着要将单体应用中的业务拆分成一个个子服务,每个服务的粒度相对较小,因此系统中会出现大量的服务。由于每个服务都需要必要...
Java数据结构-了解复杂度 java

Java数据结构-了解复杂度

2.实例分析与计算  四.写在最后  // 计算斐波那契递归fibonacci的时间复杂度 int fibonacci(int N) { return N < 2 ? N : fibonacci...
Java数据结构-认识顺序表 java

Java数据结构-认识顺序表

目录二.顺序表1.概念及结构2.顺序表的实现打印顺序表获取顺序表的有效长度在pos位置新增元素判断是否包含某个元素查找某个元素对应的位置获取/查找pos位置的元素给pos位置的元素...
腾讯云618

发表评论