【数据结构】二叉树与堆
文章目录
- 1.树概念及结构
- 1.1树的相关概念
- 1.2树的结构
- 2.二叉树概念及结构
- 2.1相关概念
- 2.2特殊的二叉树
- 2.3二叉树的性质
- 2.4二叉树的存储结构
- 3.二叉树的顺序结构及实现
- 3.1二叉树的顺序结构
- 3.2堆的概念
- 3.3堆的实现
- Heap.h
- Heap.c
- 3.4堆的应用
- 3.4.1 堆排序
- 3.4.2 TOP-K
- OJ题
- 最小K个数
- 4.二叉树链式结构的实现
- 4.1遍历操作
- 4.2其他操作
- 4.3判断完全二叉树
- 5.总结
1.树概念及结构
1.1树的相关概念
树的概念:树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的
- 有一个特殊的结点,称为根结点,根节点没有前驱结点
- 除根节点外,其余结点被分成M(M>0)个互不相交的集合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的子孙
森林:由m(m>0)棵互不相交的树的集合称为森林
概念的知识很多,但是我们还是需要去理解!
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个结点的满二叉树的深度,h=long(n+1) . (ps:是log以2为底,n+1为对数)
-
对于具有n个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节点从0开始编号,则对于序号为i的结点有 :
1.若i>0,i位置节点的双亲序号:(i-1)/2;i=0,i为根节点编号,无双亲节点
2.若2i+1<n,左孩子序号:2i+1,2i+1>=n否则无左孩子
3.若2i+2<n,右孩子序号:2i+2,2i+2>=n否则无右孩子
了解完二叉树的性质之后,我们不妨来做几道选择题:
1.某二叉树共有 399 个结点,其中有 199 个度为 2 的结点,则该二叉树中的叶子结点数为( )
A 不存在这样的二叉树
B 200
C 198
D 199
答案:B。n0 = n2+1,既n0=199+1 = 200
2.下列数据结构中,不适合采用顺序存储结构的是( )
A 非完全二叉树
B 堆
C 队列
D 栈
答案:A。
3.在具有 2n 个结点的完全二叉树中,叶子结点个数为( )
A n
B n+1
C n-1
D n/2
答案:A。总结点数n = n0+n1+n2;又n2 = n0-1,既n=n0+n1+n0-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 = n0+n1+n0-1;n1为0或者1,代入能整除的选B
2.4二叉树的存储结构
二叉树一般可以使用两种结构存储,一种顺序结构,一种链式结构
- 顺序存储
顺序结构存储就是使用数组来存储,一般使用数组只适合表示完全二叉树,因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储,下面我们会说到。二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树
- 链式存储
二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链,当前我们使用的是二叉链
3.二叉树的顺序结构及实现
3.1二叉树的顺序结构
普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结
构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储。
3.2堆的概念
如果有一个关键码的集合K ={K0,K1,K2,…Kn-1};把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中,并满足:Ki<=K2i+1并且Ki<=K2i+2,i = 0,1,2…,则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。
- 堆中某个节点的值总是不大于或不小于其父节点的值
- 堆总是一棵完全二叉树
我们来做一道选择题试一试:
下列关键字序列为堆的是:()
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.h>typedef 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(parent>=0)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 (minchild+1<n&&a[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,利用向上调整建堆——O(N*logN)//直接插入/*for (int i = 1; i < n; i++){AdjustUp(a, i);}*///建完堆之后无序,我们排个序//建堆——向下调整建堆(从最后一个节点的父亲开始,开始向下调整,直到根)——O(N)for (int i = (n-1-1)/2; i>=0; i--){AdjustDown(a, n, i);}
两种的时间复杂度不一样:向上调整建堆的时间复杂度是O(N*logN);向下调整建堆的时间复杂度是O(N)。所以我们选用的是向下调整算法进行建堆,关于向下调整算法时间复杂度的推导过程:
因此:建堆的时间复杂度为O(N)。
关于向上调整算法时间复杂度的推导过程(注意红色部分,这就是这两种的区别):
了解完以后,我们来实现堆排序:
//O(N*longN)
//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{//最小的默认为左孩子int minchild = 2 * parent + 1;while (minchild <n){//找出小的那个孩子if (minchild+1<n&&a[minchild+1] < 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; i>=0; 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*2+1;while(minchild<n){if(minchild+1<n&&a[minchild+1]>a[minchild]){minchild++;}if(a[minchild]>a[parent]){Swap(&a[minchild],&a[parent]);parent = minchild;minchild = parent*2+1;}else{break;}}}
int* smallestK(int* arr, int arrSize, int k, int* returnSize){if(k==0){*returnSize = 0;return NULL;}int *minHeap = (int*)malloc(sizeof(int)*(k));for(int i = 0;i<k;i++){minHeap[i] = arr[i];}//前K个数建大堆for(int j = (k-1-1)/2;j>=0;j--){AdjustDown(minHeap,k,j);}//后N-K个数进入for(int i = k;i<arrSize;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);root=NULL;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题目了,没事就去多刷刷题目。这次博客就先到这里结束了。🌹
相关文章:
【数据结构】二叉树与堆
文章目录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.二叉…...
Git图解-常用命令操作-可视化
目录 一、前言 二、初始化仓库 2.1 设置用户名与邮箱 2.2 初始化仓库 三、添加文件 四、查看文件状态 五、查看提交日志 六、查看差异 七、版本回退 八、删除文件 九、分支管理 9.1 创建分支 9.2 切换分支 9.3 查看分支 9.4 合并分支 十、文件冲突 十一、转视…...
C语言-基础了解-20-typedef
typedef 一、typedef C 语言提供了 typedef 关键字,您可以使用它来为类型取一个新的名字。下面的实例为单字节数字定义了一个术语 BYTE: typedef unsigned char BYTE; 在这个类型定义之后,标识符 BYTE 可作为类型 unsigned char 的缩写&…...
Ubuntu系统升级16.04升级18.04
一、需求说明 作为Linux发行版中的后起之秀,Ubuntu 在短短几年时间里便迅速成长为从Linux初学者到实验室用计算机/服务器都适合使用的发行版,目前官网最新版本是22.04。Ubuntu16.04是2016年4月发行的版本,于2019年4月停止更新维护。很多软件支…...
CM6.3.2启用Kerberos(附问题解决)
基础准备支持JCE的jdk重新安装JCE的jdk(已正确配置跳过)删除/usr/java/下面的jdk,然后通过CM->管理->安全->安装Java无限制...重新安装后,配置Java(可选)主机->主机配置->搜java->Java主目录 配置路径主机->所有主机->设置->高级:Java配置Kerberos安…...
QML 动画(组合动画)
在QML中,可以把多个动画组合成一个单一的动画。 组合动画的类型: ParallelAnimation 动画同时进行(并行)SequentialAnimation 动画按照顺序执行(顺序执行)注意:将动画分组为“顺序动画”或“…...
【PHP代码注入】PHP代码注入漏洞
漏洞原理RCE为两种漏洞的缩写,分别为Remote Command/Code Execute,远程命令/代码执行PHP代码注入也叫PHP代码执行(Code Execute)(Web方面),是指应用程序过滤不严,用户可以通过HTTP请求将代码注入到应用中执行。代码注入(代码执行)…...
Python 常用语句同C/C++、Java的不同
文章目录前言1. 数字 int2. 字符 string3. 列表 List4. 元组 tuple5. 字典 dictionary6. 集合 set7. 值类型变量与引用类型变量8. if elif else9. >、<、>、<、、!10. while11. for前言 本篇为本人前段时间的一个简单汇总,这里可能并不齐全,…...
一把火烧掉了苹果摆脱中国制造的幻想,印度制造难担重任
这几年苹果不断推动印度制造,希望摆脱对中国制造的依赖,然而近期苹果在印度的一家代工厂发生大火却证明了苹果的这一计划遭受重大打击,印度制造根本就无法中国制造。一、印度制造屡屡发生幺蛾子苹果推动印度制造已有多年了,然而印…...
常用的 JavaScript 数组 API
以下是一些常用的 JavaScript 数组 API 的代码示例: 1、push() push(): 在数组末尾添加一个或多个元素,返回新的数组长度 const arr [1, 2, 3]; const newLength arr.push(4, 5); console.log(arr); // [1, 2, 3, 4, 5] console.log(newLength); //…...
海思3531a pjsip交叉编译
学习文档: PJSUA2 Documentation — PJSUA2 Documentation 1.0-alpha documentationhttps://www.pjsip.org/docs/book-latest/html/index.html ./configure --prefix/opensource/pjproject-2.12/build3531a \ --host/opt/hisi-linux/x86-arm/arm-hisi…...
《安富莱嵌入式周报》第305期:超级震撼数码管瀑布,使用OpenAI生成单片机游戏代码的可玩性,120通道逻辑分析仪,复古电子设计,各种运动轨迹函数源码实现
往期周报汇总地址:嵌入式周报 - uCOS & uCGUI & emWin & embOS & TouchGFX & ThreadX - 硬汉嵌入式论坛 - Powered by Discuz! 说明: 谢谢大家的关注,继续为大家盘点上周精彩内容。 视频版: https://www.bi…...
力扣-查找每个员工花费的总时间
大家好,我是空空star,本篇带大家了解一道简单的力扣sql练习题。 文章目录前言一、题目:1741. 查找每个员工花费的总时间二、解题1.正确示范①提交SQL运行结果2.正确示范②提交SQL运行结果3.正确示范③提交SQL运行结果4.正确示范④提交SQL运行…...
企业级信息系统开发学习笔记1.8 基于Java配置方式使用Spring MVC
文章目录零、本节学习目标一、基于Java配置与注解的方式使用Spring MVC1、创建Maven项目 - SpringMVCDemo20202、在pom.xml文件里添加相关依赖3、创建日志属性文件 - log4j.properties4、创建首页文件 - index.jsp5、创建Spring MVC配置类 - SpringMvcConfig6、创建Web应用初始…...
【C语言复习】C语言中的文件操作
C语言中的文件操作写在前面文件操作什么是文件文件的分类文件名文件的操作文件指针文件的打开和关闭文件的顺序读写文件的随机读写fseekftellrewindfeof写在前面 文件操作在C语言部分只是属于了解内容,但是因为它可能会应用在项目中,所以我把它单独写成…...
00后整顿职场,当摸鱼测试员遇上了内卷00后。
在程序员职场上,什么样的人最让人反感呢? 是技术不好的人吗?并不是。技术不好的同事,我们可以帮他。 是技术太强的人吗?也不是。技术很强的同事,可遇不可求,向他学习还来不及呢。 真正让人反感的,是技术平平&…...
程序员的上帝视角(4)——视角
对于开发人员来说,工作都是从评估一个需求开始。我们第一个要解决的问题就是看待需求的视角。视角的不同,得到的设计方案可能是完全不同的。作为一个程序员,不能单单从个人视角来看待问题。而是要尝试从不同角色出发,不停思考。上…...
一、webpack基础
webpack基础 一、webpack是什么 webpack 是一个用于现代 JavaScript 应用程序的静态模块打包工具。 说白了webpack就是一个构建和管理静态资源的工具,在我们使用框架开发时,它会在我们内部的一个或者多个入口根据我们引入的各个模块将他们根据一定的规…...
超详细VMware CentOS7(最小安装)安装教程
前言:在我们使用虚拟机的时候,不要去担心我们的一些操作会使虚拟机损坏或者有没有可能会使我们的电脑本身出现一些问题,要记住无论我们把我们的虚拟机如何都不会影响我们本身的机器,因为它只是虚拟的,在虚拟机里不要担…...
经典卷积模型回顾8—NIN实现图像分类(matlab)
首先,介绍一下NiN(Network In Network)模型。NiN模型是由加州大学伯克利分校的Lin、Chen、Yan等人在2013年提出的一种深度卷积神经网络模型,其特点是在传统的卷积神经网络中加入了多个小的全连接网络,用于对特征进行非…...
【Java笔记】泛型
本章专题与脉络 泛型概述 生活中的例子 举例1:中药店,每个抽屉外面贴着标签 举例2:超市购物架上很多瓶子,每个瓶子装的是什么,有标签 举例3:家庭厨房中: Java中的泛型,就类似于上…...
【Linux】用户管理
😊😊作者简介😊😊 : 大家好,我是南瓜籽,一个在校大二学生,我将会持续分享C/C相关知识。 🎉🎉个人主页🎉🎉 : 南瓜籽的主页…...
深入理解Mysql索引底层数据结构与算法
索引是帮助MySQL高效获取数据的排好序的数据结构 深入理解Mysql索引底层数据结构与算法1.常见的数据结构讲解1.1 二叉树1.1.1 二叉树的定义1.1.2 二叉树示例1.1.3 Mysql为什么不使用二叉树进行数据存储1.2 红黑树1.2.1 红黑树的定义1.2.2 红黑树示例1.2.3 Mysql 为什么不适用红…...
【SpringBoot高级篇】SpringBoot集成jasypt 配置脱敏和数据脱敏
【SpringBoot高级篇】SpringBoot集成jasypt数据脱敏配置脱敏使用场景配置脱敏实践数据脱敏pomymlEncryptMethodEncryptFieldEncryptConstantEncryptHandlerPersonJasyptApplication配置脱敏 使用场景 数据库密码直接明文写在application.yml配置中,对安全来说&…...
JAVA知识体系(二)
分布式: 微服务之间的通信 当前我们微服务架构中,微服务之间使用的三种通讯方式:代理访问,feign请求,消息队列 其中代理访问我们使用的是netflix-zuul,只要是对外暴露请求的所有网关,主要用在…...
Verilog 学习第八节(数码管段码显示)
共阴极数码管:低电平端接的都是0,高电平端哪里设置为1 ,哪里就亮~ 共阳极数码管与之相反~ 视觉暂留: 对于三位的共阴极数码管 第0.01s:让数码管0的a段亮,其他数码管全灭 Sel0为高电平,sel1和sel…...
方案开发|快递吊钩电子秤方案
物流的发展为我们提供了生活的便利,足不出户仍可以感受天南地北的美食的特产,在现在这个时代已经是现实并发展成为常态的事情了。在物流发展的每一个环节中,吊钩电子秤也是它必不可缺的一环。人们在寄出物品前需要通过吊钩电子秤称量过重量&a…...
Spring-IOC容器初始化过程
Spring IOC容器的初始化过程:Resource定位,BeanDefinition载入,向IOC容器注册BeanDefinition。整个过程由refresh()方法触发,三个过程由不同的模块完成,使用户更加灵活的对这三个过程剪裁和扩展。 BeanDefinition 就是POJO对象在IOC容器中的抽象。通过BeanDefinition 这个…...
AspCms标签手册
网站通用标签{aspcms:sitepath} 网站终极目录(可放在二级目录,其它语言则在三级目录){aspcms:languagepath} 语言目录{aspcms:siteurl} 网站地址{aspcms:sitelogo} LOGO地址{aspcms:sitetitle} 网站标题{aspcms:additiontitle} 网站附加标题{aspcms:sitekeywords} 网站关键词{a…...
什么是Netty
一.Netty介绍 1.什么是netty Netty 是由 JBOSS 提供的一个 Java 开源框架。Netty 提供异步的、基于事件驱动的网络应用程序框架,用以快速开发高性能、高可靠性的网络 IO 程序,是目前最流行的 NIO 框架,Netty 在互联网领域、大数据分布式计算…...
策划网站做营销推广/学校教育培训机构
缓存实现的过程以及淘汰旧页面的机制不同,所以会有不同缓存调度方法,就常见的就是FIFO,LRU,LFU缓存过期策略。 1.FIFO(First In First out):先见先出,淘汰最先近来的页面࿰…...
海城 网站建设/营销新闻
连接方法请移步这里 http://www.cnblogs.com/hangxin1940/archive/2013/04/05/3000395.html 这里使用Python的curses包开发cli窗口程序,用来实时刷新传感器的读数 最终的效果 ![gy85](http://images.cnblogs.com/cnblogs_com/hangxin1940/466697/o_GY-85.jpg "gy85")…...
定制网站开发报价/app推广赚钱平台
Java Q&A: 使用Factory Method模式 (转)[more]Java Q&A: 使用Factory Method模式Q: 阅读 "Polymorphism in its purest form" 一文时,我看到了一个不熟悉的术语 "Factory method"。你能解释一下什么是Factory method并说明如何使用它吗…...
安徽网站建设推荐/重庆seo网站建设
1、为什么要自动打包工具? 每修改一个问题,测试都让你打包一个上传fir , 你要clean -> 编译打包 -> 上传fir -> 通知测试。而且打包速度好慢,太浪费时间了。如果有一个工具能自动的帮你做完上面所有的事情,岂…...
临沂住房和城乡建设厅网站/直通车关键词优化口诀
前几天撸项目代码时, 由一个技术点间接牵扯出了这东西. 所以就来总结一下. 深拷贝 拷贝对象每个层级的属性. 作用的对象是 js中引用类型的对象,基本类型没有涉及. 本质上将引用类型的对象在堆上重新开辟一块新的空间进行存放. 1 var p_1 {name: 病猫, age: 22}; 2…...
怎么用flash做网站/如何写好一篇软文
《毕业设计之读书笔记》由会员分享,可在线阅读,更多相关《毕业设计之读书笔记(6页珍藏版)》请在人人文库网上搜索。1、读 书 笔 记建筑基坑支护技术规程读书笔记图书出处与作者:该规程为北京地方标准,由中国土木工程学会、北京市勘…...