链式二叉树的概念：
链式二叉树解决的是非完全二叉树解决不了的问题
什么意思呢，简单的说就是，链式二叉树
可以是下面三种二叉树
但是非链式二叉树只能是前两种
链式二叉树的存储
节点结构：首先定义一个结构体或类来表示二叉树的节点。每个节点通常包含三个部分：
- 存储数据的成员变量（例如，
_data）。- 指向其左子节点的指针（例如，
_left）。- 指向其右子节点的指针（例如，
_right）。链式二叉树的存储方式提供了很高的灵活性，可以轻松地添加和删除节点，同时也使得树结构的实现更加直观和易于操作。
前序/中序/后序遍历
讲解链式二叉树之前我们需要先了解一下，前序/中序/后序，因为在初阶数据结构里，链式二叉树我们是用递归的方式来实现的，非递归的方式，在后续篇章会进行讲解。
这里我们上图，假设是这一张图
前序遍历
前序遍历的顺序是：首先访问根节点，然后递归地进行左子树的前序遍历，最后递归地进行右子树的前序遍历。
遍历顺序：根-左-右
步骤：
- 访问当前节点。
- 遍历左子树。
- 遍历右子树。
示例： 假设有如下的二叉树：
关于前序遍历，我们需要把空节点也看出来
如图
所以根据遍历顺便，我们应该是
1 2 3 NULL NULL NULL 4 5 NULL NULL 6 NULL NULL
中序遍历
中序遍历的顺序是：首先递归地进行左子树的中序遍历，然后访问根节点，最后递归地进行右子树的中序遍历。
遍历顺序：左-根-右
步骤：
- 遍历左子树。
- 访问当前节点。
- 遍历右子树。
正确的是
后序遍历
后序遍历的顺序是：首先递归地进行左子树的后序遍历，然后递归地进行右子树的后序遍历，最后访问根节点。
遍历顺序：左-右-根
步骤：
- 遍历左子树。
- 遍历右子树。
- 访问当前节点。
正确的是
总结
链式二叉树的实现
创建文件
定义链式二叉树结构
typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType _data; struct BinaryTreeNode* _left; struct BinaryTreeNode* _right; }BTNode;解释：
typedef int BTDataType;这行代码使用typedef关键字定义了一个新的别名BTDataType，它是int类型的别名。这意味着在代码中，你可以使用BTDataType作为int类型数据的一个更有意义的别名。
typedef struct BinaryTreeNode这行代码开始定义一个名为BinaryTreeNode的新结构体类型。struct BinaryTreeNode是结构体的名称，它将用于表示二叉树中的节点。
BTDataType _data; struct BinaryTreeNode* _left; struct BinaryTreeNode* _right; }这个大括号内的代码定义了BinaryTreeNode结构体的具体内容：
BTDataType _data;定义了一个名为_data的成员变量，它用于存储节点中的数据。由于使用了之前定义的BTDataType，所以这个成员变量是int类型的。struct BinaryTreeNode* _left;定义了一个名为_left的成员变量，它是一个指向BinaryTreeNode类型的指针，用于指向当前节点的左子节点。struct BinaryTreeNode* _right;定义了一个名为_right的成员变量，它也是一个指向BinaryTreeNode类型的指针，用于指向当前节点的右子节点。
BTNode;这行代码为BinaryTreeNode结构体定义了一个易记的别名BTNode。这样，在代码中就可以使用BTNode来声明二叉树的节点。总结来说，这段代码定义了一个用于表示链式二叉树节点的结构体
BTNode，其中包含一个整型数据_data和两个指向相同结构体类型的指针_left和_right，分别用于存储节点的数据和链接到左右子节点。通过这种定义，可以方便地创建和管理二叉树数据结构。
二叉树的初始化
//二叉树的初始化 BTNode* BuyNode(BTDataType x) { BTNode* newnode = (BTNode*)malloc(sizeof(BTNode)); if (newnode == NULL) { perror("BinaryTreeInit:newnode:"); exit(1); } newnode->_data = x; newnode->_left = NULL; newnode->_right = NULL; return newnode; }解释：
BTNode* BuyNode(BTDataType x)
- 这是函数的声明行，定义了一个名为
BuyNode的函数，它接收一个类型为BTDataType（之前定义的int类型别名）的参数x，并返回一个指向BTNode类型的指针。
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
- 这行代码使用
malloc函数为新的二叉树节点分配内存。sizeof(BTNode)计算BTNode类型的大小，确保分配足够的内存。分配成功后，newnode指针将指向这块新分配的内存。
if (newnode == NULL)
- 这行代码检查
malloc是否成功分配了内存。如果newnode为NULL，表示内存分配失败。
perror("BinaryTreeInit:newnode:");
- 如果内存分配失败，使用
perror函数输出错误信息到标准错误。"BinaryTreeInit:newnode:"是自定义的错误前缀，后跟系统定义的错误信息。
exit(1);
- 紧接着，使用
exit函数以状态码1退出程序。状态码1通常表示程序因错误而终止。
newnode->_data = x;
- 如果内存分配成功，这行代码将参数
x的值赋给新节点的_data成员变量，从而初始化节点存储的数据。
newnode->_left = NULL;
- 这行代码将新节点的
_left指针设置为NULL，表示当前没有左子节点。
newnode->_right = NULL;
- 类似地，这行代码将新节点的
_right指针设置为NULL，表示当前没有右子节点。
return newnode;
- 最后，函数返回指向新创建并初始化的
BTNode节点的指针。总结来说，
BuyNode函数负责创建一个新的二叉树节点，初始化其数据和子节点指针，如果内存分配失败，则输出错误信息并终止程序。这个函数是构建二叉树时用于生成节点的基本工具。这里的关键点是认识到 ，左右节点的存在
二叉树的销毁
这里就采取了递归，开始上难度了，这里我先不做讲解，模拟创建二叉树之后我们进行讲解递归
// 二叉树销毁 void BinaryTreeDestory(BTNode* root) { if (root == NULL) { return; } BinaryTreeDestory(root->_left); BinaryTreeDestory(root->_right); free(root); }解释：
void BinaryTreeDestory(BTNode* root)
- 这是函数的声明行，定义了一个名为
BinaryTreeDestory的函数，它接收一个指向BTNode类型的指针root作为参数。该函数没有返回值（void类型）。
if (root == NULL)
- 这行代码检查传入的
root指针是否为NULL。如果是NULL，表示二叉树为空或已经被销毁，因此函数直接返回。
BinaryTreeDestory(root->_left);
- 如果
root不是NULL，这行代码首先递归调用BinaryTreeDestory函数，传入当前节点的左子节点root->_left作为参数。这样做会先销毁左子树。
BinaryTreeDestory(root->_right);
- 接着，这行代码递归调用
BinaryTreeDestory函数，传入当前节点的右子节点root->_right作为参数。这会销毁右子树。
free(root);
- 在左子树和右子树都被销毁之后，这行代码使用
free函数释放当前节点root所占用的内存。总结来说，
BinaryTreeDestory函数通过递归的方式，先销毁二叉树的左子树和右子树，然后释放根节点的内存。这种销毁方式确保了二叉树中的所有节点都会被释放，避免了内存泄漏。需要注意的是，在使用这种销毁方式时，确保在销毁二叉树后不再使用任何指向该树的指针，因为整个树的内存已经被释放。
模拟简易链式二叉树
//构建二叉树 void teer() { BTNode* node1 = BuyNode(1); BTNode* node2 = BuyNode(2); BTNode* node3 = BuyNode(3); BTNode* node4 = BuyNode(4); BTNode* node5 = BuyNode(5); BTNode* node6 = BuyNode(6); //BTNode* node7 = BuyNode(7); node1->_left = node2; node2->_left = node3; node1->_right = node4; node4->_left = node5; node4->_right = node6; //node2->_right = node7; } int main() { //构建二叉树 teer(); return 0; }这里我们模拟实现一个二叉树
就是这样
前序遍历实现
// 二叉树前序遍历 void BinaryTreePrevOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } printf("%d ", root->_data); BinaryTreePrevOrder(root->_left); BinaryTreePrevOrder(root->_right); }解释：
void BinaryTreePrevOrder(BTNode* root)
- 这是函数的声明行，定义了一个名为
BinaryTreePrevOrder的函数，它接收一个指向BTNode类型的指针root作为参数。该函数没有返回值（void类型）。
if (root == NULL)
- 这行代码检查传入的
root指针是否为NULL。如果是NULL，表示当前节点为空，不需要遍历。
printf("NULL ");
- 如果当前节点为空，打印字符串
"NULL "到标准输出。这是一种表示空节点的常见做法，但在实际应用中，通常会省略这一步，或者用其他方式处理空节点。
printf("%d ", root->_data);
- 如果当前节点不为空，这行代码会打印当前节点的
_data成员变量的值。%d是格式化输出的占位符，表示后面跟着的参数是一个整数。
BinaryTreePrevOrder(root->_left);
- 这行代码递归调用
BinaryTreePrevOrder函数，传入当前节点的左子节点root->_left作为参数。这将执行左子树的前序遍历。
BinaryTreePrevOrder(root->_right);
- 最后，这行代码递归调用
BinaryTreePrevOrder函数，传入当前节点的右子节点root->_right作为参数。这将执行右子树的前序遍历。总结来说，
BinaryTreePrevOrder函数通过递归的方式实现了二叉树的前序遍历。它首先打印当前节点的值，然后递归地遍历左子树，最后递归地遍历右子树。这种遍历方式在树的遍历、搜索、复制等操作中非常有用。图解：
中序遍历实现
// 二叉树中序遍历 void BinaryTreeInOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } BinaryTreeInOrder(root->_left); printf("%d ", root->_data); BinaryTreeInOrder(root->_right); }解释：
void BinaryTreeInOrder(BTNode* root)
- 这是函数的声明行，定义了一个名为
BinaryTreeInOrder的函数，它接收一个指向BTNode类型的指针root作为参数。该函数没有返回值（void类型）。
if (root == NULL)
- 这行代码检查传入的
root指针是否为NULL。如果是NULL，表示当前节点为空，不需要遍历。
printf("NULL ");
- 如果当前节点为空，打印字符串
"NULL "到标准输出。这通常用于表示空节点，但在实际的中序遍历中，通常会忽略空节点而不是打印它们。
BinaryTreeInOrder(root->_left);
- 这行代码递归调用
BinaryTreeInOrder函数，传入当前节点的左子节点root->_left作为参数。这将执行左子树的中序遍历。
printf("%d ", root->_data);
- 在左子树遍历之后，这行代码打印当前节点的
_data成员变量的值。因为在左子树遍历之后访问根节点，所以对于二叉搜索树来说，这会保证按升序打印节点值。
BinaryTreeInOrder(root->_right);
- 最后，这行代码递归调用
BinaryTreeInOrder函数，传入当前节点的右子节点root->_right作为参数。这将执行右子树的中序遍历。
后序遍历实现
// 二叉树后序遍历 void BinaryTreePostOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } BinaryTreePostOrder(root->_left); BinaryTreePostOrder(root->_right); printf("%d ", root->_data); }解释：
void BinaryTreePostOrder(BTNode* root)
- 这是函数的声明行，定义了一个名为
BinaryTreePostOrder的函数，它接收一个指向BTNode类型的指针root作为参数。该函数没有返回值（void类型）。
if (root == NULL)
- 这行代码检查传入的
root指针是否为NULL。如果是NULL，表示当前节点为空，不需要遍历。
printf("NULL ");
- 如果当前节点为空，打印字符串
"NULL "到标准输出。这通常用于表示空节点，但在实际的后序遍历中，通常会忽略空节点而不是打印它们。
BinaryTreePostOrder(root->_left);
- 这行代码递归调用
BinaryTreePostOrder函数，传入当前节点的左子节点root->_left作为参数。这将执行左子树的后序遍历。
BinaryTreePostOrder(root->_right);
- 在左子树遍历之后，这行代码递归调用
BinaryTreePostOrder函数，传入当前节点的右子节点root->_right作为参数。这将执行右子树的后序遍历。
printf("%d ", root->_data);
- 在左子树和右子树都遍历之后，这行代码打印当前节点的
_data成员变量的值。因为这是在访问完左右子树之后的操作，所以它是后序遍历的一部分。
二叉树节点个数
什么是节点个数，也就是，全部节点个数
// 二叉树节点个数 int BinaryTreeSize(BTNode* root) { if (root == NULL) { return 0; } return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1; }解释：
int BinaryTreeSize(BTNode* root)
- 这是函数的声明行，定义了一个名为
BinaryTreeSize的函数，它接收一个指向BTNode类型的指针root作为参数。函数返回一个整数值，表示树中的节点总数。
if (root == NULL)
- 这行代码检查传入的
root指针是否为NULL。如果是NULL，表示当前节点为空，不计入节点总数。
return 0;
- 如果当前节点为空，函数返回
0。这是递归的基本情况，表示空树的节点数为0。
return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
- 如果当前节点不为空，这行代码递归调用自身两次：一次计算左子树的节点数
BinaryTreeSize(root->_left)，一次计算右子树的节点数BinaryTreeSize(root->_right)。然后将这两个调用的结果相加，并加上1来表示当前节点本身。这样，你就得到了整棵树的节点总数。图解
二叉树叶子节点个数
什么是叶子结点个数
也就是：
// 二叉树叶子节点个数 int BinaryTreeLeafSize(BTNode* root) { if (root == NULL) return 0; if (BinaryTreeLeafSize(root->_left) == 0 && BinaryTreeLeafSize(root->_right) == 0) return 1; return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right); }解释：
int BinaryTreeLeafSize(BTNode* root)
- 这是函数的声明行，定义了一个名为
BinaryTreeLeafSize的函数，接收一个指向BTNode类型的指针root作为参数。函数返回一个整数值，表示树中叶子节点的总数。
if (root == NULL)
- 这行代码检查传入的
root指针是否为NULL。如果是NULL，表示当前节点为空，不计入叶子节点的总数。
return 0;
- 如果当前节点为空，函数返回
0。这是递归的基本情况之一，表示空树的叶子节点数为0。
if (BinaryTreeLeafSize(root->_left) == 0 && BinaryTreeLeafSize(root->_right) == 0)
- 这行代码是一个条件语句，用于检查当前节点的左子节点和右子节点是否都为空。如果两者都为空，那么当前节点就是一个叶子节点。
return 1;
- 如果当前节点是叶子节点，即它的左右子节点都为空，那么返回
1，表示叶子节点数为1。
return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
- 如果当前节点不是叶子节点，这行代码递归调用自身两次：一次计算左子树的叶子节点数
BinaryTreeLeafSize(root->_left)，一次计算右子树的叶子节点数BinaryTreeLeafSize(root->_right)。然后将这两个调用的结果相加，得到当前子树的叶子节点总数。总结来说，
BinaryTreeLeafSize函数通过递归的方式遍历二叉树，计算叶子节点的个数。它首先检查当前节点是否为空，如果不是空，再检查当前节点是否为叶子节点（左右子节点都为空），如果是叶子节点则计数1，否则递归地计算左右子树的叶子节点数并相加。这种方法可以正确地计算出任意二叉树的叶子节点总数。图解
二叉树高度
高度也就是二叉树的层数
// 二叉树高度 int BinaryTreeHeight(BTNode* root) { if (root == NULL) { return 0; } int heightleft = BinaryTreeHeight(root->_left); int heightright = BinaryTreeHeight(root->_right); return heightleft >= heightright ? heightleft + 1 : heightright + 1; }这里的关键是理解如何递归地计算左子树和右子树的高度。
int heightleft = BinaryTreeHeight(root->_left);
- 这行代码是对
BinaryTreeHeight函数的递归调用，目的是计算当前节点的左子树的高度。root->_left是对当前节点左子节点的引用，如果左子节点存在，就对它调用BinaryTreeHeight函数，否则返回0（如果左子节点为空）。
int heightright = BinaryTreeHeight(root->_right);
- 类似于上面的调用，这行代码计算当前节点的右子树的高度。
root->_right是对当前节点右子节点的引用，同样地，如果右子节点存在，就对它调用BinaryTreeHeight函数，否则返回0（如果右子节点为空）。这里的关键点在于
int heightleft = BinaryTreeHeight(root->_left);
int heightright = BinaryTreeHeight(root->_right);这两行代码是递归过程中的关键步骤，它们分别独立地计算左子树和右子树的高度。由于树的高度是递归定义的，即树的高度是其左子树和右子树高度的最大值加
1（当前节点），所以需要分别计算左右子树的高度。一旦得到
heightleft和heightright，函数就会决定：
- 如果
heightleft大于或等于heightright，则当前节点的左子树高度是决定整棵树高度的关键，因此返回heightleft + 1。- 如果
heightright大于heightleft，则右子树的高度决定了整棵树的高度，因此返回heightright + 1。这种递归方法确保了能够找到从根节点到任意叶子节点的最长路径，从而得到二叉树的准确高度。
否则会产生栈溢出的现象
下面有一题题解，我们会进行图解，因为一样，所以这里不进行图解，
先上图
二叉树查找值为x的节点
这里还是有点难度的
// 二叉树查找值为x的节点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root == NULL) return NULL; if (root->_data == x) return root; BTNode* ret1 = BinaryTreeFind(root->_left, x); if (ret1 != NULL) { return ret1; } BTNode* ret2 = BinaryTreeFind(root->_right, x); if (ret2 != NULL) { return ret2; } return NULL; }解释：
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
- 这是函数的声明行，定义了一个名为
BinaryTreeFind的函数。它接收两个参数：一个指向BTNode类型的指针root，表示二叉树的根节点；一个BTDataType类型的值x，表示要查找的值。函数返回一个指向BTNode类型的指针，如果找到匹配的节点，则返回该节点的地址；如果没有找到，则返回NULL。
if (root == NULL)
- 这行代码检查传入的
root指针是否为NULL。如果是NULL，表示当前节点为空，无法找到匹配的值，因此返回NULL。
if (root->_data == x)
- 如果当前节点不为空，这行代码比较当前节点的
_data成员变量与给定值x是否相等。
return root;
- 如果找到匹配的值，即当前节点的
_data等于x，则返回当前节点的指针。
BTNode* ret1 = BinaryTreeFind(root->_left, x);
- 如果当前节点的值不匹配，这行代码递归调用
BinaryTreeFind函数，搜索左子树。递归调用的结果（一个节点指针）被存储在ret1变量中。
if (ret1 != NULL)
- 接着，检查
ret1是否不为空。如果不为空，表示在左子树中找到了匹配的节点，因此返回ret1。
BTNode* ret2 = BinaryTreeFind(root->_right, x);
- 如果左子树中没有找到匹配的节点，这行代码递归调用
BinaryTreeFind函数，搜索右子树。递归调用的结果（一个节点指针）被存储在ret2变量中。
if (ret2 != NULL)
- 然后，检查
ret2是否不为空。如果不为空，表示在右子树中找到了匹配的节点，因此返回ret2。
return NULL;
- 如果在当前节点的左子树和右子树中都没有找到匹配的节点，则返回
NULL。图解
二叉树第k层节点个数
// 二叉树第k层节点个数 int BinaryTreeLevelKSize(BTNode* root, int k) { if (root == NULL) return 0; if (k == 1) return 1; return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1); }解释：
int BinaryTreeLevelKSize(BTNode* root, int k)
- 这是函数的声明行，定义了一个名为
BinaryTreeLevelKSize的函数。它接收两个参数：一个指向BTNode类型的指针root，表示当前的节点（可以是任意层的节点，包括根节点）；一个整型变量k，表示要查找的目标层级。函数返回一个整数值，表示在第k层上的节点总数。
if (root == NULL)
- 这行代码检查传入的
root指针是否为NULL。如果是NULL，表示当前节点为空，无法计算节点个数，因此返回0。
if (k == 1)
- 这行代码检查目标层级
k是否为 1。如果是 1，表示当前节点位于第 1 层，因此返回1，表示第 1 层有一个节点。
return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
- 如果当前节点不为空且目标层级不是第 1 层，这行代码递归地调用自身两次，分别计算左子树和右子树在第
k-1层的节点个数。然后，将这两个调用的结果相加，得到第k层的节点总数。总结来说，
BinaryTreeLevelKSize函数通过递归的方式遍历二叉树，计算并返回第k层上的节点个数。它首先检查当前节点是否为空，如果不为空且目标层级为第 1 层，则返回 1。如果不是第 1 层，则递归地计算左子树和右子树在降低一层后的节点个数，并将它们相加得到结果。这种方法可以正确地计算出任意二叉树在指定层级的节点总数。图解
层序遍历
什么是层序遍历
也就是：顾名思义，一层一层的输出
这里的关键点在于，怎么样一层一层进入，输出
那么此时我们可以采取队列的形式来进行使用，同时进队列，同时出队列
所以，这里我们是直接调用队列
队列的讲解-CSDN博客
https://blog.csdn.net/Jason_from_China/article/details/138730053
#include"Queue.h" // 层序遍历 void BinaryTreeLevelOrder(BTNode* root) { // 按照顺序，放入队列里面，先进先出，后进后出的原则 // 1，创建队列，初始化 // 2，如果不为空，根节点入队列 // 3，取栈顶，打印，出队列 Queue ps; QueueInit(&ps); if (root) QueuePush(&ps, root); while (!QueueEmpty(&ps)) { BTNode* ret = QueueFront(&ps); QueuePop(&ps); printf("%d ", ret->_data); if (ret->_left) QueuePush(&ps, ret->_left); if (ret->_right) QueuePush(&ps, ret->_right); } //队列的销毁 QueueDestroy(&ps); }解释：
#include"Queue.h"
- 这行代码包含了队列数据结构的头文件，该文件中定义了队列操作的相关函数和数据结构。
void BinaryTreeLevelOrder(BTNode* root)
- 这是函数的声明行，定义了一个名为
BinaryTreeLevelOrder的函数，它接收一个指向BTNode类型的指针root作为参数，表示二叉树的根节点。
Queue ps;
- 这行代码声明了一个名为
ps的队列变量。然而，这可能不足以正确地在某些语言中创建队列，因为队列可能需要动态分配（取决于其实现）。
QueueInit(&ps);
- 这行代码调用
QueueInit函数来初始化队列ps。
if (root) QueuePush(&ps, root);
- 如果根节点
root不为空，这行代码调用QueuePush函数将根节点入队。
while (!QueueEmpty(&ps))
- 这行代码开始一个循环，它会一直执行，直到队列变空。
QueueEmpty函数检查队列是否为空。
BTNode* ret = QueueFront(&ps);
- 这行代码调用
QueueFront函数获取队列前端的节点，但不从队列中移除它。
QueuePop(&ps);
- 这行代码调用
QueuePop函数从队列中移除前端的节点。
printf("%d ", ret->_data);
- 这行代码打印当前节点
ret的数据。
if (ret->_left) QueuePush(&ps, ret->_left);
- 如果当前节点
ret的左子节点存在，这行代码将其入队。
if (ret->_right) QueuePush(&ps, ret->_right);
- 如果当前节点
ret的右子节点存在，这行代码将其入队。
QueueDestroy(&ps);
- 最后，这行代码调用
QueueDestroy函数销毁队列，释放所有分配的内存。总结来说，
BinaryTreeLevelOrder函数使用队列来实现二叉树的层序遍历。它首先初始化一个队列，然后将根节点入队。在循环中，它取出队列前端的节点，打印其数据，然后将其左右子节点（如果存在）依次入队。这个过程一直重复，直到队列为空。这里的关键在于我们要认识到出去一个节点，进去两个节点
判断二叉树是否是完全二叉树
这里的逻辑也是采取队列的形式来进行判断，只是我们需要入空，当最后入的数值为空的时候，我们需要跳出循环，然后进行判断
// 判断二叉树是否是完全二叉树 bool BinaryTreeComplete(BTNode* root) { Queue ps; QueueInit(&ps); if (root) QueuePush(&ps, root); while (!QueueEmpty(&ps)) { BTNode* ret = QueueFront(&ps); QueuePop(&ps); if (ret == NULL) { break; } if (ret->_left) QueuePush(&ps, ret->_left); if (ret->_right) QueuePush(&ps, ret->_right); } while (!QueueEmpty(&ps)) { BTNode* ret = QueueFront(&ps); QueuePop(&ps); if (ret != NULL) { QueueDestroy(&ps); return false; } } //队列的销毁 QueueDestroy(&ps); return true; }
#include"Queue.h"
- 包含队列操作的头文件。
bool BinaryTreeComplete(BTNode* root)
- 函数声明，返回类型为
bool，表示最终的布尔结果（是或不是完全二叉树）。
Queue ps;
- 声明一个队列
ps。注意：这可能不足以在某些语言中创建队列，因为队列可能需要动态分配。
QueueInit(&ps);
- 初始化队列。
if (root) QueuePush(&ps, root);
- 如果根节点不为空，则将其入队。
第一个
while循环：
- 使用队列进行层序遍历，访问所有节点。
BTNode* ret = QueueFront(&ps);
- 获取队列前端的节点。
QueuePop(&ps);
- 将队列前端的节点出队。
if (ret == NULL) { break; }
- 如果节点为
NULL，则退出循环。这个条件永远不会满足，因为NULL节点不会被入队。
if (ret->_left) QueuePush(&ps, ret->_left);
- 如果存在左子节点，则将其入队。
if (ret->_right) QueuePush(&ps, ret->_right);
- 如果存在右子节点，则将其入队。
第二个
while循环：
- 这个循环的目的是检查队列中是否还有非
NULL节点。
BTNode* ret = QueueFront(&ps);
- 再次获取队列前端的节点。
QueuePop(&ps);
- 再次将队列前端的节点出队。
if (ret != NULL) { QueueDestroy(&ps); return false; }
- 如果节点不为
NULL，销毁队列并返回false。这部分逻辑是错误的，因为按照完全二叉树的定义，队列中应该只有NULL节点。
QueueDestroy(&ps);
- 销毁队列。
return true;
- 返回
true表示树是完全二叉树。
链式二叉树代码总结
Link_Teer.h
#define _CRT_SECURE_NO_WARNINGS 1 #pragma once #include<assert.h> #include<stdio.h> #include<stdlib.h> #include<stdbool.h> typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType _data; struct BinaryTreeNode* _left; struct BinaryTreeNode* _right; }BTNode; //二叉树的初始化 BTNode* BuyNode(BTDataType x); // 二叉树前序遍历 void BinaryTreePrevOrder(BTNode* root); // 二叉树中序遍历 void BinaryTreeInOrder(BTNode* root); // 二叉树后序遍历 void BinaryTreePostOrder(BTNode* root); // 二叉树节点个数 int BinaryTreeSize(BTNode* root); // 二叉树叶子节点个数 int BinaryTreeLeafSize(BTNode* root); // 二叉树高度 int BinaryTreeHeight(BTNode* root); // 二叉树查找值为x的节点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x); // 二叉树第k层节点个数 int BinaryTreeLevelKSize(BTNode* root, int k); // 二叉树销毁 void BinaryTreeDestory(BTNode* root); // 层序遍历 void BinaryTreeLevelOrder(BTNode* root); // 判断二叉树是否是完全二叉树 bool BinaryTreeComplete(BTNode* root);
Link_Teer.c
#include"Link_Teer.h" //二叉树的初始化 BTNode* BuyNode(BTDataType x) { BTNode* newnode = (BTNode*)malloc(sizeof(BTNode)); if (newnode == NULL) { perror("BinaryTreeInit:newnode:"); exit(1); } newnode->_data = x; newnode->_left = NULL; newnode->_right = NULL; return newnode; } // 二叉树前序遍历 void BinaryTreePrevOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } printf("%d ", root->_data); BinaryTreePrevOrder(root->_left); BinaryTreePrevOrder(root->_right); } // 二叉树中序遍历 void BinaryTreeInOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } BinaryTreeInOrder(root->_left); printf("%d ", root->_data); BinaryTreeInOrder(root->_right); } // 二叉树后序遍历 void BinaryTreePostOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } BinaryTreePostOrder(root->_left); BinaryTreePostOrder(root->_right); printf("%d ", root->_data); } // 二叉树节点个数 int BinaryTreeSize(BTNode* root) { if (root == NULL) { return 0; } return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1; } // 二叉树叶子节点个数 int BinaryTreeLeafSize(BTNode* root) { if (root == NULL) return 0; if (BinaryTreeLeafSize(root->_left) == 0 && BinaryTreeLeafSize(root->_right) == 0) return 1; return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right); } // 二叉树高度 int BinaryTreeHeight(BTNode* root) { if (root == NULL) { return 0; } int heightleft = BinaryTreeHeight(root->_left); int heightright = BinaryTreeHeight(root->_right); return heightleft >= heightright ? heightleft + 1 : heightright + 1; } // 二叉树第k层节点个数 int BinaryTreeLevelKSize(BTNode* root, int k) { if (root == NULL) return 0; if (k == 1) return 1; return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1); } // 二叉树查找值为x的节点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root == NULL) return NULL; if (root->_data == x) return root; BTNode* ret1 = BinaryTreeFind(root->_left, x); if (ret1 != NULL) { return ret1; } BTNode* ret2 = BinaryTreeFind(root->_right, x); if (ret2 != NULL) { return ret2; } return NULL; } // 二叉树销毁 void BinaryTreeDestory(BTNode* root) { if (root == NULL) { return; } BinaryTreeDestory(root->_left); BinaryTreeDestory(root->_right); free(root); } #include"Queue.h" // 层序遍历 void BinaryTreeLevelOrder(BTNode* root) { // 按照顺序，放入队列里面，先进先出，后进后出的原则 // 1，创建队列，初始化 // 2，如果不为空，根节点入队列 // 3，取栈顶，打印，出队列 Queue ps; QueueInit(&ps); if (root) QueuePush(&ps, root); while (!QueueEmpty(&ps)) { BTNode* ret = QueueFront(&ps); QueuePop(&ps); printf("%d ", ret->_data); if (ret->_left) QueuePush(&ps, ret->_left); if (ret->_right) QueuePush(&ps, ret->_right); } //队列的销毁 QueueDestroy(&ps); } // 判断二叉树是否是完全二叉树 bool BinaryTreeComplete(BTNode* root) { Queue ps; QueueInit(&ps); if (root) QueuePush(&ps, root); while (!QueueEmpty(&ps)) { BTNode* ret = QueueFront(&ps); QueuePop(&ps); if (ret == NULL) { break; } if (ret->_left) QueuePush(&ps, ret->_left); if (ret->_right) QueuePush(&ps, ret->_right); } while (!QueueEmpty(&ps)) { BTNode* ret = QueueFront(&ps); QueuePop(&ps); if (ret != NULL) { QueueDestroy(&ps); return false; } } //队列的销毁 QueueDestroy(&ps); return true; }
test.c
#include"Link_Teer.h" //构建二叉树 void teer() { BTNode* node1 = BuyNode(1); BTNode* node2 = BuyNode(2); BTNode* node3 = BuyNode(3); BTNode* node4 = BuyNode(4); BTNode* node5 = BuyNode(5); BTNode* node6 = BuyNode(6); //BTNode* node7 = BuyNode(7); node1->_left = node2; node2->_left = node3; node1->_right = node4; node4->_left = node5; node4->_right = node6; //node2->_right = node7; printf(" 二叉树前序遍历测试:\n"); BinaryTreePrevOrder(node1); printf("\n\n\n"); printf("二叉树中序遍历测试:\n"); BinaryTreeInOrder(node1); printf("\n\n\n"); printf("二叉树后序遍历测试:\n"); BinaryTreePostOrder(node1); printf("\n\n\n"); printf("二叉树节点个数测试:\n"); int ret1 = BinaryTreeSize(node1); printf("%d", ret1); printf("\n\n\n"); printf("二叉树叶子节点个数测试:\n"); int ret2 = BinaryTreeLeafSize(node1); printf("%d", ret2); printf("\n\n\n"); printf("二叉树高度测试:\n"); int ret3 = BinaryTreeHeight(node1); printf("%d", ret3); printf("\n\n\n"); printf("二叉树第k层节点个数测试:\n"); int ret4 = BinaryTreeLevelKSize(node1, 3); printf("%d", ret4); printf("\n\n\n"); printf("二叉树查找值为x的节点测试:\n"); BTNode* ret5 = BinaryTreeFind(node1, 6); printf("%d", ret5->_data); printf("\n\n\n"); printf("层序遍历测试:\n"); BinaryTreeLevelOrder(node1); printf("\n\n\n"); printf("判断二叉树是否是完全二叉树测试:\n"); bool ret6 = BinaryTreeComplete(node1); printf("%d", ret6); } int main() { //构建二叉树 teer(); return 0; }
