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)
{
// 空树直接返回true
if (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;
}
当出现一个空的时候，便不能再出现空，且空不会再带入左右节点，也不能带入
总结
下篇我们来介绍一下二叉树的一些基本操作~
原文地址：https://blog.csdn.net/2301_80392199/article/details/143031603
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！