合肥网页设计工资_公司网站设计有哪些使用技巧呢_怎么做蛋糕_品牌推广方案案例

树

树的概念与结构

树是一种非线性的数据结构，它是由n（n>=0）个有限节点组成的一个具有层次关系的集合。
把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

有一个特殊的节点，称为根节点，根节点没有前驱节点。
除根节点外，其余节点被分成M（M>0）个互不相交的集合T1、T2、…、Tm，
其中每一个集合Ti（1 <= i <= m）又是一棵结构与树类似的子树。每棵子树的
根节点有且只有一个前驱，可以有0个或多个后继。因此，树是递归定义的。

树形结构中，子树之间不能有交集，否则就不是树形结构

非树形结构：

子树是不相交的
除了根节点外，每个节点有且仅有一个父节点
一棵N个节点的树有N-1条边

树相关术语

父节点/双亲结点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
如图：A是B的父节点，E是J的父节点等等。

子节点/孩子节点：一个节点含有的子树的根节点称为该节点的子节点；
如图：B是A的子节点，K是F的子节点等等。

节点的度：一个节点有几个孩子，它的度就是多少；
如图：A的度是6，F的度是2，K的度是0等等。

树的度：一棵树中，最大的节点的度称为树的度；
如图：可知A的度最大，所以树的度为6。

叶子节点/终端节点：度为0的节点称为叶子节点；
如图：B、C、H、I等等节点都是叶子节点。

分支节点/非终端节点：度不为0的节点；
如图：D、E、F、G等等节点都是分支节点。

兄弟节点：具有相同父节点的节点互称为兄弟节点；
如图：B、C是兄弟节点。

节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

树的高度或深度：树中节点的最大层次；
如图：树的高度为4。

节点的祖先：从根到该节点所经分支上的所有节点；
如图：对于P来说，节点A、E、J都是P的祖先，而A是所有节点的祖先。

路径：一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列；
如图：A到Q的路径为：A-E-J-Q；H到Q的路径为：H-D-A-E-J-Q。

子孙：以某节点为根的子树中任一节点都称为该节点的子孙；
如图：所有节点都是A的子孙，I、J、P、Q是E子孙。

森林：由m（m>0）棵互不相交的树组成的集合称为森林；

树的表示

孩子兄弟表示法：

树结构相对线性比较复杂，要存储表示起来就比较麻烦了，既要保存数据域，
也要保存节点和节点之间的关系，实际中树有很多种表示方式，如：双亲表示
法、孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。

这里就简单的了解其中最常用的孩子兄弟表示法。

struct TreeNode
{struct TreeNode* child;  //指向其左边开始的第一个孩子节点struct TreeNode* brother;//指向其右边的下一个兄弟节点int data;                //节点中的数据域
};

如图一个树的结构

对于该树的孩子兄弟表示法

树形结构实际运用场景

文件系统是计算机存储和管理文件的一种方式，它利用树形结构来组织和管理文件和文件夹。
在文件系统中，树结构被广泛应用，它通过父节点和子节点之间的关系来表示不同层级的文件
和文件夹之间的关联。

二叉树

二叉树的概念与结构

在树形结构中，我们最常用的就是二叉树，一棵二叉树是节点的一个有限集合，该集合由
一个根节点加上两棵别称为左子树和右子树的二叉树组成（左右子树可能为NULL）。

从上图可以看出二叉树具备以下特点：

1. 二叉树不存在度大于2的节点
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

注意：对于任意的二叉树都是由以下几种情况复合而成的

特殊的二叉树

满二叉树

一个二叉树，如果每一层的节点数都达到最大值，则这个二叉树就是满二叉树。
即如果一个二叉树的层数为K，且节点总数为(2^k)-1，那么它就是满二叉树。

完全二叉树

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。
对于深度为K，有n个节点的二叉树，当且仅当其每一个节点都与深度为K的
满二叉树中编号从1至n的节点一一对应时称之为完全二叉树。

注意：满二叉树是一种特殊的完全二叉树。

二叉树存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

顺序结构

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是
完全二叉树会有空间的浪费，所以完全二叉树更适合使用顺序结构存储。

