【数据结构】堆与二叉树

devtools/2025/3/3 17:30:21/

一、树的概念

1.1 什么是树？

树是一种非线性的数据结构，其由 n 个 ( n >= 0 ) 有限节点所组成的一个有层次关系的集合。之所以称其为树，是因为其逻辑结构看起来像是一颗倒挂的树。

img

在树中，有一个特殊的节点称为根节点（如上图中的 body 节点）

根节点的特色是他没有前驱节点，除了根节点之外的其他节点被分成了 M 个 ( M > 0 ) 互不相交的集合 T 1 、 T 2 、 . . . T m {T_1}、T_2、...T_m T1​、T2​、...Tm​

每一个集合的结构与树类似，我们又称其为子树，每个子树的根节点都有且只有一个前驱节点

我们从图中可以看到树的逻辑结构是一层一层递下去的，因此，树是以递归来实现。

1.2 与树相关的专有名词

节点的度：一个节点的子树个数

​ 以上图为例：body 节点的度为 3 （ul、p、div）

叶节点或终端节点：度为零的节点

​ 以上图为例： li、li、p、img 都是叶节点

分支节点或非终端节点：度不为零的节点

​ 以上图为例：body、ul、div 都是分支节点

双亲节点或父节点：如果一个节点有子节点，则这个节点就是这个子节点的双亲节点

​ 以上图为例：body节点是 ul、p、div 的双亲节点

孩子节点或子节点：一个节点所拥有的子树根节点就是这个节点的孩子节点

​ 以上图为例：body节点的孩子节点为 ul、p、div

兄弟节点：有相同双亲节点的节点

​ 以上图为例：ul的兄弟节点是p和div；li的兄弟节点是li和img

树的度：最大节点的的度就是树的度

​ 以上图为例：最大节点的度是3 （body节点）所以树的度为3

节点的层次：以根节点开始，根为第一层，根节点的子节点为第二层，以此类推

树的高度：就是节点的最大的层次

​ 以上图为例：最大的节点层次是3，所以树的高度是3

堂兄弟节点：双亲在同一层的节点互为堂兄弟

​ 以上图为例 li 和 img 是堂兄弟节点

节点的祖先：从根到该节点所经分支上的所有节点

​ 以上图为例：body是所有节点的祖先

子孙：以某节点为根的子树中任一节点都称为该节点的子孙

​ 以上图为例：除了body节点以外的节点都是body节点的子孙

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

二、二叉树的概念

2.1 概念

二叉树的本质就是树，但二叉树有着自己的特殊性质
在这里插入图片描述

从图中可以看到两个二叉树的性质

  1. 二叉树每个节点的度不会大于2
  2. 二叉树有左右子树之分

二叉树的不同情况
在这里插入图片描述
注意：树可以没有节点，此时就是空树

2-2 特殊二叉树

  1. 满二叉树 （ 图 a ）

    一个二叉树每一层的节点数都是该层的最大值，则这个二叉树就是满二叉树

  2. 完全二叉树 （图 b ）

    一个二叉树每一层的节点依照从左至右的顺序，如果有一层的节点不是该层的最大值，则这个二叉树是完全二叉树

    注意：满二叉树是一个特殊的完全二叉树
    在这里插入图片描述

2-3 二叉树的性质

  1. 若根节点的层数为1，则第 i 层的最大节点数为 2 i − 1 {2^{i-1}} 2i−1

  2. 若根节点的层数为1，则深度为 h 的二叉树最大节点数为 2 h − 1 {2^h - 1} 2h−1

  3. 对任何一棵二叉树, 如果度为 0 其叶节点个数为 n 0 {n_0} n0​ , 度为 2 的分支节点个数为 n 2 {n_2} n2​ ,则有 n 0 = n 2 + 1 {n_0 = n_2 + 1} n0​=n2​+1

  4. 若规定根节点的层数为1，具有 n 个节点的满二叉树的深度， h = l o g 2 ( n + 1 ) {h = log_2(n+1)} h=log2​(n+1)

    注意这里的 log 是以2为底

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

    于序号为 i。的节点有

    （1）若 i > 0，i 位置节点的双亲序号： i − 1 2 {\frac {i-1}{2}} 2i−1​； i=0，i 为根节点编号，无双亲节点

    （2）若 2i+1< n，左孩子序号：2i+1，2i+1 >= n 则无左孩子

    （3）若 2i+2 <n，右孩子序号：2i+2，2i+2 >= n 则无右孩子

