0
0

【数据结构】万字二叉树与堆

文章目录

1.树概念及结构

1.1树的相关概念

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

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

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

image-20220809181742844
image-20220809181925803

节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：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树的结构

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法 ：

image-20220809182528111

树在实际中的运用（表示文件系统的目录树结构,网上找的图片） ：

image-20220809183345009

2.二叉树概念及结构

2.1相关概念

一棵二叉树是结点的一个有限集合:

1.或者为空

2.由一个根节点加上两棵别称为左子树和右子树的二叉树组成

image-20220809183538677

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

2.2特殊的二叉树

  • 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是 ，则它就是满二叉树。
  • 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树

看了概念可能不太好理解，我们来看图对比一下就知道区别在哪里了：

image-20220809183826569

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

答案：Bimage-20220809194855914

5.一个具有767个节点的完全二叉树，其叶子节点个数为（）
A 383
B 384
C 385
D 386

答案：B。类似于第3题，总结点n = n0+n1+n0-1;n1为0或者1,代入能整除的选B

2.4二叉树的存储结构

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

  1. 顺序存储 顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，下面我们会说到。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树

image-20220809195550127

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

3.二叉树的顺序结构及实现

3.1二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结
构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储。

image-20220809200130790

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

解析：这里没有明确说明是大堆还是小堆，我们直接在草稿上简单画一下就知道答案了：

image-20220809214454246

3.3堆的实现

Heap.h

#include<stdio.h>#include<assert.h>#include<stdlib.h>#include<time.h>#include<stdbool.h>typedefint HPDataType;typedefstructHeap{
    HPDataType* a;int size;int capacity;}HP;//初始化堆voidHeapInit(HP* php);//销毁堆voidHeapDestory(HP* php);//打印堆voidHeapPrint(HP* php);//插入X继续保持堆形态voidHeapPush(HP* php,HPDataType x);//删除堆顶元素voidHeapPop(HP* php);//判断是否为空
bool HeapEmpty(HP* php);//返回堆顶元素
HPDataType HeapTop(HP* php);//返回堆的元素大小intHeapSize(HP* php);

这就是一些要实现的接口，下面通过Heap.c对以上接口进行说明。

Heap.c

初始化

//初始化voidHeapInit(HP* php){assert(php);
    php->a =NULL;
    php->size = php->capacity =0;}

插入X并保持堆

插入之前是小根堆（假设堆已经创建好，后面会说到堆的创建，不要急，先看这一部分，便于理解，后面堆的创建就简单多了），我们是在尾部把X插入的，然后再进行向上调整（原来必须是大堆或者小堆了）。

比如先插入一个10到数组的尾上 ，再进行向上调整算法，直到满足堆 ：

image-20220809203019107

最后一个位置是：php->size-1.要找到父节点：(child-1)/2,如此我们去比较大小进行交换调整，就能够实现我们的向上调整：

//交换voidSwap(HPDataType* p1, HPDataType* p2){
    HPDataType tmp =*p1;*p1 =*p2;*p2 = tmp;}//向上调整（这里是小堆）voidAdjustUp(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继续保持堆形态voidHeapPush(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);}

我们不妨来测试一下这段代码：

image-20220809214028865

删除堆顶元素

开始之前，想想删除堆顶元素能干什么❓可以找出次大获知次小

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

image-20220809214606723

//向下调整voidAdjustDown(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;}}}//删除堆顶元素——找出次大或者次小voidHeapPop(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];}

元素个数

intHeapSize(HP* php){assert(php);return php->size;}

打印

voidHeapPrint(HP* php){assert(php);for(int i =0; i < php->size; i++){printf("%d ", php->a[i]);}printf("\n");}

销毁

voidHeapDestory(HP* php){assert(php);free(php->a);
    php->a =NULL;
    php->size = php->capacity =0;}

3.4堆的应用

3.4.1 堆排序

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

  1. 建堆 升序：建大堆（如果建小堆的话，小堆不一定有序，只是堆顶最小，那下一个最小的数呢？如何依次选最小的数据？就算是选出来了之后，结点之间的关系就全乱了，无法继续利用优势，只能重新建堆O(N)，选出次小的数据，效率太低了）建大堆直接交换堆顶和最后一个，进行向下调整即可降序：建小堆
  2. 堆利用堆删除思想来进行排序建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。回顾一下向下调整的过程：image-20220809232058329

这里的建堆，是直接用数组进行建堆，可以用向上调整算法进行建堆，也可以利用向下调整建堆，有什么区别？我们先来看代码的实现：

//建堆——a，利用向上调整建堆——O（N*longN）//直接插入/*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*longN）;向下调整建堆的时间复杂度是O（N）。所以我们选用的是向下调整算法进行建堆，关于向下调整算法时间复杂度的推导过程：

image-20220809233233322

因此：建堆的时间复杂度为O(N)。

关于向上调整算法时间复杂度的推导过程（注意红色部分，这就是这两种的区别）：

image-20220809234931329

了解完以后，我们来实现堆排序：

//O(N*longN)//向下调整voidAdjustDown(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;}}}voidHeapSort(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++;}}intmain(){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");return0;}