实际中我们通常把堆（一种二叉树）使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统
虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

链式结构

二叉树的链式存储结构是指：用链表来表示一棵二叉树，即用链来表示元素的逻辑关系。通常的方法
是链表中每个节点由三个域组成，数据域和左右指针域，左右指针分别用来给出该节点左孩子和右孩
子所在的链节点的存储地址。链式结构又分为二叉链和三叉链。

实现顺序结构二叉树

堆的概念与结构

如果有一个集合K = {k0, k1, k2, …, kn-1},把它的所有元素按完全二叉树的顺序存储方式存储，
在一个一维数组中，满足：Ki <= K2i+1且Ki <= K2i+2（或Ki >= K2i+1且Ki >= K2i+2），
i = 0、1、2…，则称为小根堆（或大根堆）。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的性质

堆中某个节点的值总是不大于或不小于其父节点的值
堆总是一棵完全二叉树

二叉树性质

对于具有n个节点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有的节点
从0开始编号，则对于序号为i的节点有：

1. 若i>0，i节点的父节点的序号：(i-1)/2；i=0时，i为根节点编号，无父节点。
2. 若2i+1<n，i节点的左孩子节点的序号：2i+1；2i+1>=n时，无左孩子节点。
3. 若2i+2<n，i节点的右孩子节点的序号：2i+2；2i+2>=n时，无右孩子节点。

堆(Heap)的实现

heap.h

//堆的实现
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>//堆的结构
typedef int HPDatatype;
typedef struct Heap
{HPDatatype* arr;int size;//有效数据个数int capacity;//空间大小
}HP;//初始化
void HPInit(HP* php);//销毁
void HPDestroy(HP* php);//交换
void Swap(HPDatatype* x, HPDatatype* y);//向上调整法
void AdjustUp(HPDatatype* arr, int child);//入堆 -- 堆尾入
void HPPush(HP* php, HPDatatype x);//打印
void HPPrint(HP* php);//判空
bool HPEmpty(HP* php);//向下调整法
void AdjustDown(HPDatatype* arr, int parent, int n);//出堆 -- 堆顶出
void HPPop(HP* php);//查询堆顶数据
HPDatatype HPTop(HP* php);

初始化

//初始化
void HPInit(HP* php)
{//防止php为NULLassert(php);//初始化php->arr = NULL;php->capacity = php->size = 0;
}

销毁

//销毁
void HPDestroy(HP* php)
{//防止php为NULLassert(php);//php->arr不为空，就释放if (php->arr)free(php->arr);php->arr = NULL;php->capacity = php->size = 0;
}

入堆 – 堆尾入

//入堆 -- 堆尾入
void HPPush(HP* php, HPDatatype x)
{//防止php为NULLassert(php);//判断增容if (php->capacity == php->size){int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDatatype* tmp = (HPDatatype*)realloc(php->arr, newcapacity * sizeof(HPDatatype));if (tmp == NULL){perror("realloc fail");exit(1);}php->arr = tmp;php->capacity = newcapacity;}//入堆php->arr[php->size] = x;//向上调整成堆AdjustUp(php->arr, php->size);//更新有效数据个数php->size++;
}

向上调整算法

堆的插入

将新数据插入到数组的尾上，再进行向上调整算法，直到满足堆。

对于下图新插入的元素10，这里是在建小堆。
第一步：10比其父节点元素28小，交换位置，继续向上调整
第二步：10比其父节点元素18小，交换位置，继续向上调整
第三步：10比其父节点元素15小，交换位置，继续向上调整
第四步：此时元素10节点的序号为0，无父节点，无法向上调整，跳出循环

//交换
void Swap(HPDatatype* x, HPDatatype* y)
{HPDatatype tmp = *x;*x = *y;*y = tmp;
}//向上调整法 -- 时间复杂度：logn
void AdjustUp(HPDatatype* arr, int child)//这里的child是新插入元素的序号（即下标）
{//找到其父节点int parent = (child - 1) / 2;//经过上图演示知只有child==0时才跳出循环while (child > 0){//小堆：<//大堆：>if (arr[child] < arr[parent]){//调整//交换Swap(&arr[child], &arr[parent]);//为下一次向上调整做准备child = parent;parent = (child - 1) / 2;}else//说明arr数组已经符合堆结构break;}
}