2-4 二叉树的存储结构

一般来所，二叉树的存储结构可以分成两种

  1. 顺序存储结构

    顺序存储结构就是利用数组来实现，通常只有完全二叉树才会使用数组来实现，因为如果不是完全二叉树会有空间浪费的问题，在实际当中只有堆会使用到二叉树的顺序存储结构

    虽然物理结构上是数组，但是逻辑结构上还是一棵二叉树
    在这里插入图片描述

  2. 链式存储结构

    链式存储结构就是以链表来表示一棵二叉树，在目前主要以二叉链表来表示，每个节点由数据域（data）、左指针（指向左孩子 – leftchild）、右指针（ 指向右孩子 – rightchild）所组成

    而二叉树的延伸 – 红黑树则以三叉链表来表示，在二叉链表的基础上再加上指向双亲节点的指针
    在这里插入图片描述
    在这里我们主要介绍一般的二叉树

三、堆 （ Heap )

3.1 堆的概念

堆就是将数据以二叉树的顺序存储结构进行实现
且满足 K i < = K 2 ∗ i + 1 {K_i <= K_{2*i+1}} Ki​<=K2∗i+1​ 且 K i < = K 2 ∗ i + 2 {K_i <= K_{2*i+2}} Ki​<=K2∗i+2​ （称为小堆）
或 K i > = K 2 ∗ i + 1 {K_i >= K_{2*i+1}} Ki​>=K2∗i+1​ 且 K i > = K 2 ∗ i + 2 {K_i >= K_{2*i+2}} Ki​>=K2∗i+2​ （称为大堆）

堆的性质

  1. 堆中某个节点的值总是不大于或不小于其父节点的值 （满足大堆或小堆 ）

  2. 堆总是一棵完全二叉树
    在这里插入图片描述

3.2 堆的接口

// 以順序表實現堆
typedef int HeapDatatype;
typedef struct Heap
{HeapDatatype *a; // 用來創建數組int capacity;    // 容量int size;        // 有效數據個數
} HP;
// 初始化
void HeapInit(HP *php);
// 初始化數組（利用一个已存在的数组来建堆）
void HeapInitArray(HP *php, int *a, int n);
// 交換
void Swap(HeapDatatype *x1, HeapDatatype *x2);
// 向上調整
void AdjustUp(HeapDatatype *a, int child);
// 向下調整
void AdjustDown(HeapDatatype *a, int n, int parent);
// 插入數據
void HeapPush(HP *php, HeapDatatype x);
// 刪除數據
void HeapPop(HP *php);
// 取堆頂數據
HeapDatatype HeapTop(HP *php);
// 判斷堆是否為空
bool HeapEmpty(HP *php);
// 堆有效數據的個數
int HeapSize(HP *php);
// 堆銷毀
void HeapDestroy(HP *php);
3.2.1 堆初始化
void HeapInit(HP *php){assert(php);php->a = (HeapDatatype*)malloc(sizeof(HeapDatatype)*4);if(php->a == NULL){perror("malloc fail");return;}php->capacity = 4;php->size = 0;
}
3.2.2 堆初始化（以另一个数组来为堆做初始化）
void HeapInitArray(HP * php,int *a,int n){assert(php);php->a = (HeapDatatype*)malloc(sizeof(HeapDatatype)*n);if(php->a == NULL){perror("malloc fail");return;}php->capacity = n;php->size = n;for(int i = 0;i<n;++i){php->a[i] = a[i];}// 建堆for(int i = (i-2)/2; i >= 0; --i ){AdjustDown(php->a,php->size,i);}  
}
3.2.3 向上调整
void AdjustUp(HeapDatatype*a, int child){// 找双亲节点int parent = (child-1)/2;while(child > 0){if(a[child] > a[parent]){Swap(&a[child],&a[parent]);child = parent;parent = (child-1)/2;}else{break;}}
}
3.2.4 向下调整
void AdjustDown(HeapDatatype*a, int n, int parent){int child = 2*parent + 1;// 判断那个孩子比较大while(child < n){if(child + 1 < n && a[child] < a[child+1]){child++;}if(a[child] > a[parent] ){Swap(&a[child],&a[parent]);parent = child;child = 2*parent+1;}else{break;}}
}
3.2.5 插入数据
void HeapPush(HP *php, HeapDatatype x){assert(php);if(php->capacity == php->size){HeapDatatype* tmp = (HeapDatatype*)realloc(php->a,sizeof(HeapDatatype)*2*php->capacity);if(tmp == NULL){perror("realloc fail");return;}php->a = tmp;php->capacity *= 2;}php->a[php->size++] = x;// 插入之后，要确保依然满足堆的特性，所以要进行向上调整AdjustUp(php->a,php->size-1);
}
3.2.6 删除数据