image-20220810131240864

这里建的是小堆自然是降序。

3.4.2 TOP-K

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大 有人说：简单啊，排个序（NlogN），选出前K个即可。但是：如果数据量非常大，排序就不太可取了 (可能数据都不能一下子全部加载到内存中 )

最佳的方式就是用堆来解决：

  1. 用数据集合中前K个元素来建堆前k个最大的元素，则建小堆(建大堆呢，有什么区别)前k个最小的元素，则建大堆
  2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

image-20220810140711442

代码实现（这里采用前面学的文件的一些函数）：

//创建一个文件，并且随机生成一些数字voidCreateDataFile(constchar* 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个最大的数并且打印voidPrintTopK(constchar* 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);}intmain(){int N =10000;constchar* filename ="Data.txt";int k =10;CreateDataFile(filename, N);PrintTopK(filename, k);return0;}

image-20220810145303781

随机生成10000以内的数字，至此，TOP-K代码的实现到这里结束。下面，我们可以来做一道OJ题目：

OJ题

最小K个数

点我

image-20220810155320284

一看就是上面说的TOP-k问题，直接上手代码：

voidSwap(int*p1,int*p2){int*tmp =*p1;*p1 =*p2;*p2 = tmp;}voidAdjustDown(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;returnNULL;}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;}

image-20220810155403330

4.二叉树链式结构的实现

在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。为了降低学习成本，此处手动快速创建一棵简单的二叉树，这里以简单的实现为主。后续在来讨论其创建方式：

以这颗树为例子：image-20220810163832470

#include<stdio.h>#include<assert.h>#include<stdlib.h>typedefint BTDataType;typedefstructBinaryTreeNode{
    BTDataType data;structBinaryTreeNode* left;structBinaryTreeNode* 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遍历操作

先序、中序、后序遍历递归操作：

//先序voidPreOrder(BTNode* root){if(root ==NULL){printf("NULL ");return;}printf("%d ", root->data);PreOrder(root->left);PreOrder(root->right);}//中序voidInOrder(BTNode* root){if(root ==NULL){printf("NULL ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);}//后序voidPostOrder(BTNode* root){if(root ==NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);}

我们不难发现，二叉树的遍历操作通过递归实现非常地简单，实现并不难，但是函数怎么执行的（我们这里以前序遍历为例）

前序遍历递归图解：

image-20220810165526334

image-20220810165556180

出去这三种遍历的方式，还有层序遍历

层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在
层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层
上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序

层序遍历后面会说，这里先暂时不展开了，这篇博客先说一些比较基础的知识。

4.2其他操作

结点个数

intTreeSize(BTNode* root){if(root ==NULL)return;returnTreeSize(root->left)+TreeSize(root->right)+1;}

叶结点个数

//叶子结点个数intTreeLeafSize(BTNode* root){if(root ==NULL)return0;if(root->left ==NULL&& root->right ==NULL)return1;returnTreeLeafSize(root->left)+TreeLeafSize(root->right);}

高度

//高度intTreeHeight(BTNode* root){if(root ==NULL)return0;int left =TreeHeight(root->left);int right =TreeHeight(root->right);return left > right ? left +1: right +1;}

求第K层结点个数

//求第K层结点个数intTreeKLevel(BTNode* root,int k){assert(k >0);if(root ==NULL)return0;if(k ==1)return1;returnTreeKLevel(root->left, k -1)+TreeKLevel(root->right, k -1);}

返回x所在的结点

//返回X所在的结点
BTNode*TreeFind(BTNode* root, BTDataType x){if(root ==NULL)returnNULL;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;returnNULL;}

通过主函数来调用测试上面的几个函数接口：

intmain(){
    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));return0;}

image-20220810184945477

5.总结

我们从树的概念开始，了解了树的相关知识、以及引出了二叉树的概念，了解二叉树的一些性质，通过二叉树的顺序存储，我们又认识了堆，堆的主要算法是向上调整算法以及向下调整算法，以及说了堆的应用，堆排序以及TOP-K问题，以及根据TOP-K解决实际的OJ题。最后还说了二叉树的遍历操作以及一些函数接口，在这个地方，我们并没有说得那么详细，对于二叉树的了解还是比较基础的。后面会把这一部分内容补充完整。同时，对于二叉树有了一定的了解之后，我们可以去多做一些OJ题目了，没事就去多刷刷题目。这次博客就先到这里结束了。🌹

标签： 数据结构 算法 c语言
本文转载自: https://blog.csdn.net/weixin_60478154/article/details/126272670
版权归原作者 平凡的人1 所有， 如有侵权，请联系我们删除。
登录后发布评论

“【数据结构】万字二叉树与堆”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

安全见闻（9）二进制安全

C++20 STL CookBook2 更强大的编译时 + 安全比较 + spaceship比较符

Linux：login shell和non-login shell以及其配置文件

使用git命令实现对gitee仓库的下载、更新、上传、上传更新操作。

network-magic：网络管理员必备的开源网络管理工具

git-- github的使用

结合Gitee、PicGo和Typora构建一个免费的个人笔记工具

文章导航