test.c中对入堆操作进行测试

	HP hp;HPInit(&hp);//测试入堆HPPush(&hp, 20);HPPush(&hp, 14);HPPush(&hp, 25);HPPush(&hp, 16);HPPush(&hp, 24);HPPush(&hp, 13);

计算向上调整算法建堆时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树
来证明（时间复杂度本来看的就是近似值，多几个节点不影响结果）

则需要移动节点总的移动步数为：每层节点个数 × 向上调整次数（第一层调整次数为0）

打印

//打印
void HPPrint(HP* php)
{//防止php为NULLassert(php);//遍历arr数组打印for (int i = 0; i < php->size; i++){printf("%d ", php->arr[i]);}printf("\n");
}

判空

//判空
bool HPEmpty(HP* php)
{//防止php为NULLassert(php);//有效元素个数为0时堆为空return php->size == 0;
}

出堆 – 堆顶出

//出堆 -- 堆顶出
void HPPop(HP* php)
{//防止堆为空assert(!HPEmpty(php));//交换堆顶数据和堆尾数据Swap(&php->arr[0], &php->arr[php->size - 1]);//出堆--达到删除堆顶数据效果php->size--;//向下调整成堆AdjustDown(php->arr, 0, php->size);
}

向下调整算法

堆的删除

删除堆是删除堆顶的数据，将堆顶的数据跟最后一个数据交换，然后删除数组最后一个数据，
再进行向下调整算法。

向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

//向下调整法 -- 时间复杂度：logn
void AdjustDown(HPDatatype* arr, int parent, int n)//parent是堆顶下标，n是有效元素个数
{//求parent的左孩子int child = parent * 2 + 1;//如果要调整的孩子的下标>=有效元素个数就出循环while (child < n){//小堆：>//大堆：<//保证右孩子合法且如果左孩子的数据大于右孩子的数据，就让parent和右孩子比较if (child + 1 < n && arr[child] > arr[child + 1])child++;//小堆：<//大堆：>if (arr[child] < arr[parent]){//调整//交换Swap(&arr[child], &arr[parent]);//为下一次调整做准备parent = child;child = parent * 2 + 1;}else//说明arr数组已经符合堆结构break;}
}

test.c中对出堆操作进行测试

	HP hp;HPInit(&hp);//测试入堆HPPush(&hp, 20);HPPush(&hp, 14);HPPush(&hp, 25);HPPush(&hp, 16);HPPush(&hp, 24);HPPush(&hp, 13);HPPrint(&hp);//测试出堆HPPop(&hp);HPPrint(&hp);HPPop(&hp);HPPrint(&hp);HPPop(&hp);HPPrint(&hp);HPPop(&hp);HPPrint(&hp);HPPop(&hp);HPPrint(&hp);HPPop(&hp);HPPrint(&hp);HPDestroy(&hp);

下图是第一次出堆的图解

计算向下调整算法建堆时间复杂度

则需要移动节点总的移动步数为：每层节点个数 × 向下调整次数

查询堆顶数据

//查询堆顶数据
HPDatatype HPTop(HP* php)
{//防止堆为空assert(!HPEmpty(php));//返回堆顶数据return php->arr[0];
}

test.c中测试

	HP hp;HPInit(&hp);HPPush(&hp, 20);HPPush(&hp, 14);HPPush(&hp, 25);HPPush(&hp, 16);HPPush(&hp, 24);HPPush(&hp, 13);HPPrint(&hp);while (!HPEmpty(&hp)){printf("%d ", HPTop(&hp));HPPop(&hp);}HPDestroy(&hp);

怎么把堆排成了升序，难道这就是传说中的堆排序吗？

堆的应用

堆排序

版本一：基于已有数组建堆、取堆顶元素完成排序

//堆排序 -- 基于数据结构堆实现
void HeapSort1(int* arr, int n)
{HP hp;HPInit(&hp);//对数组的每个元素入堆for (int i = 0; i < n; i++){HPPush(&hp, arr[i]);}//将数组arr替换成有序数组int i = 0;while (!HPEmpty(&hp)){arr[i++] = HPTop(&hp);HPPop(&hp);}HPDestroy(&hp);
}int main()
{int arr[6] = { 20, 14, 25, 16, 24, 13 };printf("排序前：\n");Print(arr, 6);HeapSort1(arr, 6);printf("排序后：\n");Print(arr, 6);
}