删除数据的思路
在这里插入图片描述
代码实现

void HeapPop(HP * php){assert(php);Swap(&php->a[0],&php->a[size-1]);php->size--;AdjustDown(php->a,php->size,0);
}
3.2.7 取堆顶的数据
HeapDatatype HeapTop(HP *php){assert(php);return php->a[0];
}
3.2.8 判断堆是否为空
bool HeapEmpty(HP *php){assert(php);return php->size == 0;
}
3.2.9 取堆中有效数据个数
int HeapSize(HP *php){assert(php);return php->size;
}
3.2.10 堆的销毁
void HeapDestroy(HP *php){assert(php);free(php->a);php->a = NULL;php->size = 0;php->capacity = 0;
}

3.3 堆的分析

  1. 堆的时间复杂度：O( n ) – 利用错位相减法可以得到
  2. 堆的空间复杂度：取决于malloc的大小 （ 通常是O(n) ）

3.4 堆的应用

  1. 堆排序

    堆排序的两个步骤

    1. 建堆

      • 如果要排升序 – 建大堆
      • 如果要排降序 – 建小堆

    2. 利用堆删除的思想来完成堆排序

    代码实现

    void HeapSort(int *a, int n){ // n 是有效数据个数// 先建堆（假设我们要排升序）for(int i = 0;i<n;++i){AdjustDown(a,i);}// 升序while(n >= 0){Swap(&a[0],&a[n-1]); // 因为是排升序（建大堆）所以堆顶的数据一定是最大的AdjustDown(a,n,0);--n;}
}

  2. Top-K 问题

    排完序后（这里要排降序），我们就可以取得最大的前 k 个数据

    但如果数据量大的话，直接排序就不是那么好的方法，因此，我们可以采用以下方法

    1. 建堆

      • 求前 k 个最大的数据 – 建大堆

      • 求前 k 个最小的数据 – 建小堆

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

    • 注意替换后如果不满足堆的特性，要进行调整

四、二叉树 （ BinaryTree )

要说明二叉树，我们需要先建一个二叉树，注意当前的创建方法并不是二叉树的真正创建方法，真正的创建方法会在未来更进阶的二叉树中进行说明，当前主要以快速上手二叉树为主

4.1 回顾

我们前面有说到，二叉树是

  1. 空树
  2. 非空：由根节点、根节点的左子树、根节点的右子树组成

从二叉树的逻辑结构不难发现二叉树的实现是以递归来实现的
而对二叉树的增删查改通常不是通过一般的二叉树实现的，所以在这里我们不讨论二叉树的增删查改，我们会利用二叉树的遍历来了解最一般的二叉树

4.2 二叉树的遍历

二叉树的遍历主要问题有四种

  1. 前序遍历：访问顺序 – 根 - 左子树 - 右子树

  2. 中序遍历：访问顺序 – 左子树 - 根 - 右子树

  3. 后序遍历：访问顺序 – 左子树 - 右子树 - 根

  4. 层序遍历：访问顺序 – 依序访问每一层的节点，一层访问完后再访问下一层
    在这里插入图片描述
    层序遍历不仅遍历方式和其他三种不一样，实现方式也与其他三种不一样

4.3 二叉树的遍历（代码实现）

4.3.1 创建节点

因为我们不是以正规的二叉树创建方法实现，所以我们要自己创建二叉树

