湘潭网站建设方案咨询,莱芜招聘的网站,最新的电商资讯有哪些,怎样营销建设网站文章目录1.树概念及结构1.1树的相关概念1.2树的结构2.二叉树概念及结构2.1相关概念2.2特殊的二叉树2.3二叉树的性质2.4二叉树的存储结构3.二叉树的顺序结构及实现3.1二叉树的顺序结构3.2堆的概念3.3堆的实现Heap.hHeap.c3.4堆的应用3.4.1 堆排序3.4.2 TOP-KOJ题最小K个数4.二叉…
文章目录1.树概念及结构1.1树的相关概念1.2树的结构2.二叉树概念及结构2.1相关概念2.2特殊的二叉树2.3二叉树的性质2.4二叉树的存储结构3.二叉树的顺序结构及实现3.1二叉树的顺序结构3.2堆的概念3.3堆的实现Heap.hHeap.c3.4堆的应用3.4.1 堆排序3.4.2 TOP-KOJ题最小K个数4.二叉树链式结构的实现4.1遍历操作4.2其他操作4.3判断完全二叉树5.总结1.树概念及结构
1.1树的相关概念
树的概念树是一种非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的
有一个特殊的结点称为根结点根节点没有前驱结点除根节点外其余结点被分成M(M0)个互不相交的集合T1**、T2、……、**Tm其中每一个集合Ti(1 i m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱可以有0个或多个后继因此树是递归定义的 注意树形结构中子树之间不能有交集否则就不是树形结构 节点的度个节点含有的子树的个数称为该节点的度 如上图A的为6 叶节点或终端节点度为0的节点称为叶节点 如上图B、C、H、I…等节点为叶节点 非终端节点或分支节点度不为0的节点 如上图D、E、F、G…等节点为分支节点 双亲节点或父节点若一个节点含有子节点则这个节点称为其子节点的父节点 如上图A是B的父节点 孩子节点或子节点一个节点含有的子树的根节点称为该节点的子节点 如上图B是A的孩子节点 兄弟节点具有相同父节点的节点互称为兄弟节点 如上图B、C是兄弟节点 树的度一棵树中最大的节点的度称为树的度 如上图树的度为6 节点的层次从根开始定义起根为第1层根的子节点为第2层以此类推 树的高度或深度树中节点的最大层次 如上图树的高度为4 堂兄弟节点双亲在同一层的节点互为堂兄弟如上图H、I互为兄弟节点 节点的祖先从根到该节点所经分支上的所有节点如上图A是所有节点的祖先 子孙以某节点为根的子树中任一节点都称为该节点的子孙。如上图所有节点都是A的子孙 森林由mm0棵互不相交的树的集合称为森林 概念的知识很多但是我们还是需要去理解
1.2树的结构
树结构相对线性表就比较复杂了要存储表示起来就比较麻烦了既要保存值域也要保存结点和结点之间的关系实际中树有很多种表示方式如双亲表示法孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法 树在实际中的运用表示文件系统的目录树结构,网上找的图片 2.二叉树概念及结构
2.1相关概念 一棵二叉树是结点的一个有限集合: 1.或者为空 2.由一个根节点加上两棵别称为左子树和右子树的二叉树组成 二叉树不存在度大于2的结点二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树
2.2特殊的二叉树
满二叉树一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。也就是说如果一个二叉树的层数为K且结点总数是 则它就是满二叉树。完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树
看了概念可能不太好理解我们来看图对比一下就知道区别在哪里了 2.3二叉树的性质 若规定根节点的层数为1则一棵非空二叉树的第i层上最多有2^(i-1) 个结点. 若规定根节点的层数为1则深度为h的二叉树的最大结点数是2^(h-1) 对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2,则有n0 n2 1 若规定根节点的层数为1具有n个结点的满二叉树的深度hlong(n1) . (ps是log以2为底n1为对数) 对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有节点从0开始编号则对于序号为i的结点有 : 1.若i0i位置节点的双亲序号(i-1)/2i0i为根节点编号无双亲节点 2.若2i1n左孩子序号2i12i1n否则无左孩子 3.若2i2n右孩子序号2i22i2n否则无右孩子
了解完二叉树的性质之后我们不妨来做几道选择题
1.某二叉树共有 399 个结点其中有 199 个度为 2 的结点则该二叉树中的叶子结点数为 A 不存在这样的二叉树 B 200 C 198 D 199
答案B。n0 n21既n01991 200 2.下列数据结构中不适合采用顺序存储结构的是 A 非完全二叉树 B 堆 C 队列 D 栈
答案A。
3.在具有 2n 个结点的完全二叉树中叶子结点个数为 A n B n1 C n-1 D n/2
答案A。总结点数n n0n1n2;又n2 n0-1,既nn0n1n0-1,在完全二叉树中n1只有0个或者1个代入选A
4.一棵完全二叉树的节点数位为531个那么这棵树的高度为 A 11 B 10 C 8 D 12
答案B
5.一个具有767个节点的完全二叉树其叶子节点个数为 A 383 B 384 C 385 D 386
答案B。类似于第3题总结点n n0n1n0-1;n1为0或者1,代入能整除的选B
2.4二叉树的存储结构
二叉树一般可以使用两种结构存储一种顺序结构一种链式结构
顺序存储 顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储下面我们会说到。二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树 链式存储 二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链当前我们使用的是二叉链
3.二叉树的顺序结构及实现
3.1二叉树的顺序结构
普通的二叉树是不适合用数组来存储的因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结 构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储。 3.2堆的概念
如果有一个关键码的集合K {K0,K1,K2,…Kn-1};把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中并满足:KiK2i1并且KiK2i2,i 012…则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆。
堆中某个节点的值总是不大于或不小于其父节点的值堆总是一棵完全二叉树
我们来做一道选择题试一试
下列关键字序列为堆的是 A 100,60,70,50,32,65 B 60,70,65,50,32,100 C 65,100,70,32,50,60 D 70,65,100,32,50,60 E 32,50,100,70,65,60 F 50,100,70,65,60,32
解析这里没有明确说明是大堆还是小堆我们直接在草稿上简单画一下就知道答案了 3.3堆的实现
Heap.h
#include stdio.h
#include assert.h
#include stdlib.h
#include time.h
#include stdbool.htypedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;
//初始化堆
void HeapInit(HP* php);
//销毁堆
void HeapDestory(HP* php);
//打印堆
void HeapPrint(HP* php);
//插入X继续保持堆形态
void HeapPush(HP* php,HPDataType x);
//删除堆顶元素
void HeapPop(HP* php);
//判断是否为空
bool HeapEmpty(HP* php);
//返回堆顶元素
HPDataType HeapTop(HP* php);
//返回堆的元素大小
int HeapSize(HP* php);这就是一些要实现的接口下面通过Heap.c对以上接口进行说明。
Heap.c
初始化
//初始化
void HeapInit(HP* php)
{assert(php);php-a NULL;php-size php-capacity 0;
}插入X并保持堆
插入之前是小根堆假设堆已经创建好后面会说到堆的创建不要急先看这一部分便于理解后面堆的创建就简单多了我们是在尾部把X插入的然后再进行向上调整原来必须是大堆或者小堆了。
比如先插入一个10到数组的尾上 再进行向上调整算法直到满足堆 最后一个位置是php-size-1.要找到父节点(child-1)/2,如此我们去比较大小进行交换调整就能够实现我们的向上调整
//交换
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}
//向上调整这里是小堆
void AdjustUp(HPDataType* a,int child)
{//父亲结点int parent (child - 1) / 2;//终止条件孩子等于0大于0就继续调整//不要拿父亲作为条件,父亲和孩子都等于0的时候paretn (0-1)/2还是0死循环了//while(parent0)while (child 0){//孩子小于父亲——小堆//如果要建大堆的话直接反过来就行了if (a[child] a[parent]){//交换Swap(a[child], a[parent]);//继续往上迭代child parent;parent (child - 1) / 2;}else{break;}}
}
//插入X继续保持堆形态
void HeapPush(HP* php, HPDataType x)
{assert(php);if (php-size php-capacity){int newCapacity php-capacity 0 ? 4 : php-capacity * 2;//进行扩容HPDataType* tmp (HPDataType*)realloc(php-a,sizeof(HPDataType) * newCapacity);if (NULL tmp){perror(malloc fail);exit(-1);}php-a tmp;php-capacity newCapacity;}//插入php-a[php-size] x;php-size;//向上调整最后一个位置AdjustUp(php-a, php-size - 1);
}我们不妨来测试一下这段代码 删除堆顶元素
开始之前想想删除堆顶元素能干什么❓可以找出次大获知次小
删除堆是删除堆顶的数据将堆顶的数据根最后一个数据一换然后删除数组最后一个数据再进行向下调整算法。 //向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{//最小的默认为左孩子int minchild 2 * parent 1;while (minchild n){//找出小的那个孩子if (minchild1na[minchild 1] a[minchild]){minchild;}if (a[minchild] a[parent]){Swap(a[minchild], a[parent]);parent minchild;minchild 2 * parent 1;}else{break;}}
}
//删除堆顶元素——找出次大或者次小
void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));Swap(php-a[0], php-a[php-size - 1]);php-size--;AdjustDown(php-a, php-size, 0);}
判断是否为空
bool HeapEmpty(HP* php)
{assert(php);return php-size 0;
}取堆顶元素
//返回堆顶元素
HPDataType HeapTop(HP* php)
{assert(php);assert(!HeapEmpty(php));return php-a[0];
}元素个数
int HeapSize(HP* php)
{assert(php);return php-size;
}打印
void HeapPrint(HP* php)
{assert(php);for (int i 0; i php-size; i){printf(%d , php-a[i]);}printf(\n);
}销毁
void HeapDestory(HP* php)
{assert(php);free(php-a);php-a NULL;php-size php-capacity 0;
}3.4堆的应用
3.4.1 堆排序
堆排序即利用堆的思想来进行排序总共分为两个步骤 建堆 升序建大堆如果建小堆的话小堆不一定有序只是堆顶最小那下一个最小的数呢如何依次选最小的数据就算是选出来了之后结点之间的关系就全乱了无法继续利用优势只能重新建堆O(N)选出次小的数据效率太低了建大堆直接交换堆顶和最后一个进行向下调整即可 降序建小堆 堆利用堆删除思想来进行排序 建堆和堆删除中都用到了向下调整因此掌握了向下调整就可以完成堆排序。回顾一下向下调整的过程
这里的建堆是直接用数组进行建堆可以用向上调整算法进行建堆也可以利用向下调整建堆有什么区别我们先来看代码的实现
//建堆——a利用向上调整建堆——ON*logN//直接插入/*for (int i 1; i n; i){AdjustUp(a, i);}*///建完堆之后无序我们排个序//建堆——向下调整建堆(从最后一个节点的父亲开始,开始向下调整直到根)——O(N)for (int i (n-1-1)/2; i0; i--){AdjustDown(a, n, i);}
两种的时间复杂度不一样向上调整建堆的时间复杂度是ON*logN;向下调整建堆的时间复杂度是ON。所以我们选用的是向下调整算法进行建堆关于向下调整算法时间复杂度的推导过程 因此建堆的时间复杂度为O(N)。
关于向上调整算法时间复杂度的推导过程注意红色部分这就是这两种的区别 了解完以后我们来实现堆排序
//O(N*longN)
//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{//最小的默认为左孩子int minchild 2 * parent 1;while (minchild n){//找出小的那个孩子if (minchild1na[minchild1] a[minchild]){minchild;}//小堆if (a[minchild] a[parent]){Swap(a[minchild], a[parent]);parent minchild;minchild 2 * parent 1;}else{break;}}
}void HeapSort(int* a, int n)
{//建堆——a利用向上调整建堆//直接插入/*for (int i 1; i n; i){AdjustUp(a, i);}*///建完堆之后无序我们排个序//建堆——向下调整建堆(从最后一个节点的父亲开始,开始向下调整直到根)for (int i (n-1-1)/2; i0; i--){AdjustDown(a, n, i);}//选数int i 1;while (i n){Swap(a[0], a[n - i]);AdjustDown(a, n - i, 0);i;}}int main()
{int a[] { 15,1,19,25,8,34,65,4,27,7 };HeapSort(a, sizeof(a) / sizeof(int));for (int i 0; i sizeof(a) / sizeof(int); i){printf(%d , a[i]);}printf(\n);return 0;
}这里建的是小堆自然是降序。
3.4.2 TOP-K
TOP-K问题即求数据结合中前K个最大的元素或者最小的元素一般情况下数据量都比较大 有人说简单啊排个序NlogN选出前K个即可。但是如果数据量非常大排序就不太可取了 (可能数据都不能一下子全部加载到内存中 )
最佳的方式就是用堆来解决 用数据集合中前K个元素来建堆 前k个最大的元素则建小堆(建大堆呢有什么区别) 前k个最小的元素则建大堆 用剩余的N-K个元素依次与堆顶元素来比较不满足则替换堆顶元素 将剩余N-K个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素。 代码实现这里采用前面学的文件的一些函数
//创建一个文件并且随机生成一些数字
void CreateDataFile(const char* filename, int N)
{FILE* Fin fopen(filename, w);if (Fin NULL){perror(fopen fail);exit(-1);}srand(time(0));for (int i 0; i N; i){fprintf(Fin, %d , rand()%10000);}
}//建堆选前K个最大的数并且打印
void PrintTopK(const char* filename, int k)
{assert(filename);FILE* fout fopen(filename, r);if (fout NULL){perror(fopen fail);exit(-1);}//小堆int* minHeap (int*)malloc(sizeof(int) * k);if (minHeap NULL){perror(malloc fail);exit(-1);}//读前K个元素for (int i 0; i k; i){fscanf(fout, %d, minHeap[i]);}//建k个数的堆for (int j (k - 1 - 1) / 2; j 0; j--){AdjustDown(minHeap, k, j);}//读取后N-k个int val 0;while (fscanf(fout,%d,val) ! EOF){if (val minHeap[0]){minHeap[0] val;AdjustDown(minHeap, k, 0);}}for (int i 0; i k; i){printf(%d , minHeap[i]);}printf(\n);free(minHeap);fclose(fout);
}int main()
{int N 10000;const char* filename Data.txt;int k 10;CreateDataFile(filename, N);PrintTopK(filename, k);return 0;
}随机生成10000以内的数字至此TOP-K代码的实现到这里结束。下面我们可以来做一道OJ题目
OJ题
最小K个数
点我 一看就是上面说的TOP-k问题直接上手代码
void Swap(int*p1,int*p2){int*tmp *p1;*p1 *p2;*p2 tmp;}void AdjustDown(int*a,int n,int parent){int minchild parent*21;while(minchildn){if(minchild1na[minchild1]a[minchild]){minchild;}if(a[minchild]a[parent]){Swap(a[minchild],a[parent]);parent minchild;minchild parent*21;}else{break;}}}
int* smallestK(int* arr, int arrSize, int k, int* returnSize){if(k0){*returnSize 0;return NULL;}int *minHeap (int*)malloc(sizeof(int)*(k));for(int i 0;ik;i){minHeap[i] arr[i];}//前K个数建大堆for(int j (k-1-1)/2;j0;j--){AdjustDown(minHeap,k,j);}//后N-K个数进入for(int i k;iarrSize;i){if(arr[i]minHeap[0]){minHeap[0] arr[i];AdjustDown(minHeap,k,0);}}*returnSize k;return minHeap;
}4.二叉树链式结构的实现
在学习二叉树的基本操作前需先要创建一棵二叉树然后才能学习其相关的基本操作。为了降低学习成本此处手动快速创建一棵简单的二叉树这里以简单的实现为主。后续在来讨论其创建方式
以这颗树为例子
#include stdio.h
#include assert.h
#include stdlib.h
typedef int BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;BTNode* CreatTree()
{BTNode* n1 (BTNode*)malloc(sizeof(BTNode));assert(n1);BTNode* n2 (BTNode*)malloc(sizeof(BTNode));assert(n2);BTNode* n3 (BTNode*)malloc(sizeof(BTNode));assert(n3);BTNode* n4 (BTNode*)malloc(sizeof(BTNode));assert(n4);BTNode* n5 (BTNode*)malloc(sizeof(BTNode));assert(n5);BTNode* n6 (BTNode*)malloc(sizeof(BTNode));assert(n6);n1-data 1;n2-data 2;n3-data 3;n4-data 4;n5-data 5;n6-data 6;n1-left n2;n1-right n4;n2-left n3;n2-right NULL;n3-left NULL;n3-right NULL;n4-left n5;n4-right n6;n5-left NULL;n5-right NULL;n6-left NULL;n6-right NULL;return n1;
}
这就大概搭建起了二叉树的框架下面来说一说其操作
4.1遍历操作
先序、中序、后序遍历递归操作
//先序
void PreOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}printf(%d , root-data);PreOrder(root-left);PreOrder(root-right);
}//中序
void InOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}InOrder(root-left);printf(%d , root-data);InOrder(root-right);
}//后序
void PostOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-data);
}我们不难发现二叉树的遍历操作通过递归实现非常地简单实现并不难但是你真的理解了吗❓函数怎么执行的我们这里以前序遍历为例
前序遍历递归图解 除了这三种遍历的方式二叉树还有层序遍历 层序遍历除了先序遍历、中序遍历、后序遍历外还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1层序遍历就是从所在二叉树的根节点出发首先访问第一层的树根节点然后从左到右访问第2层上的节点接着是第三层的节点以此类推自上而下自左至右逐层访问树的结点的过程就是层序 如何实现层序遍历❓
我们可以借用一个队列把结点代入队列 不为空出队列在把孩子带入队列在出队列在把孩子代入如此往复直到结点全部出队列即队列为空层序遍历结束。简单来说就是上一层结点出的时候带入下一层结点。这里用C语言实现所以我们首先是要去手写一个队列。
//二叉树
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;//队列用链表实现data的类型是BTNode*
typedef BTNode* QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;
}Queue;void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);void QueueInit(Queue* pq)
{assert(pq);pq-head pq-tail NULL;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-head;while (cur){QNode* next cur-next;free(cur);cur next;}pq-head pq-tail NULL;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){printf(malloc fail\n);exit(-1);}newnode-data x;newnode-next NULL;if (pq-tail NULL){pq-head pq-tail newnode;}else{pq-tail-next newnode;pq-tail newnode;}
}
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq-head-next NULL){free(pq-head);pq-head pq-tail NULL;}else{QNode* next pq-head-next;free(pq-head);pq-head next;}
}QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-head-data;
}QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-tail-data;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq-head NULL;
}int QueueSize(Queue* pq)
{assert(pq);QNode* cur pq-head;int size 0;while (cur){size;cur cur-next;}return size;
}//层序遍历
void TreeLevelOrder(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);}printf(\n);QueueDestroy(q);
}我们不妨来测试上面的层序遍历 DFS 深度优先遍历——前序
BFS广度优先遍历——层序
这里有一个小问题根据前序和中序中序和后序也可以一定要有中序重建一棵树 4.2其他操作
结点个数
int TreeSize(BTNode* root)
{if (root NULL)return;return TreeSize(root-left) TreeSize(root-right) 1;
}叶结点个数
//叶子结点个数
int TreeLeafSize(BTNode* root)
{if (root NULL)return 0;if (root-left NULL root-right NULL)return 1;return TreeLeafSize(root-left) TreeLeafSize(root-right);
}高度
//高度
int TreeHeight(BTNode* root)
{if (root NULL)return 0;int left TreeHeight(root-left);int right TreeHeight(root-right);return left right ? left 1 : right 1;
}求第K层结点个数
//求第K层结点个数
int TreeKLevel(BTNode* root, int k)
{assert(k 0);if (root NULL)return 0;if (k 1)return 1;return TreeKLevel(root-left, k - 1) TreeKLevel(root-right, k - 1);
}返回x所在的结点
//返回X所在的结点
BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root NULL)return NULL;if (root-data x)return root;//先去左树找BTNode* left TreeFind(root-left, x);if (left ! NULL)return left;//左树找不到在去右树找BTNode* right TreeFind(root-right, x);if (right ! NULL)return right;return NULL;
}销毁
void BinaryTreeDestory(BTNode* root)
{if (root NULL){return;}BinaryTreeDestory(root-left);BinaryTreeDestory(root-right);free(root);
}通过主函数来调用测试上面的几个函数接口
int main()
{BTNode* root CreatTree();PreOrder(root);printf(\n);InOrder(root);printf(\n);PostOrder(root);printf(\n);printf(Size:%d\n, TreeSize(root));printf(LeafSize:%d\n, TreeLeafSize(root));printf(TreeHeight:%d\n, TreeHeight(root));printf(TreeKLevel:%d\n, TreeKLevel(root,1));printf(Tree Find:%p\n, TreeFind(root, 6));BinaryTreeDestory(root);rootNULL;return 0;
}4.3判断完全二叉树
我们该怎么去判断是否为完全二叉树呢❓这就可以用到我们上面说的层序遍历了
我们一层一层地走对于完全二叉树来说一层一层地走遇到空以后后面就不会有非空了因为完全二叉树是从左到右依次连续的有非空的话那就不是完全二叉树了。
//判断是否为完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);if (front NULL){break;}QueuePush(q, front-left);QueuePush(q, front-right);}//遇到空以后后面全是空——完全二叉树while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);if (front ! NULL){QueueDestory(q);return false;}}QueueDestroy(q);return true;
}5.总结 我们从树的概念开始了解了树的相关知识、以及引出了二叉树的概念了解二叉树的一些性质通过二叉树的顺序存储我们又认识了堆堆的主要算法是向上调整算法以及向下调整算法以及说了堆的应用堆排序以及TOP-K问题以及根据TOP-K解决实际的OJ题。最后还说了二叉树的遍历操作以及一些函数接口但是在这个地方我们并没有说得那么详细对于二叉树的了解还是比较基础的还存在许多的内容我们没有展开出来。后面会把这一部分内容补充完整。同时对于二叉树有了一定的了解之后我们可以去多做一些OJ题目了没事就去多刷刷题目。这次博客就先到这里结束了。