g
该版本有一个前提，必须提供有现成的数据结构堆。

版本二：数组建堆,首尾交换,交换后的堆尾数据从堆中删掉,将堆顶数据向下调整选出次小(大)数据

//利用堆的思想实现堆排序
void HeapSort(int* arr, int n)
{
//这两个建堆思想都是由小及大，把一个大工程分成几个小工程，从小工程开始建堆1.向下调整法建堆 O(N)//for (int i = (n - 1 - 1) / 2; i >= 0; i--)//{//	AdjustDown(arr, i, n);//}//1.向上调整法建堆 O(N)for (int i = 0; i < n; i++){AdjustUp(arr, i);}//2.堆排序//O(N*logN)//end是堆尾下标int end = n - 1;while (end > 0){//交换堆顶和堆尾Swap(&arr[0], &arr[end]);//调整AdjustDown(arr, 0, end);end--;}//结论：排升序 -- 建大堆 排降序 -- 建小堆
}

TOP-K问题

TOP-K问题：即求数据集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于TOP-K问题，能想到的最简单直接的方式就是排序，但是如果数据量非常大，排序就不太
可取（可能数据都不能一下子全部加载到内存中）。最佳的方式就是用堆来解决，基本思路如下：

1）用数据集合中前K个元素来建堆
前K个最大的元素，则建小堆
前K个最小的元素，则建大堆

2）用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比较之后，堆中剩余的K个元素就是所求的前K个最小或最大的元素

//造10万个数
void CreateNDate()
{//造数据int n = 100000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL) {perror("fopen error");return;}for (int i = 0; i < n; ++i){int x = (rand() + i) % 1000000;fprintf(fin, "%d\n", x);}fclose(fin);
}void TopK()
{int k;printf("请输入K的值：");scanf("%d", &k);const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen fail");exit(1);}//申请K个int大小的空间int* minHeap = (int*)malloc(k * sizeof(int));if (minHeap == NULL){perror("malloc fail");exit(2);}//从文件中输入k个数据建小堆for (int i = 0; i < k; i++){fscanf(fout, "%d", &minHeap[i]);}//向下调整建小堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(minHeap, i, k);}//让剩下的n-k个数据依次根堆顶比较int x;while (fscanf(fout, "%d", &x) != EOF){//建小堆，x比堆顶大就入堆if (x > minHeap[0]){minHeap[0] = x;//调整AdjustDown(minHeap, 0, k);}}//输出Print(minHeap, k);fclose(fout);fout = NULL;
}int main()
{CreateNDate();TopK();
}

在data.txt中放入1个最大的数，验证TOP-K问题是否解决成功。

实现链式结构二叉树 - 递归的暴力美学

用链表来表示一棵二叉树，即用链来表示元素的逻辑关系。链表中每个节点由数据域和左右指针域
组成，左右指针分别用来给出该节点左右孩子所在的链节点的存储地址。

Tree.h

//实现链式结构的二叉树
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>//二叉树节点的结构
typedef char BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;//当前节点的数据域struct BinaryTreeNode* left;//指向当前节点的左孩子struct BinaryTreeNode* right;//指向当前节点的右孩子
}BTNode;//二叉树创建
BTNode* CreateTree();//前序遍历 - 根左右
void PreOrder(BTNode* root);//中序遍历 - 左根右
void InOrder(BTNode* root);//后序遍历 - 左右根
void PostOrder(BTNode* root);//二叉树节点个数
int BinaryTreeSize(BTNode* root);//二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);//二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);//二叉树的深度/高度
int BinaryTreeDepth(BTNode * root);//二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);//二叉树销毁
void BinaryTreeDestory(BTNode** proot);//层序遍历 - 需要借助数据结构队列
void LevelOrder(BTNode* root);

二叉树的创建

手动创建一棵链式二叉树:

//申请新节点
BTNode* BuyBTNode(BTDataType x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}//二叉树创建
BTNode* CreateTree()
{BTNode* n1 = BuyBTNode('A');BTNode* n2 = BuyBTNode('B');BTNode* n3 = BuyBTNode('C');BTNode* n4 = BuyBTNode('D');BTNode* n5 = BuyBTNode('E');BTNode* n6 = BuyBTNode('F');n1->left = n2;n1->right = n3;n2->left = n4;n3->left = n5;n3->right = n6;return n1;
}

这里创建的二叉树是按照上图创建的。

回归二叉树的概念，二叉树分为空树和非空二叉树，非空二叉树由根节点、根节点的左子树、
根节点的右子树组成，而根节点的左子树和右子树分别又是由子树节点、子树节点的左子树、
子树节点的右子树组成的，因此二叉树定义是递归式的，后续链式二叉树的操作中基本都是
递归实现的。

前中后序遍历

二叉树的操作离不开树的遍历，二叉树的遍历分为前序遍历、中序遍历、后序遍历等。

遍历规则

1. 前序遍历（Preorder Traversal亦称先序遍历）访问顺序为：根节点、左子树、右子树
2. 中序遍历（Inorder Traversal）访问顺序为：左子树、根节点、右子树
3. 后序遍历（Postorder Traversal）访问顺序为：左子树、右子树、根节点

前/中/后序遍历

//前序遍历 - 根左右
void PreOrder(BTNode* root)
{//如果根节点为空就打印NULLif (root == NULL){printf("NULL ");return;}//顺序：根、左、右printf("%c ", root->data);PreOrder(root->left);PreOrder(root->right);
}//中序遍历 - 左根右
void InOrder(BTNode* root)
{//如果根节点为空就打印NULLif (root == NULL){printf("NULL ");return;}//顺序：左、根、右InOrder(root->left);printf("%c ", root->data);InOrder(root->right);
}//后序遍历 - 左右根
void PostOrder(BTNode* root)
{//如果根节点为空就打印NULLif (root == NULL){printf("NULL ");return;}//顺序：左、右、根PostOrder(root->left);PostOrder(root->right);printf("%c ", root->data);
}

test.c

	BTNode* bt = CreateTree();//测试前中后序遍历PreOrder(bt);printf("\n");InOrder(bt);printf("\n");PostOrder(bt);printf("\n");

二叉树节点个数

如果根节点为空，返回0
如果根节点不为空，返回1 + 左子树节点个数 + 右子树节点个数

//二叉树节点个数
int BinaryTreeSize(BTNode* root)
{//如果根节点为空就返回0if (root == NULL)return 0;//走到这里说明root!=NULLreturn 1 + BinaryTreeSize(root->left)+ BinaryTreeSize(root->right);
}

test.c

	//测试二叉树节点个数printf("Size：%d\n", BinaryTreeSize(bt));

二叉树叶子节点个数

如果根节点为空，返回0
如果根节点不为空，但左右孩子节点为空，说明该节点是叶子节点，返回1
否则，递归地计算左子树和右子树中叶子节点个数，并将它们相加返回

//二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{//如果根节点为空就返回0if (root == NULL)return 0;//如果根节点不为空，但左右孩子节点为空，说明该节点是叶子节点，返回1if (root->left == NULL && root->right == NULL)return 1;//否则，递归地计算左子树和右子树中叶子节点个数，并将它们相加返回return BinaryTreeLeafSize(root->left)+ BinaryTreeLeafSize(root->right);
}

test.c

	//测试叶子节点个数printf("LeafSize：%d\n", BinaryTreeLeafSize(bt));

二叉树第k层节点个数

若根节点为空，直接返回0，表明该层没有节点
若k == 1，说明到达了目标层，若节点存在就返回1
若k > 1，递归地在左子树和右子树中计算第k-1层地节点个数，并将结果相加

//二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{//若根节点为空，直接返回0，表明该层没有节点if (root == NULL)return 0;//若k == 1，说明到达了目标层，若节点存在就返回1if (k == 1)return 1;//若k > 1，递归地在左子树和右子树中计算第k-1层地节点个数，并将结果相加return BinaryTreeLevelKSize(root->left, k - 1)+ BinaryTreeLevelKSize(root->right, k - 1);
}