// 先定义结构体
typedef int BTDatatype;
typedef struct BinaryTreeNode{BTDatatype data; // 存储数据struct BinaryTreeNode* left; // 指向左孩子struct BinaryTreeNode* right; // 指向右孩子
}BTNode;
// 创建节点
BTNode* CreateNode(BTDatatype x){BTNode* node = (BTNode*)malloc(sizeof(BTNode));if(node == NULL){perror("malloc fail");return;}node->data = x;node->left = NULL:node->right = NULL:return node;
}
4.3.2 创建树

创建节点并创建树

BTNode* CreateTree(){// 创建节点BTNode* node1 = CreateNode(1);BTNode* node2 = CreateNode(2);BTNode* node3 = CreateNode(3);BTNode* node4 = CreateNode(4);BTNode* node5 = CreateNode(5);BTNode* node6 = CreateNode(6);node1->left = node2;node1->right = node3;node2->left = node4;node2->right = node5;node3->right = node6; // 这里没有写错，我们让node3没有左孩子return node1;
}
4.3.3 二叉树遍历
// 前序遍历 (我们会把空节点一起打印出来)
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);
}
4.3.4 二叉树的其他接口
// 求二叉树的节点数
// 方法：求得左子树和右子树的节点数后再加1（根节点）
int TreeSize(BTNode* root){if(root == NULL){return;}int lnum = TreeSize(root->left);int rnum = TreeSize(root->right);return lnum + rnum + 1;
}
// 求二叉树的高度
int TreeHeight(BTNode* root){if(root == NULL){return 0;}int lnum = TreeHeight(root->left);int rnum = TreeHeight(root->right);return lnum > rnum ? lnum + 1 : rnum + 1;
}
4.3.4 第k層的節點數
int TreeKLevel(BTNode* root, int k){if(root == NULL){return 0;}if(k == 1){return 1;}int lnum = TreeKLevel(root->left,k-1);int rnum = TreeKLevel(root->right,k-1);return lnum + rnum;
}
4.3.5 寻找值为x的节点（如果有多个值为x的节点则返回第一个节点）
// 思路：先从根节点开始，如果根节点的值不满足我们要找的，就找左子树的节点，如果左子树没有，找右子树的节点
BTNode* BinaryTreeFind(BTNode* root, BTDatatype x){if(root == NULL){return NULL;}if(root->data == x){return root;}// 将左子树的结果保存BTNode* lret = BTNBinaryTreeFind(root->left,x);if(lret){return lret;}// 将右子树的结果保存BTNode* rret = BinaryTreeFind(root->right,x);if(rret){return rret;}// 整个二叉树都没有找到就返回NULLreturn NULL;
}
4.3.6 层序遍历 & 判断一棵树是否是完全二叉树

层序遍历

我们前面有说过，层序遍历的实现和前、中、后序遍历有些不同，在实现层序遍历我们需要用到队列

栈与队列 — 关于队列的代码实现都在这篇博客中，但要注意在二叉树这里的队列的数据类型是BTNode*

如何以队列实现层序遍历？

在这里插入图片描述

队列的特性：先进先出

所以用队列实现层序遍历的步骤

  1. 先 Push 根节点进栈
  2. Pop 队头节点的时候将该节点的左右孩子 Push 到队列中

重要！因为判断是否是完全二叉树也会用到这个概念

// 层序遍历
void LevelOrder(BTNode* root){Queue q;QueueInit(&q);// 如果root不是空，就将根节点Push进队列if(root != NULL){QueuePush(&q,root);}// 当队列不为空时while(!QueueEmpty(&q)){BTNode* front = Queuefornt(&q); // 将对头的节点取出// 打印Printf("%d ", front->data);// 将对头节点的左右孩子 Push 进队列if(root->left){QueuePush(&q,root->left);}if(root->right){QueuePush(&q,root->right);}// 删掉对头的节点QueuePop(&q);}// 结束后要记得销毁队列QueueDestroy(&q);
}

判断一棵树是否是完全二叉树

我们前面说过完全二叉树有一个特性：每一层的节点是依序从左至右的

也就是说我们利用层序遍历的概念，只要空的节点后面存在非空节点，则这棵树就不是完全二叉树

