西安网站网络营销,上海优化排名公司,软件定制开发系统,怎么样做短视频大家好#xff0c;我是小卡皮巴拉 文章目录
目录
引言
一.堆排序
1.1 版本一
核心概念
堆排序过程
1.2 版本二
堆排序函数 HeapSort
向下调整算法 AdjustDown
向上调整算法 AdjustUp
二.链式二叉树
2.1 前中后序遍历
链式二叉树的结构
创建链式二叉树
前序遍历… 大家好我是小卡皮巴拉 文章目录
目录
引言
一.堆排序
1.1 版本一
核心概念
堆排序过程
1.2 版本二
堆排序函数 HeapSort
向下调整算法 AdjustDown
向上调整算法 AdjustUp
二.链式二叉树
2.1 前中后序遍历
链式二叉树的结构
创建链式二叉树
前序遍历
中序遍历
后序遍历
2.2 链式二叉树的常见操作
二叉树的结点个数
二叉树叶子结点的个数
二叉树第k层结点的个数
求二叉树的高度/深度
二叉树查找值为x的结点
2.3 层序遍历
使用层序遍历检验是否为完全二叉树
兄弟们共勉 每篇前言 博客主页小卡皮巴拉 咱的口号小比特大梦想 作者请求由于博主水平有限难免会有错误和不准之处我也非常渴望知道这些错误恳请大佬们批评斧正。 引言
在数据结构与算法的广阔天地中堆排序与链式二叉树无疑是两颗璀璨的明珠。它们各自以其独特的魅力和广泛的应用场景在数据处理和算法优化中发挥着举足轻重的作用。
堆排序作为一种基于堆数据结构的比较排序算法以其高效的排序速度和稳定的性能表现成为了众多排序算法中的佼佼者。它利用堆的性质通过一系列精心设计的操作将无序的数据逐步转化为有序从而实现了数据的快速排序。
而链式二叉树则以其灵活的节点连接方式和高效的查找性能成为了数据结构中不可或缺的一部分。它通过将数据元素组织成二叉树的形式利用节点的指针域实现数据的动态存储和访问为数据的查找、插入和删除等操作提供了极大的便利。
今天我们将一起踏上一段探索之旅深入剖析堆排序的算法实现与链式二叉树的构建细节。从堆的构建、调整与排序过程到链式二叉树的节点定义、插入与遍历操作我们将一步步揭开这两大数据结构的神秘面纱带你领略它们背后的智慧与魅力。
一.堆排序
1.1 版本一
版本一基于已有数组建堆、取堆顶元素完成排序版本
void HeapSort(int* arr,int n)
{HP hp;HPInit(hp);//调用push将数组中的数据建堆for (int i 0; i n; i){HPPush(hp, arr[i]);}int i 0;while (!HPEmpty(hp)){arr[i] HPTop(hp);HPPop(hp);}HPDesTroy(hp);
} 核心概念 堆一种特殊的完全二叉树用于实现堆排序。这里我们假设使用最大堆。 空间复杂度O(N)因为使用了额外的堆数据结构。 堆排序过程 构建堆 将数组a中的元素逐个添加到堆hp中。 注意传统堆排序直接在输入数组上构建堆这里为了教学目的使用了额外的堆结构。 排序 当堆不为空时重复以下步骤 取出堆顶元素最大值将其放到数组a的当前位置。 从堆中移除堆顶元素。 这个过程会持续到堆为空此时数组a将按降序排列。 清理 销毁堆hp释放任何动态分配的内存。 1.2 版本二
数组建堆首尾交换交换后的堆尾数据从堆中删掉将堆顶数据向下调整选出次大的数据 堆排序函数 HeapSort 函数定义void HeapSort(int* arr, int n) arr指向待排序数组的指针。 n数组的长度。 建堆过程 循环从最后一个非叶子节点开始(n - 1 - 1) / 2逐步向上至根节点i 0对每个节点调用AdjustDown以确保以该节点为根的子树满足堆性质。 注释中提到的向上调整算法AdjustUp被注释掉了但其实用向上调整算法也是能够建堆的但向下调整更为高效。 排序过程 如果要进行升序排序需要构建最大堆大堆如果要进行降序排序则需要构建最小堆小堆。 通过交换堆顶当前最大值与数组末尾元素并减小堆的大小end--然后调用AdjustDown来维护堆的性质从而实现排序。 这个过程重复进行直到堆的大小减为1此时数组已排序完成。 //堆排序
void HeapSort(int* arr, int n)
{//根据给定的arr来进行建堆//childn-1 parent:(n-1-1)/2//向下调整算法建堆for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(arr, i, n);}//向上调整算法建堆/*for (int i 0; i n; i){AdjustUp(arr, i);}*///堆排序//排升序——建大堆//排降序——建小堆//建小堆大堆时主要影响因素在向下调整算法中//1.左孩子和右孩子的比较//2.孩子和父亲的比较//如果要从构造小堆改为构造大堆两个判断条件的都要取反int end n - 1;while (end 0){Swap(arr[0], arr[end]);AdjustDown(arr, 0, end);end--;}
} 向下调整算法 AdjustDown 函数定义void AdjustDown(HPDataType* arr, int parent, int n) arr指向堆数组的指针这里HPDataType是int。 parent当前需要调整的父节点索引。 n堆的大小即当前堆中元素的数量。 调整过程 计算左孩子节点的索引child parent * 2 1。 在while循环中首先检查是否存在右孩子并且右孩子的值是否小于左孩子的值。如果是则更新child为右孩子的索引。 接着比较父节点与孩子节点的值。如果父节点的值大于孩子节点的值对于最大堆而言则交换它们并继续向下调整更新parent和child。 如果父节点的值不大于孩子节点的值则跳出循环因为当前子树已经满足堆性质。 //向下调整算法
void AdjustDown(HPDataType* arr, int parent,int n)
{int child parent * 2 1;while (child n){//先找最小的孩子if (child 1 n arr[child] arr[child 1]){child;}//parent和child比较if (arr[child] arr[parent]){Swap(arr[child], arr[parent]);parent child;child parent * 2 1;}else{break;}}
} 向上调整算法 AdjustUp 函数定义void AdjustUp(HPDataType* arr, int child) arr指向堆数组的指针这里HPDataType是int类型表示堆中存储的是整数。 child当前需要向上调整的节点的索引也称为“孩子”节点。 调整过程 初始化父节点索引 根据孩子节点索引child计算出父节点索引parent (child - 1) / 2。 循环调整 当child大于0并且孩子节点的值大于父节点的值时对于最大堆 交换孩子节点和父节点的值。 更新child为当前父节点的索引。 重新计算新的父节点索引。 终止条件 当child不大于0或者孩子节点的值不大于新的父节点的值时停止调整。 //向上调整算法
void AdjustUp(HPDataType* arr, int child)
{int parent (child - 1) / 2;while (child 0){// 大堆// 小堆 if (arr[child] arr[parent]){Swap(arr[child], arr[parent]);child parent;parent (child - 1) / 2;}else {break;}}
} 注意事项 注释中提到的向上调整算法AdjustUp函数没有使用在堆排序中它通常用于在插入新元素后维护堆的性质但是此处也是可以使用向上调整算法来建堆的在这个特定的实现中由于是从一个无序数组开始构建堆所以使用向下调整算法AdjustDown更为高效。 堆排序是一种原地排序算法因为它只需要一个额外的常数空间来存储临时变量如child、parent等而不需要额外的数组来存储数据。 建小堆大堆时主要影响因素在向下调整算法中 1.左孩子和右孩子的比较 2.孩子和父亲的比较 如果要从构造小堆改为构造大堆两个判断条件的都要取反
二.链式二叉树
2.1 前中后序遍历
二叉树的操作离不开树的遍历我们先来看看二叉树的遍历有哪些方式
遍历规则
按照规则二叉树的遍历有前序/中序/后序的递归结构遍历
1前序遍历(PreorderTraversal亦称先序遍历)访问根结点的操作发生在遍历其左右子树之前 访 问顺序为根结点、左子树、右子树
2中序遍历(InorderTraversal)访问根结点的操作发生在遍历其左右子树之中间 访问顺序为左子树、根结点、右子树
3后序遍历(PostorderTraversal)访问根结点的操作发生在遍历其左右子树之后 访问顺序为左子树、右子树、根结点
图解遍历
以前序遍历为例
函数递归栈帧图
前序遍历结果1 2 3 4 5 6
中序遍历结果3 2 1 5 4 6
后序遍历结果3 1 5 6 4 1
后面会进行代码的实现 链式二叉树的结构 结构体名称BTNode 目的定义二叉树节点。 字段 BTDataType data; 类型字符char的别名BTDataType描述节点值。BTNode* left; 类型指向BTNode的指针描述左孩子节点。BTNode* right; 类型指向BTNode的指针描述右孩子节点。 实现代码 typedef char BTDataType;
//二叉树结点结构的定义
typedef struct BinaryTreeNode
{BTDataType data;//当前结点值域struct BinaryTreeNode* left;//指向当前结点左孩⼦struct BinaryTreeNode* right;//指向当前结点右孩⼦
}BTNode; 创建链式二叉树 函数一申请新节点 函数名buyNode 参数 BTDataType x要存储在新节点中的值。 返回值 指向新创建的BTNode结构体的指针。 功能 分配内存以创建一个新的BTNode节点。检查内存分配是否成功如果失败则打印错误信息并退出程序。初始化新节点的值域为参数x。将新节点的左右孩子指针初始化为NULL。返回指向新节点的指针。 函数二手动构造二叉树 函数名CreateTree 参数无 返回值 指向二叉树根节点的指针。 功能 调用buyNode函数创建六个新节点分别存储字符A到F。设置这些节点之间的父子关系以构造一个特定的二叉树结构 A是根节点。B和C是A的左右孩子。D和E是B的左右孩子。F是C的左孩子。返回指向根节点A的指针。 实现代码 //申请新结点
BTNode* buyNode(BTDataType x)
{BTNode* node (BTNode*)malloc(sizeof(BTNode));if (node NULL){perror(malloc fail!);exit(1);}node-data x;node-left node-right NULL;return node;
}
//手动构造一颗二叉树
BTNode* CreateTree()
{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;nodeB-right nodeE;nodeC-left nodeF;return nodeA;
} 前序遍历 函数名PreOrder 参数 BTNode* root指向二叉树根节点的指针。 返回值无 功能 实现二叉树的前序遍历算法。前序遍历的顺序是首先访问根节点然后递归地前序遍历左子树最后递归地前序遍历右子树。 实现细节 递归终止条件如果当前节点root为空则打印NULL 并返回。这个条件确保了递归能够正确终止。然而在标准的前序遍历实现中通常不会打印NULL因为空节点不产生输出。这里的打印是为了调试或满足特定要求。 访问根节点打印当前节点的值root-data。 递归遍历左子树调用PreOrder函数传入当前节点的左孩子root-left作为参数。 递归遍历右子树调用PreOrder函数传入当前节点的右孩子root-right作为参数。 实现代码 //前序遍历——根左右
void PreOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}printf(%c , root-data);PreOrder(root-left);PreOrder(root-right);
} 结合上述创建的链式二叉树其运行结果为 中序遍历 函数名InOrder 参数 BTNode* root指向二叉树根节点的指针。 返回值无 功能 实现二叉树的中序遍历算法。中序遍历的顺序是首先递归地中序遍历左子树然后访问根节点最后递归地中序遍历右子树。 实现细节 递归终止条件如果当前节点root为空则打印NULL 这里的打印是为了便于调试。 递归遍历左子树调用InOrder函数传入当前节点的左孩子root-left作为参数。 访问根节点在左子树遍历完成后打印当前节点的值root-data。 递归遍历右子树调用InOrder函数传入当前节点的右孩子root-right作为参数。 实现代码 //中序遍历——左根右
void InOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}InOrder(root-left);printf(%c , root-data);InOrder(root-right);
} 打印结果 后序遍历 函数名PostOrder 参数 BTNode* root指向二叉树根节点的指针。 返回值无 功能 实现二叉树的后序遍历算法。按照“左子树-右子树-根节点”的顺序访问节点。 实现细节 递归终止条件如果当前节点root为空则按照代码逻辑会打印NULL 。 递归遍历左子树调用PostOrder函数传入当前节点的左孩子root-left作为参数进行递归后序遍历。 递归遍历右子树同样地调用PostOrder函数传入当前节点的右孩子root-right作为参数进行递归后序遍历。 访问根节点在左右子树都被遍历之后打印当前节点的值root-data。 实现代码 //后序遍历——左右根
void PostOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}PostOrder(root-left);PostOrder(root-right);printf(%c, root-data);
}打印结果: 2.2 链式二叉树的常见操作 二叉树的结点个数 函数名BinaryTreeSize 参数 BTNode* root指向二叉树根节点的指针。 返回值 int返回二叉树的节点总数。 功能 实现计算二叉树节点总数的算法。递归地计算左子树和右子树的节点数并将它们与根节点相加得到总节点数。 实现细节 递归终止条件如果当前节点root为空则根据二叉树的定义空树没有节点返回0。 递归计算左子树节点数调用BinaryTreeSize函数传入当前节点的左孩子root-left作为参数递归地计算左子树的节点总数。 递归计算右子树节点数同样地调用BinaryTreeSize函数传入当前节点的右孩子root-right作为参数递归地计算右子树的节点总数。 计算总节点数将左子树的节点数、右子树的节点数与根节点1个相加得到当前二叉树的总节点数。 实现代码 //二叉树的结点个数
int BinaryTreeSize(BTNode* root)
{if (root NULL){return 0;}//递归//每一颗二叉树的结点个数都可以表示为//根结点1左子树结点个数右子树结点个数return 1 BinaryTreeSize(root-left) BinaryTreeSize(root-right);
} 二叉树叶子结点的个数 函数名BinaryTreeLeafSize 参数 BTNode* root指向二叉树根节点的指针。 返回值 int返回二叉树中叶子节点的总数。 功能 实现计算二叉树叶子节点总数的算法。递归地检查每个节点是否为叶子节点并累加叶子节点的数量。 实现细节 递归终止条件如果当前节点root为空则根据二叉树的定义空树没有叶子节点返回0。 叶子节点判断如果当前节点的左孩子root-left和右孩子root-right都为空则当前节点是叶子节点返回1。 递归计算叶子节点数如果当前节点不是叶子节点则递归地调用BinaryTreeLeafSize函数分别传入当前节点的左孩子和右孩子作为参数计算左子树和右子树的叶子节点总数并将这两个数相加得到当前二叉树的叶子节点总数。 实现代码 //二叉树叶子结点的个数
int BinaryTreeLeafSize(BTNode* root)
{if (root NULL){return 0;}//递归//叶子结点左孩子和右孩子都为空if (root-left NULL root-right NULL){return 1;}//总数左子树叶子结点个数右子树叶子结点个数return BinaryTreeLeafSize(root-left) BinaryTreeLeafSize(root-right);
} 二叉树第k层结点的个数 函数名BinaryTreeLevelKSize 参数 BTNode* root指向二叉树根节点的指针。int k指定的层数从1开始计数。 返回值 int返回二叉树第k层节点的总数。 功能 实现计算二叉树第k层节点总数的算法。递归地遍历二叉树直到达到指定的层数然后累加该层的节点数。 实现细节 递归终止条件 如果当前节点root为空则根据二叉树的定义该层没有节点返回0。如果当前层数k等于1说明已经到达了根节点所在的层根节点位于第1层因此该层有1个节点返回1。递归计算第k层节点数 如果当前节点不是空节点且当前层数k大于1则递归地调用BinaryTreeLevelKSize函数分别传入当前节点的左孩子和右孩子作为新的根节点并将层数k减1因为向下递归一层计算左子树和右子树在第k-1层的节点总数。将左子树和右子树在第k-1层的节点数相加得到当前二叉树在第k层的节点总数。 注意 这里的递归逻辑有一点需要注意即当我们想要计算第k层的节点数时实际上是递归地去计算左子树和右子树在第k-1层的节点数。这是因为当我们从根节点开始递归时根节点是第1层它的子节点左孩子和右孩子位于第2层依此类推。 实现代码 //二叉树第k层结点的个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root NULL){return 0;}if (k 1){return 1; // 根节点所在层只有1个节点}//递归//总数左子树第k-1层结点的个数右子树第k-1层结点的个数return BinaryTreeLevelKSize(root-left, k - 1) BinaryTreeLevelKSize(root-right, k - 1);
} 求二叉树的高度/深度 函数名BinaryTreeDepth 参数 BTNode* root指向二叉树根节点的指针。 返回值 int返回二叉树的高度或深度即从根节点到最远叶子节点的最长路径上的节点数。 功能 实现计算二叉树高度的算法。递归地计算左子树和右子树的高度并返回其中较大的高度值加上1根节点的高度。 实现细节 递归终止条件如果当前节点root为空则根据二叉树的定义空树的高度为0。 递归计算子树高度分别调用BinaryTreeDepth函数传入当前节点的左孩子root-left和右孩子root-right作为参数递归地计算左子树和右子树的高度。 计算总高度将左子树的高度leftDep和右子树的高度rightDep进行比较取其中较大的值然后加上1根节点的高度得到当前二叉树的总高度。 实现代码 //求二叉树的高度/深度
int BinaryTreeDepth(BTNode* root)
{if (root NULL){return 0;}//递归计算左子树和右子树的高度int leftDep BinaryTreeDepth(root-left);int rightDep BinaryTreeDepth(root-right);//返回当前树的高度根节点的高度1加上左右子树中较大的高度return 1 (leftDep rightDep ? leftDep : rightDep);
} 二叉树查找值为x的结点 函数名BinaryTreeFind 参数 BTNode* root指向二叉树根节点的指针。BTDataType x要查找的目标值其类型应与二叉树节点的数据类型相匹配。 返回值 BTNode*返回指向找到的值为x的节点的指针如果未找到则返回NULL。 功能 实现在二叉树中查找值为x的节点的算法。递归地遍历二叉树直到找到值为x的节点或遍历完整个树。 实现细节 递归终止条件如果当前节点root为空则根据二叉树的定义该节点下不存在任何子节点因此返回NULL表示未找到。 查找目标值如果当前节点的值root-data等于目标值x则找到了目标节点返回当前节点的指针。 递归查找 首先递归地调用BinaryTreeFind函数传入当前节点的左孩子root-left作为新的根节点和相同的目标值x尝试在左子树中查找目标节点。如果左子树中找到了目标节点即leftFind不为NULL则返回该节点的指针。如果左子树中没有找到目标节点则继续递归地调用BinaryTreeFind函数传入当前节点的右孩子root-right作为新的根节点和相同的目标值x尝试在右子树中查找目标节点。如果右子树中找到了目标节点即rightFind不为NULL则返回该节点的指针。 未找到目标值如果左子树和右子树中都没有找到目标节点则返回NULL表示在整个二叉树中未找到值为x的节点。 实现代码 BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{//先遍历左子树//找到了直接返回//没有找到再去遍历右子树if (root NULL){return NULL;}if (root-data x){return root;}BTNode* leftFind BinaryTreeFind(root-left, x);if (leftFind){return leftFind;}BTNode* rightFind BinaryTreeFind(root-right, x);if (rightFind){return rightFind;}return NULL;
} 2.3 层序遍历
除了先序遍历、中序遍历、后序遍历外还可以对二叉树进行层序遍历。设二叉树的根结点所在层数为1层序遍历就是从所在二叉树的根结点出发首先访问第1层的树根结点然后从左到右访问第2层上的结点接着是第3层的结点以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历实现层序遍历需要额外借助数据结构队列 函数名LevelOrder 参数 BTNode* root指向二叉树根节点的指针。 功能 实现二叉树的层序遍历广度优先遍历通过队列数据结构辅助完成。 实现细节 初始化队列 创建一个Queue类型的变量q。调用QueueInit(q)函数初始化队列q使其处于可用状态。根节点入队 调用QueuePush(q, root)函数将二叉树的根节点root添加到队列q的末尾。遍历队列 使用while循环遍历队列q条件是队列不为空!QueueEmpty(q)。在循环体内首先调用QueueFront(q)函数获取队列头部的节点指针并将其赋值给BTNode* top。这里需要注意的是QueueFront只是获取队列头部的节点指针并不会将该节点从队列中移除。紧接着调用QueuePop(q)函数从队列中移除刚才通过QueueFront获取的节点即top指向的节点。使用printf(%c, top-data);语句打印当前节点即top指向的节点的值。这里假设节点值的数据类型为字符因此使用%c格式说明符。孩子节点入队 检查当前节点top的左孩子是否存在top-left。如果存在则调用QueuePush(q, top-left);将其添加到队列q的末尾。同样地检查当前节点的右孩子是否存在top-right。如果存在则调用QueuePush(q, top-right);将其添加到队列q的末尾。销毁队列 遍历完成后调用QueueDestroy(q)函数销毁队列q并释放其占用的资源。 代码实现 //层序遍历
void LevelOrder(BTNode* root)
{//借助数据结构——队列Queue q;QueueInit(q);QueuePush(q, root);while (!QueueEmpty(q)){//取队头出队头BTNode* top QueueFront(q);QueuePop(q);printf(%c, top-data);//将队头左右孩子入队列(不为空)if (top-left){QueuePush(q, top-left);}if (top-right){QueuePush(q, top-right);}}QueueDestroy(q);
} 上述是完整的解析其中用队列实现层序遍历的核心思路如下 初始化队列 创建一个空队列用于存储待访问的节点。根节点入队 将二叉树的根节点加入队列。循环遍历 当队列不为空时执行以下步骤 a. 从队列头部取出一个节点访问该节点例如打印其值。 b. 如果该节点有左孩子将左孩子加入队列。 c. 如果该节点有右孩子将右孩子加入队列。结束 当队列为空时遍历结束所有节点都已按层次顺序访问过。 学习了层序遍历下面我们用层序遍历来检验二叉树是否为完全二叉树 使用层序遍历检验是否为完全二叉树 函数名BinaryTreeComplete 参数 BTNode* root指向二叉树根节点的指针。 返回值 bool如果二叉树是完全二叉树则返回true否则返回false。 功能 该函数通过层序遍历的方式验证给定的二叉树是否为完全二叉树。 实现细节 空树处理 首先检查根节点root是否为NULL。如果是根据完全二叉树的定义有时空树也被认为是完全二叉树函数返回true。队列初始化 创建一个名为q的队列并调用QueueInit(q)函数对其进行初始化。根节点入队 将二叉树的根节点root通过QueuePush(q, root)函数加入队列q。遍历与检查 使用while循环遍历队列q条件是队列不为空!QueueEmpty(q)。在循环内部首先通过QueueFront(q)函数获取队列头部的节点指针并将其赋值给BTNode* node。随后调用QueuePop(q)函数将node节点从队列中移除。使用一个布尔变量met_null来跟踪是否遇到了空节点。如果在遍历过程中遇到了空节点并且之后还遇到了非空节点则树不是完全二叉树。空节点与非空节点处理 如果node为空则将met_null设置为true表示之后应该只遇到空节点。如果node不为空则检查met_null是否为true。如果是说明在之前已经遇到了空节点但当前节点却是非空的因此树不是完全二叉树。在这种情况下函数会销毁队列并返回false。如果node不为空且met_null为false则将node的左右孩子如果存在加入队列。队列销毁与结果返回 如果遍历完成后没有违反完全二叉树的性质则函数销毁队列q并返回true表示树是完全二叉树。 代码实现 #include stdbool.h// 假设已经定义了BTNode结构体、Queue结构体以及相关的队列操作函数bool BinaryTreeComplete(BTNode* root) {if (root NULL) {// 空树被认为是完全二叉树根据定义可有所不同这里假设是return true;}Queue q;QueueInit(q);QueuePush(q, root);bool met_null false; // 标记是否遇到了空节点while (!QueueEmpty(q)) {BTNode* node QueueFront(q);QueuePop(q);// 如果已经遇到了空节点但当前节点不是空则不是完全二叉树if (met_null node ! NULL) {QueueDestroy(q);return false;}// 如果当前节点是空则设置标记为true表示之后应该只遇到空节点if (node NULL) {met_null true;} else {// 否则将当前节点的左右孩子加入队列QueuePush(q, node-left);QueuePush(q, node-right);}}QueueDestroy(q);return true;
} 简化提炼思路如下 思路 初始化 使用一个队列来进行层序遍历。将根节点加入队列。初始化一个布尔变量 met_null 为 false用于标记是否遇到了空节点。层序遍历 遍历队列直到队列为空。在每次循环中从队列头部取出一个节点。如果 met_null 为 true意味着之前已经遇到了空节点但当前节点不是空节点则树不是完全二叉树返回 false。如果当前节点是空节点则将 met_null 设置为 true。如果当前节点不是空节点则将其左右孩子如果存在加入队列。结束条件 如果遍历结束后没有违反完全二叉树的性质即没有在遇到空节点后再遇到非空节点则树是完全二叉树返回 true。 关键点 一旦在层序遍历中遇到了空节点之后的所有节点如果存在都应该是空节点否则树就不是完全二叉树。使用队列来保持层序遍历的顺序。使用布尔变量 met_null 来跟踪是否遇到了空节点。 兄弟们共勉 码字不易求个三连 抱拳了兄弟们
