数据结构：树形结构（树、堆）详解

Ne0inhk

— 10 min read
数据结构：树形结构（树、堆）详解

数据结构：树形结构（树、堆）详解

一、树

树的物理结构和逻辑结构上都是树形结构

（一）树的性质

• ⼦树是不相交的
• 除了根结点外，每个结点有且仅有⼀个⽗结点
• ⼀棵N个结点的树有N-1条边

（二）树的种类

树按照根节点的分支来分，可以分为二叉树和多叉树。

二叉树

二叉树（Binary Tree）
定义：每个节点最多有两个子节点的树结构。可以是空树，或者由一个根节点和左、右子树组成。

多叉树

多叉树（Multiway Tree）
定义：每个节点可以有多个子节点的树结构，节点子节点的数量没有限制。

树按照结点的特性来观察，又可以有满N叉树和完全N叉树

满N叉树

满N叉树是一种深度为K的二叉树，其中每一层的节点数都达到了该层能有的最大节点数。
在这里插入图片描述

完全N叉树

除了最后一层外，每一层都被完全填满，并且最后一层所有节点都尽量靠左排列。
在这里插入图片描述

（三）二叉树的实现

1、二叉树结构定义

用 typedef 可以使得后面的使用范围更广

typedefint BTDataType;typedefstructBinaryTreeNode{ BTDataType data;structBinaryTreeNode* left;structBinaryTreeNode* right;}BTNode;

2、二叉树功能实现

（1）前序、中序、后序、层序遍历

下面的层序遍历方式采用的是一层一层的处理方式

voidPreOrder(BTNode* root){if(root ==NULL)return;printf("%d ", root->data);PreOrder(root->left);PreOrder(root->right);return;}voidInOrder(BTNode* root){if(root ==NULL)return;InOrder(root->left);printf("%d ", root->data);InOrder(root->right);return;}voidPostOrder(BTNode* root){if(root ==NULL)return;PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);return;}voidLevelOrder(BTNode* root){ queue<BTNode*> q; q.push(root);while(!q.empty()){int num = q.size();for(int i =0; i < num; i++){ BTNode* temp = q.front();if(temp->left) q.push(temp->left);if(temp->right) q.push(temp->right);printf("%d ", temp->data); q.pop();}printf("\n");}return;}
（2）二叉树结点个数

两种方法都可以实现求结点个数，但是第二种需要另外创建变量接收返回值，因此第一种方式比较好

//方法一intBinaryTreeSize(BTNode* root){if(root ==NULL)return0;return1+BinaryTreeSize(root->left)+BinaryTreeSize(root->right);}//方法二voidBinaryTreeSize(BTNode* root,int* psize){if(root ==NULL)return;if(root->left){(*psize)++;BinaryTreeSize(root->left, psize);}if(root->right){(*psize)++;BinaryTreeSize(root->right, psize);}return;}
（3） ⼆叉树叶⼦结点个数

只需要统计叶子结点即可，和求普通结点个数相似

intBinaryTreeLeafSize(BTNode* root){if(root ==NULL)return0;if(root->left ==NULL&& root->right ==NULL)return1;returnBinaryTreeLeafSize(root->left)+BinaryTreeLeafSize(root->right);}
（4） 二叉树第k层结点个数

需要加一个二叉树层数的变量

intBinaryTreeLevelKSize(BTNode* root,int k){if(root ==NULL)return0;if(k ==1)return1;returnBinaryTreeLevelKSize(root->left, k -1)+BinaryTreeLevelKSize(root->right, k -1);}
（5）二叉树的深度/高度
intBinaryTreeDepth(BTNode* root){if(root ==NULL)return0;int a =BinaryTreeDepth(root->left);int b =BinaryTreeDepth(root->right);return(a > b ? a : b)+1;}
（6）⼆叉树查找值为x的结点

如果没有找到，不要忘记返回空

BTNode*BinaryTreeFind(BTNode* root, BTDataType x){if(root ==NULL)returnNULL;if(root->data == x)return root; BTNode* left =BinaryTreeFind(root->left, x);if(left)return left; BTNode* right =BinaryTreeFind(root->right, x);if(right)return right;returnNULL;}
（7）二叉树销毁

采用二级指针的方式传入，可以避免函数处理后在进行置空处理。

voidBinaryTreeDestory(BTNode** root){if(*root ==NULL)return;BinaryTreeDestory(&((*root)->left));BinaryTreeDestory(&((*root)->right));free(*root);*root =NULL;return;}
（8）判断二叉树是否为完全二叉树