test.c

	//测试二叉树第k层节点个数printf("lKSize：%d\n", BinaryTreeLevelKSize(bt, 3));

二叉树的深度/高度

当根节点为空时返回0
否则，递归地计算左子树和右子树地深度，取二者的较大值，然后加1（加上根节点本身）

//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root)
{//当根节点为空时返回0if (root == NULL)return 0;//否则，递归地计算左子树和右子树地深度，取二者的较大值，然后加1（加上根节点本身）int leftDepth = BinaryTreeDepth(root->left);int rightDepth = BinaryTreeDepth(root->right);return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);}

test.c

	//测试二叉树的深度/高度printf("Depth：%d\n", BinaryTreeDepth(bt));

二叉树查找值为x的节点

若当前节点为空，就返回NULL
若当前节点的值等于x，就返回该节点
递归地在左子树中查找，若找到了就返回该节点
若左子树中未找到，就递归地在右子树中查找并返回结果
若上述所有情况都找不到，就返回NULL

//二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{//若当前节点为空，就返回NULLif (root == NULL)return NULL;//若当前节点的值等于x，就返回该节点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;//若上述所有情况都找不到，就返回NULLreturn NULL;
}

test.c

	//测试二叉树查找值为x的节点BTNode* find = BinaryTreeFind(bt, 'E');if (find != NULL)printf("找到了\n");elseprintf("找不到\n");

二叉树销毁 – 左右根

若当前节点为空，就直接返回
递归销毁左子树
递归销毁右子树
最后销毁根节点，并置空

//二叉树销毁 -- 左右根
void BinaryTreeDestory(BTNode** proot)
{//防止proot为NULLassert(proot);//若当前节点为空，就直接返回if (*proot == NULL)return;//递归销毁左子树BinaryTreeDestory(&((*proot)->left));//递归销毁右子树BinaryTreeDestory(&((*proot)->right));//最后销毁根节点，并置空free(*proot);*proot = NULL;
}

test.c

	//测试销毁BinaryTreeDestory(&bt);

层序遍历

设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，
首先访问第一层的节点，然后从左到右访问第2层上的节点，接着是第3层的
节点，以此类推，自上而下，自左至右逐层访问树的节点的过程就是层序遍历。

实现层序遍历需要借助数据结构：队列

借助队列实现层序遍历是因为队列具有先进先出的特点。

把之前写的队列的实现拉入当前项目，把数据data的类型改为树的节点指针类型，
让队列能够存放树的节点，方便在遍历时找该节点的孩子节点。

代码实现

//层序遍历 - 需要借助数据结构队列
void LevelOrder(BTNode* root)
{//创建一个队列并初始化Q q;QInit(&q);//将根节点入队列QPush(&q, root);//利用队列实现层序遍历while (!QEmpty(&q))//队列不为空就进入循环{//取队头，出队头BTNode* top = QFront(&q);//保存队头节点QPop(&q);//出对头printf("%c ", top->data);//打印保存的队头数据//将队头非空左右孩子入队列if (top->left)QPush(&q, top->left);if (top->right)QPush(&q, top->right);}//销毁队列QDestroy(&q);
}

test.c

	//测试层序遍历LevelOrder(bt);

判断是否为完全二叉树

利用该图更好理解。

//判断二叉树是否为完全二叉树 - 需要借助数据结构队列
bool BinaryTreeComplete(BTNode* root)
{//创建一个队列并初始化Q q;QInit(&q);//将根节点入队列QPush(&q, root);//第一次循环while (!QEmpty(&q)){//取队头，出队头BTNode* top = QFront(&q);QPop(&q);//如果取到空节点就跳出循环if (top == NULL)break;//不为空，就继续将左右孩子入队QPush(&q, top->left);QPush(&q, top->right);}//第二次循环while (!QEmpty(&q)){//取队头，出队头BTNode* top = QFront(&q);QPop(&q);//如果取到不为空的节点，就说明不是完全二叉树if (top != NULL){QDestroy(&q);return false;}}//跳出循环，说明是完全二叉树QDestroy(&q);return true;
}