树与二叉树学习笔记
树与二叉树
- 计算机中的树
- 树的概念
- 树的类型
- 什么是二叉树
- 二叉树:定义与特点
- 二叉树:前序、中序、后序遍历
- 二叉树:深度、广度优先遍历
- 二叉树:线索化
- 二叉树:序列化与反序列化
- haffman树
- 平均编码长度
- 构建haffman树
- haffman树:代码演示
计算机中的树
树的概念
计算机中的树与现实生活中的树结构是类似的,但是计算机中的树型结构更加抽象化。在计算机中的树型结构具备以下几个特点:
- 除了根节点,每个结点都具有唯一父节点。
- 每个结点可以有若干个子节点。
- 树型结构具备层次关系。
- 边与结点之间,具备无循环的特性。
树的类型
-
二叉树(Binary Tree):
每个节点最多有两个子节点,通常称为左子节点和右子节点。
-
多叉树
每个节点最多不止有两个子节点,比如说字典树、和双数组字典树。
什么是二叉树
二叉树:定义与特点
- 每个结点最多只有两个子节点。
- 遍历和结构操作方便。
- 满足递归的基本性质,相关操作可以借助递归方式完成。
- 二叉树在计算机领域应用广泛。
二叉树:前序、中序、后序遍历
- 前序遍历
所谓前序遍历,指的就是遍历顺序按照:根、左、右 的方式进行。
// typedef struct Node {// int val;// struct Node *left, *right; // } Node;void preOrder(Node *root) {if (root == NULL) return ;printf("%d ", root->val);preOrder(root->left);preOrder(root->right);return ;}
- 中序遍历
中序遍历的遍历顺序按照:左、根、右 的方式进行。
// typedef struct Node {
// int val;
// struct Node *left, *right;
// } Node;void inOrder(Node *root) {if (root == NULL) return ;inOrder(root->left);printf("%d ", root->val);inOrder(root->right);return ;
}
- 后序遍历
后序遍历的遍历顺序是按照:左、右、根的方式
// typedef struct Node {
// int val;
// struct Node *left, *right;
// } Node;void lastOrder(Node *root) {if (root == NULL) return ;lastOrder(root->left);lastOrder(root->right);printf("%d ", root->val);return ;
}
二叉树:深度、广度优先遍历
- 深度优先遍历(DFS)
深度优先遍历,其遍历方式就是,沿着其中一条路径一直走到底,当无路可走时,就需要按照原来的路径回退一步,继续搜索其他结点,重复原来的操作。(不撞南墙不回头)
// typedef struct Node {
// int key;
// struct Node *lchild, *rchild;
//} Node;int tot = 0;void dfs(Node *root) {if (root == NULL) return ;int l, r;l = tot;tot += 1;dfs(root->lchild);dfs(root->rchild);r = tot; printf("%d : l[%d] | r[%d]\n", root->key, l, r);return ;
}
- 广度优先遍历(BFS)
广度优先遍历,也可称之为层序遍历,因为将树型结构看成是一个金子塔,那么BFS就是从顶向底层遍历。
// typedef struct Node {
// int key;
// struct Node *lchild, *rchild;
//} Node;#define MAX_QUEUE 15void bfs(Node *root) {if (root == NULL) return ;Node *array[MAX_QUEUE] = {0};#undef MAX_QUEUEint head = 0, tail = 0;array[tail++] = root;while (tail != head) {Node *tmp = array[head++];if (tmp->lchild) array[tail++] = tmp->lchild;if (tmp->rchild) array[tail++] = tmp->rchild;printf("%d ", tmp->key);}printf("\n");return ;
}
二叉树:线索化
二叉树的线索化,其实就是将左右子节点为空的结点,重复利用起来,为特定的遍历方式,建立线索化,这样在完成某一个遍历顺序时,可以达到线性复杂度的效率。摆脱递归式遍历的资源浪费问题。
- 中序遍历线索化
中序遍历的线索化,可以将当前结点中子节点为空的结点指向中序遍历的前驱或者后继结点,即当左孩子为空时,则指向中序遍历中,当前结点的前驱结点,当右孩子为空时,则指向中序遍历中,当前结点的后继结点。
- 中序遍历线索化建立
//typedef struct Node {// int key;// int ltag, rtag;// struct Node *lchild, *rchild;// } Node;Node *pre_node = NULL, *in_node = NULL;
void __build_thread(Node *root) {if (root == NULL) return ;if (root->ltag == 0) __build_thread(root->lchild);if (in_node == NULL) in_node = root;if (pre_node && root->lchild == NULL) {root->lchild = pre_node;root->ltag = 1;}if (pre_node && pre_node->rchild == NULL) {pre_node->rchild = root;pre_node->rtag = 1;}pre_node = root;if (root->rtag == 0) __build_thread(root->rchild);return ;
}void build_thread(Node *root) {__build_thread(root);pre_node->rchild = NULL;pre_node->rtag = 1;return ;
}
- 中序线索化遍历
//typedef struct Node {// int key;// int ltag, rtag;// struct Node *lchild, *rchild;// } Node;Node *getNextNode(Node *root) { if (root->rtag == 1) return root->rchild;root = root->rchild;while (root->ltag == 0 && root->lchild) root = root->lchild;return root;
}
二叉树:序列化与反序列化
- 序列化(Serialize)
二叉树的序列化,指的是将二叉树的表示方法转化为字符串形式,即广义表表示方法。
//序列化
#define MAX_CHR 1000char buff[MAX_CHR + 5];
int len = 0;void serialize(Node *root) {if (root == NULL) return ;len += sprintf(buff + len, "%d", KEY(root));if (root->lchild == NULL && root->rchild == NULL) return ;len += sprintf(buff + len, "(");serialize(root->lchild);len += sprintf(buff + len, ",");serialize(root->rchild);len += sprintf(buff + len, ")");return ;
}
- 反序列化(Deserialize)
二叉树的反序列化,就是将字符串(广义表形式)表示的二叉树又转换为树节点的形式。由于二叉树满足递归的性质,因此可以借助栈完成反序列化
//反序列化Node *deserialize(char *str) {Node *root = NULL, *preNode = NULL;Node **array = (Node **)malloc(sizeof(Node *) * MAX_CHR);int top = -1, scode = 0, flag = 0;for (int i = 0; str[i]; i++) {switch (scode) {case 0: {//读取关键词if (str[i] <= '9' && str[i] >= '0') {scode = 1;//读取数字} else if (str[i] == '(') {scode = 2;//入栈新元素} else if (str[i] == ',') {scode = 3;//修改flag} else if (str[i] == ')') {scode = 4;//完成栈顶元素的弹出}i -= 1;} break;case 1: {//读取数字int num = 0;while (str[i] <= '9' && str[i] >= '0') {num = num * 10 + (str[i] - '0');i++;}preNode = getNewNode(num);if (root == NULL) {root = preNode;} if (top != -1 && flag == 0) {array[top]->lchild = preNode;}if (top != -1 && flag == 1) {array[top]->rchild = preNode;}scode = 0;i -= 1;} break;case 2: {//入栈新元素 "("array[++top] = preNode;flag = 0;scode = 0;} break;case 3: {//遇到逗号 ","flag = 1;scode = 0;} break;case 4: {//出栈 ")"--top;flag = 0;scode = 0;} break;}}return root;
}
haffman树
平均编码长度
- 定长编码:指的是无论是何种字符,每个字符的编码都是固定长度。
- 变长编码:即每种字符的编码长度都不是固定的,
- 问题1:这两种编码方式哪种更加适合用于网络传输?
- 问题2:如何衡量两种编码方式的优劣?
我们知道最重要的衡量标准,就是单位时间内网络传输数据量的大小之分。假设两种编码方式,都是在相同网络传输环境下,哪种编码方式传输效率更高呢?不言而喻,就是平均编码长度最小的编码方式。
a v g ( L ) = ∑ L i × P i avg(L) = \sum{L_i \times P_i} avg(L)=∑Li×Pi
avg(L)表示平均编码长度 = 每一种字符的编码长度与对应字符出现概率的乘积累加和
构建haffman树
- 首先,统计得到每一种字符的概率
- 每次将最低频率的两个结点合并成一颗子树
- 经过了n - 1轮合并,就得到了一颗哈夫曼树
- 按照左0右1的形式,将编码读取出来
haffman树:代码演示
- 完整代码
/*************************************************************************> File Name: 04.haffmantree.cpp> Author: > Mail: > Created Time: Wed 17 Jul 2024 10:23:16 AM CST************************************************************************/#include<stdio.h>
#include<stdlib.h>
#include<string.h>#define MAX_CHR 128typedef struct Node {char ch;int freq;struct Node *lchild, *rchild;
} Node;Node *getNewNode(char ch, int freq) {Node *p = (Node *)malloc(sizeof(Node));p->ch = ch;p->freq = freq;p->lchild = p->rchild = NULL;return p;
}int findMinNode(Node **arr, int n) {int ind = 0;for (int i = 1; i <= n; i++) {if (arr[ind]->freq > arr[i]->freq ) ind = i;}return ind;
} void swap_node(Node **arr, int i, int j) {Node *tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;return ;
}Node *buildHaffManTree(Node **arr, int n) {for (int i = 1; i < n; i++) {//find two nodeint ind1 = findMinNode(arr, n - i);swap_node(arr, ind1, n - i);int ind2 = findMinNode(arr, n - i - 1);swap_node(arr, ind2, n - i - 1);//build new nodeint freq_tmp = arr[n - i]->freq + arr[n - i - 1]->freq;Node *new_node = getNewNode(0, freq_tmp);new_node->lchild = arr[n - i - 1];new_node->rchild = arr[n - i];arr[n - i - 1] = new_node;}return arr[0];
}char *ch_code[MAX_CHR + 5] = {0};
int k = 0;void extractHaffManTree(Node *root, char buff[], int k) {buff[k] = 0;if (root->lchild == NULL && root->rchild == NULL) {ch_code[root->ch] = strdup(buff);return ;}buff[k] = '0';extractHaffManTree(root->lchild, buff, k + 1);buff[k] = '1';extractHaffManTree(root->rchild, buff, k + 1);return ;
}void clear(Node *root) {if (root == NULL) return ;clear(root->lchild);clear(root->rchild);free(root);return ;
}int main() {int n;char s[10] = {0};scanf("%d", &n);Node **array = (Node **)malloc(sizeof(Node *) * n);for (int i = 0; i < n; i++) {int freq;scanf("%s%d", s, &freq);array[i] = getNewNode(s[0], freq);}Node *root = buildHaffManTree(array, n);char buff[1000] = {0};extractHaffManTree(root, buff, 0);for (int i = 0; i < MAX_CHR; i++) {if (ch_code[i] == NULL) continue;printf("%c : %s\n", i, ch_code[i]);}clear(root);#undef MAX_CHRreturn 0;
}
- 运行效果展示
相关文章:

树与二叉树学习笔记
树与二叉树 计算机中的树树的概念树的类型 什么是二叉树二叉树:定义与特点二叉树:前序、中序、后序遍历二叉树:深度、广度优先遍历二叉树:线索化二叉树:序列化与反序列化 haffman树平均编码长度构建haffman树haffman树…...

消费金融系统开发回忆录
架构设计图 整个支付链路上的功能 支付系统应该有:账户管理、渠道管理、支付管理、对账管理、清算管理、结算管理 一笔支付订单,在支付系统侧就是要记录清楚,谁发起的、对哪个商品进行支付、通过哪个渠道支付、支付时间、支付结果等…...

org.springframework.context.ApplicationContext发送消息
1、创建消息的实体类 package com.demo;/*** 监听的实体类**/ public class EventMessage {private String name;public EventMessage(String name) {this.name name;}public String getName() {return name;}public void setName(String name) {this.name name;} }2、创建消…...
Java8-21新特性
简介 由于Java官方最近更新越来越频繁,而长期支持维护的版本LTS版每隔几年才推出一个,大规模商用的JDK只可能选择LTS版,因此这里只简单记录JDK8,11,17,21。 jdk8 Lambda表达式: Lambda表达式…...
NodeJS系列面试题
大家好,我是有用就扩散,有用就点赞。 有没有写过Koa中间件,说一下中间件原理,介绍下自己写过的中间件 koa本来就是一个轻量级框架,本身支持的功能并不多,功能都是通过中间件来实现不同的需求。开发者可以通…...

QXlsx读写excel
QXlsx读写excel 安装 QXlsx使用 qmake使用 CMake 基本用法1. 写入 Excel 文件2. 读取 Excel 文件 详细用法1. 设置单元格样式2. 合并单元格3. 创建图表4. 设置列宽和行高 完整示例 QXlsx 是一个用于在 Qt 应用中读写 Excel 文件的第三方库。它提供了丰富的 API,可以…...

昇思25天学习打卡营第13天 | mindspore 实现 ShuffleNet 图像分类
1. 背景: 使用 mindspore 学习神经网络,打卡第 13 天;主要内容也依据 mindspore 的学习记录。 2. 迁移学习介绍: mindspore 实现 ShuffleNet 图像分类; ShuffleNet 基本介绍: ShuffleNetV1 是旷视科技提…...

C语言超市管理系统UI界面
以下是部分代码。需要源码的私信 #include<easyx.h> #include<stdio.h> #include<stdlib.h>#define width 1280 #define height 840 #define font_w 35 //字体宽度 #define font_h 90 //字体高度typedef struct node {char name[100];//名字char number[1…...

BUUCTF逆向wp [MRCTF2020]Xor
第一步 查壳,该题是32位,无壳。 第二步 跟进main,发现反汇编不了 通过下图我们可以发现一串类似字符串的东西 第三步 我们看一下汇编 我们可以得到这些信息:flag的长度为27(下面是对本条指令cmp edx 27指令的应用…...

Windows版MySQL5.7解压直用(如何卸载更换位置重新安装)
文章目录 停止mysql进程及服务迁移整个mysql文件夹删除data重启计算机重新安装 停止mysql进程及服务 net stop mysql mysqld -remove mysql迁移整个mysql文件夹 删除data 重启计算机 shutdown -r -t 0重新安装 https://blog.csdn.net/xzzteach/article/details/137723185...

详解数据结构之二叉树(堆)
详解数据结构之二叉树(堆) 树 树的概念 树是一个非线性结构的数据结构,它是由 n(n>0)个有限节点组成的一个具有层次关系的集合,它的外观形似一颗倒挂着的树,根朝上,叶朝下,所以称呼为树。每颗子树的根节点有且只…...

Linux----Mplayer音视频库的移植
想要播放视频音乐就得移植相关库到板子上 Mplayer移植需要依赖以下源文件:(从官网获取或者网上) 1、zlib-1.2.3.tar.gz :通用的内存空间的压缩库。 2、libpng-1.2.57.tar.gz :png格式图片的压缩或解压库 3、Jpegsrc.v9b.tar.gz : jpeg格式图片的压…...

STM32测测速---编码电机读取速度的计算
1、首先先了解一下计算的公式 速度计算: 轮胎每转一圈的脉冲数取决于编码器的分辨率,可由下面公式进行计算: PPR是电机的线数 以GA25-370电机为例。 图片来源:第四节:STM32定时器(4.JGA25-370霍尔编码器…...
【已解决】服务器无法联网与更换镜像源
目录 问题描述: 1.修改网卡的 DNS1 和 DNS2 2.修改DNS列表 3.重启网络服务 4.切换镜像源 4.1备份原镜像源 4.2下载阿里云镜像源 4.3替换无法使用的域名 4.4刷新软件包缓存 4.5其他镜像源 5.阿里云镜像源开发者社区说明 6.阿里云DNS网址 7.DNS域名服务器…...
android11 屏蔽usb通过otg转接口外接鼠标设备
硬件平台:QCS6125 软件平台:Android11 需求:Android设备通过接usb转接线连接鼠标功能屏蔽。 考虑到屏蔽的层面可以从两个层面去做,一个是驱动层面不识别,一个就是Android系统层面不识别加载,本篇只讲后者。…...

HAL库源码移植与使用之RTC时钟
实时时钟(Real Time Clock,RTC),本质是一个计数器,计数频率常为秒,专门用来记录时间。 普通定时器无法掉电运行!但RTC可由VBAT备用电源供电,断电不断时 这里讲F1系列的RTC 可以产生三个中断信号ÿ…...

GIT命令学习 一
📑打牌 : da pai ge的个人主页 🌤️个人专栏 : da pai ge的博客专栏 ☁️宝剑锋从磨砺出,梅花香自苦寒来 ☁️运维工程师的职责:监…...
VS+QT 打包可执行文件.exe
切换成release版本,同时更改项目属性中release配置下的各个属性,确保匹配 重新生成解决方案,将生成的.exe复制到一个空白文件夹中 执行: cd D:\QT\5.12.10\msvc2015_64\binwindeployqt C:\Users\DELL\Desktop\serials\MainWind…...
Android笔试面试题AI答之Activity(2)
答案仅供参考,大部分为文心一言AI作答 目录 1. 请介绍一下Activity 生命周期?1. 完全生命周期2. 可见生命周期3. 前台生命周期4. 配置更改5. 特殊场景 2. 请介绍一下横竖屏切换时Activity的生命周期变化?1.默认行为(未设置androi…...
来自Transformers的双向编码器表示(BERT) 通俗解释
来自Transformers的双向编码器表示(BERT) 目录 1. 从上下文无关到上下文敏感2. 从特定于任务到不可知任务3. BERT:把两个最好的结合起来4. BERT的输入表示5. 掩蔽语言模型(Masked Language Modeling)6. 下一句预测&am…...
ubuntu搭建nfs服务centos挂载访问
在Ubuntu上设置NFS服务器 在Ubuntu上,你可以使用apt包管理器来安装NFS服务器。打开终端并运行: sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享,例如/shared: sudo mkdir /shared sud…...

UDP(Echoserver)
网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法:netstat [选项] 功能:查看网络状态 常用选项: n 拒绝显示别名&#…...

有限自动机到正规文法转换器v1.0
1 项目简介 这是一个功能强大的有限自动机(Finite Automaton, FA)到正规文法(Regular Grammar)转换器,它配备了一个直观且完整的图形用户界面,使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...
Linux离线(zip方式)安装docker
目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1:修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本:CentOS 7 64位 内核版本:3.10.0 相关命令: uname -rcat /etc/os-rele…...

【Linux】自动化构建-Make/Makefile
前言 上文我们讲到了Linux中的编译器gcc/g 【Linux】编译器gcc/g及其库的详细介绍-CSDN博客 本来我们将一个对于编译来说很重要的工具:make/makfile 1.背景 在一个工程中源文件不计其数,其按类型、功能、模块分别放在若干个目录中,mak…...

破解路内监管盲区:免布线低位视频桩重塑停车管理新标准
城市路内停车管理常因行道树遮挡、高位设备盲区等问题,导致车牌识别率低、逃费率高,传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法,正成为破局关键。该设备安装于车位侧方0.5-0.7米高度,直接规避树枝遮…...
Python竞赛环境搭建全攻略
Python环境搭建竞赛技术文章大纲 竞赛背景与意义 竞赛的目的与价值Python在竞赛中的应用场景环境搭建对竞赛效率的影响 竞赛环境需求分析 常见竞赛类型(算法、数据分析、机器学习等)不同竞赛对Python版本及库的要求硬件与操作系统的兼容性问题 Pyth…...

PH热榜 | 2025-06-08
1. Thiings 标语:一套超过1900个免费AI生成的3D图标集合 介绍:Thiings是一个不断扩展的免费AI生成3D图标库,目前已有超过1900个图标。你可以按照主题浏览,生成自己的图标,或者下载整个图标集。所有图标都可以在个人或…...
文件上传漏洞防御全攻略
要全面防范文件上传漏洞,需构建多层防御体系,结合技术验证、存储隔离与权限控制: 🔒 一、基础防护层 前端校验(仅辅助) 通过JavaScript限制文件后缀名(白名单)和大小,提…...
webpack面试题
面试题:webpack介绍和简单使用 一、webpack(模块化打包工具)1. webpack是把项目当作一个整体,通过给定的一个主文件,webpack将从这个主文件开始找到你项目当中的所有依赖文件,使用loaders来处理它们&#x…...