这段代码是老夫目前想了许久，觉得很有不错的代码，先不考虑它的实现复杂度以及简洁程度，它实现的功能不错，可以将二叉树包括空结点放在队列之中，自己觉得很好，哈哈，也许你没看到这句，那我就放心了。

bool BinaryTreeComplete(BTNode* root){ queue<BTNode*> q;BinaryTreePushQueue(root, q);while(!q.empty()){if(q.front()!=NULL) q.pop();elsebreak;}while(!q.empty()){if(q.front()==NULL) q.pop();elsereturn false;}return true;}voidBinaryTreePushQueue(BTNode* root, queue<BTNode*>& q){ vector<vector<BTNode*>> v;BinaryNodePushVector(root, v,0);for(int i =0; i < v.size(); i++){for(auto x : v[i]){ q.push(x);}}return;}voidBinaryNodePushVector(BTNode* root, vector<vector<BTNode*>>& v,int k){if(v.size()== k) v.push_back(vector<BTNode*>());if(root ==NULL){ v[k].push_back(NULL);//如果不处理空结点，取消这步即可return;} v[k].push_back(root);BinaryNodePushVector(root->left, v, k +1);BinaryNodePushVector(root->right, v, k +1);return;}

二、堆

堆的物理结构是一段连续空间，但是逻辑机构是树形结构

（一）堆的实现

1、堆的结构定义

下面通过宏函数来实现交换，可以使得交换简便，或者用指针也行。

typedefint HeapDataType;typedefstructHeap{ HeapDataType* __data; HeapDataType* data;int count;int capacity;}Heap;
#defineSWAP(a ,b){\HeapDataType c =(a);\(a)=(b);\(b)=(c);\}

2、堆的初始化

用偏移量的方式，节约了内存。
从数组下标为1开始分配结点，使得后面求父节点，左右孩子运算和逻辑更简单

voidHeapInit(Heap* pHeap){assert(pHeap); pHeap->__data =(HeapDataType*)malloc(sizeof(HeapDataType)); pHeap->data = pHeap->__data -1; pHeap->capacity =1; pHeap->count =0;return;}

3、向上调整操作

可以使用递归或者是循环来实现向上调整

voidHeap_UP_Update(Heap* pHeap,int i){assert(pHeap);while(FATHER(i)>=1&& pHeap->data[FATHER(i)]> pHeap->data[i]){SWAP(pHeap->data[FATHER(i)], pHeap->data[i]); i =FATHER(i);}return;}voidDG_Heap_UP_Update(Heap* pHeap,int i){assert(pHeap);if(FATHER(i)<1)return;if(pHeap->data[FATHER(i)]> pHeap->data[i]){SWAP(pHeap->data[FATHER(i)], pHeap->data[i]); i =FATHER(i);DG_Heap_UP_Update(pHeap, i);}return;}

4、向下调整操作

voidHeap_DOWN_Update(Heap* pHeap,int i){assert(pHeap);int size = pHeap->count -1;while(LEFT(i)<= size){int l =LEFT(i), r =RIGHT(i), ind = i;if(pHeap->data[ind]> pHeap->data[l]) ind = l;if(r <= size && pHeap->data[ind]> pHeap->data[r]) ind = r;if(ind == i)break;SWAP(pHeap->data[i], pHeap->data[ind]); i = ind;}return;}

5、入堆操作

voidHeapPush(Heap* pHeap, HeapDataType x){assert(pHeap);HeapCheckCapacity(pHeap); pHeap->data[pHeap->count +1]= x;DG_Heap_UP_Update(pHeap, pHeap->count +1); pHeap->count +=1;return;}

6、堆的扩容

voidHeapCheckCapacity(Heap* pHeap){assert(pHeap);if(pHeap->capacity == pHeap->count){ HeapDataType* temp =(HeapDataType*)realloc(pHeap->__data,2* pHeap->capacity *sizeof(HeapDataType));if(!temp){perror("Heap Realloc Fail!");exit(1);} pHeap->__data = temp; pHeap->capacity *=2;}return;}

7、出堆操作

voidHeapPop(Heap* pHeap){assert(pHeap);assert(!HeapEmpty(pHeap)); pHeap->data[1]= pHeap->data[pHeap->count];Heap_DOWN_Update(pHeap,1); pHeap->count -=1;return;}

8、堆的销毁

voidHeapDestroy(Heap* pHeap){assert(pHeap);free(pHeap->__data); pHeap->data =NULL; pHeap->__data =NULL; pHeap->capacity =0; pHeap->count =0;return;}

9、堆的判空、查看堆顶元素

intHeapEmpty(Heap* pHeap){assert(pHeap);return pHeap->count ==0;} HeapDataType HeapTop(Heap* pHeap){assert(!HeapEmpty(pHeap));return pHeap->data[1];}

（二）哈夫曼编码实现

#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib.h>#include<time.h>#include<string.h>#include<algorithm>#include<unordered_map>#include<vector> using namespace std;#defineFATHER(i)((i)/2)#defineLEFT(i)((i)*2)#defineRIGHT(i)((i)*2+1)typedefstructNode{char* c;int freq;structNode* lchild,* rchild;}Node; template<typename T>voidSwap(T& a, T& b){ T c = a; a = b; b = c;return;}//void swap(Node* a, Node* b) {// Node* c = a;// a = b;// b = c;// return;//} Node*getNewNode(int freq,constchar* c){ Node* p =(Node*)malloc(sizeof(Node)); p->freq = freq; p->c =_strdup(c); p->lchild = p->rchild =NULL;return p;}voidclear(Node* root){if(root ==NULL)return;clear(root->lchild);clear(root->rchild);free(root);return;}typedefstructheap{ Node** data,**__data;int size, count;}heap; heap*initHeap(int n){ heap* p =(heap*)malloc(sizeof(heap)); p->__data =(Node**)malloc(sizeof(Node*)* n); p->data = p->__data -1; p->size = n; p->count =0;return p;}intempty(heap* h){return h->count ==0;}intfull(heap* h){return h->count == h->size;} Node*top(heap* h){if(empty(h))returnNULL;return h->data[1];}//void up_update(Node** data, int i) {// while (FATHER(i) >= 1) {// int ind = i;// if (data[i]->freq < data[FATHER(i)]->freq) {// swap(data[i], data[FATHER(i)]);// }// if (ind == i) break;// i = FATHER(i);// }// return;//}voidup_update(Node** data,int i){while(i >1&& data[i]->freq < data[FATHER(i)]->freq){Swap(data[i], data[FATHER(i)]); i =FATHER(i);}return;}voiddown_update(Node** data,int i,int n){while(LEFT(i)<= n){int ind = i, l =LEFT(i), r =RIGHT(i);if(data[i]->freq > data[l]->freq) ind = l;if(RIGHT(i)<= n && data[r]->freq < data[ind]->freq) ind = r;if(ind == i)break;Swap(data[ind], data[i]); i = ind;}return;}voidpush(heap* h, Node* node){if(full(h))return; h->count +=1; h->data[h->count]= node;up_update(h->data, h->count);return;}voidpop(heap* h){if(empty(h))return; h->data[1]= h->data[h->count]; h->count -=1;down_update(h->data,1, h->count);return;}voidclearHeap(heap* h){if(h ==NULL)return;free(h->__data);free(h);return;} Node*build_huffman_tree(Node** nodeArr,int n){ heap* h =initHeap(n);for(int i =0; i < n; i++){push(h, nodeArr[i]);} Node* node1,* node2;int freq;for(int i =1; i < n; i++){ node1 =top(h);pop(h); node2 =top(h);pop(h); freq = node1->freq + node2->freq; Node* node3 =getNewNode(freq,"0"); node3->lchild = node1; node3->rchild = node2;push(h, node3);}return h->data[1];}voidoutput(Node* root){if(root ==NULL)return;output(root->lchild);//if (root->lchild == NULL && root->rchild == NULL) printf("%s : %d\n", root->c, root->freq);output(root->rchild);return;}char charArr[100]; unordered_map<char*,char*> h;voidextract_huffman_code(Node* root,int i){ charArr[i]=0;if(root->lchild ==NULL&& root->rchild ==NULL){ h[root->c]=_strdup(charArr);return;} charArr[i -1]='0';extract_huffman_code(root->lchild, i +1); charArr[i -1]='1';extract_huffman_code(root->rchild, i +1);return;}intmain(){#defineMAX_CHAR26//1.首先用一个数组读取相关字符串及其频率 Node** charArr =(Node**)malloc(sizeof(Node*)*MAX_CHAR);char arr[10];int freq;for(int i =0; i < MAX_CHAR;i++){scanf("%s%d", arr,&freq); charArr[i]=getNewNode(freq, arr);}//2.建立哈夫曼树 Node* root =build_huffman_tree(charArr, MAX_CHAR);//3.提取哈夫曼编码进入unordered_mapextract_huffman_code(root,1);//4.将unordered_map转换成vector排序，可以按照字典序输出编码 vector<pair<char*,char*>>v(h.begin(), h.end());sort(v.begin(), v.end(),[&](const pair<char*,char*>& a,const pair<char*,char*>& b){returnstrcmp(a.first, b.first)<0;});for(auto& x : v){printf("%s : %s\n", x.first, x.second);}return0;}
在这里插入图片描述

结束语

关注博主的专栏，博主会分享更多的数据结构知识！
🐾博主的数据结构专栏

在这里插入图片描述

Read more

HarmonyOS应用开发实战（基础篇）Day07-《登录注册页面》

HarmonyOS应用开发实战（基础篇）Day07-《登录注册页面》

设计：从零构建一个专业级登录页面 在移动应用开发中，登录/注册页面是用户与系统建立身份关联的第一道门户，其设计质量直接影响用户的第一印象与使用体验。本文将基于 ArkTS 与 HarmonyOS 的 ArkUI 框架，从 UI 设计到交互逻辑，完整实现一个简洁、安全、响应式的登录页面。 一、设计目标与视觉规范 根据需求草图，我们的登录页面需包含以下核心元素： * 顶部 Logo：品牌标识，增强识别度； * 账号输入框：支持文本输入，带占位提示； * 密码输入框：密文显示，保障安全； * 操作按钮组：包含“登录”与“取消”两个功能按钮； * 交互反馈：输入校验、加载状态、跳转逻辑。 整体风格遵循 HarmonyOS 设计语言（HUAWEI Design）： * 使用 vp

By Ne0inhk
Flutter 三方库 highlight 构建鸿蒙跨端开发者社区全量编程语言高亮适配研究：兼容各类型复杂文本节点正则表达式切割引擎、移动端极客视觉质感高定体验-适配鸿蒙 HarmonyOS ohos

Flutter 三方库 highlight 构建鸿蒙跨端开发者社区全量编程语言高亮适配研究：兼容各类型复杂文本节点正则表达式切割引擎、移动端极客视觉质感高定体验-适配鸿蒙 HarmonyOS ohos

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.ZEEKLOG.net Flutter 三方库 highlight 构建鸿蒙跨端开发者社区全量编程语言高亮适配研究：极限兼容各类型复杂文本节点正则表达式切割引擎、全栈重塑移动端极客阅读展示视觉质感高定体验 前言 在 OpenHarmony 的专业技术文档、代代码代码编辑器或者是社区学习类应用中，能够优雅、清晰地展示各种编程语言的代码片段，是业务质量的直接体现。普通的富文本标签在处理复杂的语法高亮（Syntax Highlighting）时不仅效率低下，且配色失准。highlight 库为 Flutter 开发者提供了一套支持全语言、高性能的语法高亮引擎。本文将带大家在鸿蒙端实战接入，实现“像素级”的技术排版。 一、原直线性 / 概念介绍 1.1 基础原理/概念介绍 highlight 的核心逻辑是基于 词法模式匹配（Lexical Pattern Matching）与主题样式的动态映射。它不仅依赖简单的关键字匹配，更通过各语言专有的正则表达式集（Modes）

By Ne0inhk

Ubuntu 26.04 LTS“坚毅浣熊”(Resolute Raccoon) 新特性前瞻

Ubuntu 26.04 LTS 发布计划与新功能详解 * 发布计划与生命周期 * 1.1 关键时间节点 * 1.2 支持周期 * 核心系统与桌面环境 * 2.1 GNOME 50：全面进入 Wayland 时代 * 核心变化 * NVIDIA Wayland 性能大幅优化 * 2.2 Linux 内核：6.20 或 7.0 * 2.3 系统核心组件 * 开发工具链全面升级 * 3.1 编译器工具链 * GCC 15 编译器套件 * 完整工具链更新 * 3.2 大规模重编译保障系统一致性 * 3.3 Web

By Ne0inhk

Flutter for OpenHarmony: Flutter 三方库 pedantic_mono 引入最严格的代码静态审计规范（鸿蒙项目代码质量卫士）

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.ZEEKLOG.net 前言 在进行 OpenHarmony 项目开发，尤其是多人协作的大型工程时，“代码风格不统一”和“潜在逻辑风险”是性能和维护的双重杀手。虽然 Dart 官方提供了 lints 包，但其约束力往往较弱。 pedantic_mono 是一套极度严格、由社区资深开发者维护的统计审计（Lint）规则集。它不仅包含了基础的排版规范，更深入到了异步安全（Async Safely）、集合操作性能以及代码健壮性等多个维度。引入它，就像是为你的鸿蒙项目请来了一位 24 小时待命的“代码审计专家”。 一、核心审计范围图 pedantic_mono 覆盖了从变量命名到高阶逻辑的每个角落。 pedantic_mono 规则库 基础规范 (命名/排序) 异步安全 (忘记 await/

By Ne0inhk