bool BinaryTreeComplete(BTNode* root){Queue q;QueueInit(&q);if(root != NULL){QueuePush(&q,root);}while(!QueueEmpty(&q)){BTNode* front = Queuefront(&q);if(front == NULL){break;}QueuePush(&q,root->left);QueuePush(&q,root->right);QueuePop(&q);}// 第二次循环来判断后面有没有非空while(!QueueEmpty(&q)){BTNode* front = Queuefront(&q);if(front){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}

http://www.ppmy.cn/devtools/164236.html

相关文章

一个滑块可变色的Seekbar

一个滑块可变色的Seekbar

因项目需要&#xff0c;做一个如下图的滑动条&#xff0c;要求如下&#xff1a; 1、滑块跟着进度条改变颜色 2、滑块有白色边和内部颜色组成 大体思路&#xff0c;就是背景需要UI按照需求提供&#xff0c;然后变色时&#xff0c;根据滑动回调动态设置对应的颜色。 直接上代码…
阅读更多...
Oracle 数据库基础入门（二）：深入理解表的约束

Oracle 数据库基础入门（二）：深入理解表的约束

在 Oracle 数据库的学习进程中&#xff0c;表的约束是构建健壮、准确且高效数据库的关键要素。约束如同数据库的 “规则守护者”&#xff0c;它通过对数据的限制&#xff0c;确保了数据的完整性和一致性&#xff0c;就如同交通规则保障道路上车辆行驶的有序性一样。对于 Java 全…
阅读更多...
【算法工程】大模型局限性新发现之解决能连github但无法clone项目的问题

【算法工程】大模型局限性新发现之解决能连github但无法clone项目的问题

最近&#xff0c;linux服务器遇到一个奇怪的问题&#xff0c;能ping通github&#xff0c;但是无法clone git项目&#xff0c;尝试了各种大模型&#xff0c;都提到代理啥的问题&#xff0c;发现没有一个能解决问题。 后来尝试设置 http.sslVerify 为 false&#xff0c;才解决问题…
阅读更多...
c# 代码规范

c# 代码规范

在C#编程中&#xff0c;遵循良好的命名规范是提高代码可读性和可维护性的关键。C# 社区普遍接受一套命名约定&#xff0c;这些约定有助于团队成员之间更好地协作&#xff0c;同时也便于其他开发者阅读和理解你的代码。以下是一些基本的C#命名规范&#xff1a; 在C#编程中&…
阅读更多...
React低代码项目：问卷编辑器 I

React低代码项目：问卷编辑器 I

问卷编辑器 Date: February 20, 2025 4:17 PM (GMT8) 目标 完成问卷编辑器的设计和开发完成复杂系统的 UI 组件拆分完成复杂系统的数据结构设计 内容 需求分析技术方案设计开发 注意事项&#xff1a; 需求指导设计&#xff0c;设计指导开发。前两步很重要页面复杂的话&…
阅读更多...
Python中文自然语言处理库SnowNLP

Python中文自然语言处理库SnowNLP

SnowNLP 介绍 SnowNLP 是一个基于 Python 的中文自然语言处理库&#xff0c;专为处理中文文本而设计。它受到 TextBlob 的启发&#xff0c;但与 TextBlob 不同的是&#xff0c;SnowNLP 没有使用 NLTK&#xff0c;所有的算法都是自己实现的&#xff0c;并且自带了一些训练好的字…
阅读更多...
在Spring Boot项目中将中文转换为拼音：从入门到实践

在Spring Boot项目中将中文转换为拼音：从入门到实践

文章目录 在Spring Boot项目中将中文转换为拼音&#xff1a;从入门到实践引言一、拼音转换的背景与需求1.1 拼音转换的应用场景1.2 技术选型 二、Spring Boot集成pinyin4j2.1 添加依赖2.2 创建拼音工具类2.3 在Spring Boot中使用工具类2.4 编写测试用例 三、实践中的注意事项3.…
阅读更多...
Ubuntu 下 nginx-1.24.0 源码分析 - ngx_init_cycle 函数 - 详解（4）

Ubuntu 下 nginx-1.24.0 源码分析 - ngx_init_cycle 函数 - 详解（4）

详解&#xff08;4&#xff09; 初始化配置转储结构&#xff08;config_dump&#xff09; if (ngx_array_init(&cycle->config_dump, pool, 1, sizeof(ngx_conf_dump_t))! NGX_OK){ngx_destroy_pool(pool);return NULL;}ngx_rbtree_init(&cycle->config_dump_rb…
阅读更多...
最新文章

Copyright @ 2022~2023