DS链式二叉树的遍历(11)

文章目录

前言
一、链式二叉树的结构
- 结构定义
- 手动搭建
二、二叉树的遍历
- 三种常见遍历(前序、中序、后序)
- 层序遍历
总结

前言

堆是特殊的二叉树，可二叉树本身也很值得研究~
正文开始！

一、链式二叉树的结构

前文也提到了二叉树一共有两种，空树与非空，且用递归定义
在这里插入图片描述

结构定义

typedef int BTDataType;//定义数据类型，可以根据需要更改typedef struct BinaryTreeNode
{BTDataType data;				//存储数据struct BinaryTreeNode* left;	//左指针struct BinaryTreeNode* right;	//右指针
}BTNode;

手动搭建

为了方便我们更快地学习二叉树的结构和基本操作，这里直接手动搭建一颗二叉树。不仅如此，在做二叉树相关题目时，由于部分原因做题平台不支持普通用户使用调试功能，可以快速搭建二叉树在本地编译器上进行调试相关操作
在这里插入图片描述

BTNode* BuyNode(BTDataType x)
{BTNode* tmp = (BTNode*)malloc(sizeof(BTNode));if (tmp == NULL){perror("malloc fail!");exit(-1);}; tmp->data = x;tmp->left = NULL;tmp->right = NULL;return tmp;
}BTNode* CreatBinaryTree()
{BTNode* n1 = BuyNode(1);BTNode* n2 = BuyNode(2);BTNode* n3 = BuyNode(3);BTNode* n4 = BuyNode(4);BTNode* n5 = BuyNode(5);BTNode* n6 = BuyNode(6);n1->left = n2;n1->right = n3;n2->left = n4;n2->right = n5;n3->left = n6;return n1;
}

二、二叉树的遍历

学习二叉树的结构，最简单的方式就是遍历，遍历是二叉树上最重要的运算之一，也是二叉树上进行其他运算的基础。二叉树遍历按照某种特定的规则，依次对二叉树中的节点进行对应的操作，并且每个节点只操作一次
在这里插入图片描述

三种常见遍历(前序、中序、后序)

根据规定，访问顺序左子树是先于右子树，导致了二叉树遍历有三种递归式结构前序/中序/后序的遍历，被访问节点必是某子树的根。根据英文缩写可以通过N、L、R表示根、左子树、右子树，对此NLR、LNR和LRN称为先根遍历、中根遍历和后根遍历
在这里插入图片描述

你可以尝试一下用三种遍历方式并写出访问顺序(空也会访问，用N代表)

在这里插入图片描述

前序:123NNN45NN6NN
中序:N3N2N1N5N4N6N
后序:NN3N2NN5NN641

我就以前序遍历为例子，给出递归的过程：
达到1号节点为根，访问左子树；达到2号节点为根；访问左子树；达到3号节点为根；访问左子树；达到为空位置返回，访问根(3号)，访问右子树；达到空位置，以3号为根子树访问完；以2号为根左子树访问完，访问根(2号)，以此类推直到遍历完毕

在这里插入图片描述

层序遍历

设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历
在这里插入图片描述
思路也很明确：

先将根节点入队，然后开始从队头出数据
出队头的数据同时将队头左右子树的结点入队（遇到NULL则不入队）
重复第二步，直到队列为空

在这里插入图片描述

void LevelOrder(BTNode* root)
{Queue q;					//创建队列QueueInit(&q);				//初始化队列if (root)					//根节点不为空则入队QueuePush(&q, root);while (!QueueEmpty(&q))		//队列不为空，循环继续{BTNode* front = QueueFront(&q);QueuePop(&q);			//出队printf("%d ", front->data);if (front->left)		//如果左子树不为空则入队QueuePush(&q, front->left);if (front->right)		//右子树不为空入队QueuePush(&q, front->right);}QueueDestory(&q);//销毁队列
}

如果你有看我的C++专栏的话，这里用队列超快超方便

对于层序遍历，我们可以来一个例子立马实践：判断二叉树是否是完全二叉树

思路很明显，我们假设是完全二叉树，也就是说即使出现了空节点，那我们也把空节点放入队列，在遍历的时候验空，如果空改变指针，此时后面就不能再出现非空节点了，否则立刻返回false

// 判断是否为完全二叉树
// 采用C++语法
bool isCompleteTree(TreeNode* root) 
{// 空树直接返回trueif (root == nullptr) {return true;}queue<TreeNode*> q;q.push(root);bool foundNull = false; // 判断while (!q.empty()) {TreeNode* front = q.front();q.pop();if (front == nullptr){foundNull = true;} else {if (foundNull) {return false;}q.push(front->left);q.pushk(front->right);}}return true;
}