1 树

1.1 树的基本概念

在这里插入图片描述

1.1.1 什么是树?

树是n(n >= 0)个结点的有限集。当n = 0时,称为空树。在任意一颗非空树上应该满足:

  • 有且仅有一个特定的称为的结点
  • 当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1、T2、…Tm,其中每个集合本身又是一棵树,并且称为根的子树
    在这里插入图片描述

1.1.2 树的特点

  1. 树的根结点没有前驱,除了根结点以外的所有结点有且只有一个前驱
  2. 树中所有结点可以有0个或者多个后继

1.1.3 树的基本术语

  1. 结点之间的关系:祖先结点、子孙结点、父结点、兄弟结点、孩子结点、表兄弟结点
    在这里插入图片描述
  2. 结点的度:树中一个结点的孩子个数
  3. 树的度:树中结点的最大度数
    在这里插入图片描述
  4. 结点的层次:从上往下数,根节点是第一层、它的子节点是第二层,以此类推
  5. 结点的高度:从下往上数
  6. 树的高度:总共有多少层
  7. 有序树:逻辑上看,树中结点的各子树从左至右都是有次序的,不能互换;无序树:从逻辑上看,树中结点的各子树从左至右是无次序的,可以互换
  8. 路径和路径长度。路径:这两个结点之间所经过的结点序列构成的;路径长度:路径上所经过的边的个数
  9. 森林:森林是m(m > 0)棵互不相交的树的集合。

1.2 树的性质

  1. 树中的结点数 = 所有结点数的度数之和+1
    在这里插入图片描述

  2. 度为m的树中第i层上至多有m的i-1次方个结点(i>=1)在这里插入图片描述

  3. 高度h的m叉树至多有多少结点?
    在这里插入图片描述

1.3 树的存储结构

1.3.1 顺式存储

双亲表示法:用一组连续空间来存储每个结点,同时为每个结点中增设一个伪指针(表示该结点的双亲结点的位置)

在这里插入图片描述
代码如下:

#define MAX_TREE_SIZE 100 // 树中最多结点数
typedef struct {// 树中结点定义ElemType data;// 数据元素int parent;// 双亲结点位置
}PTNode;
typedef struct{// 树的类型定义PTNode nodes[MAX_TREE_SIZE];int n;// 结点数
}PTree;

该存储结构的特点是比较容易得到结点的双亲结点,但是想要得到结点的孩子结点则需要遍历整个数组

1.3.2 顺式存储+链式存储

孩子表示法:每个结点的孩子结点用单链表链接在一起形成一个线性结构,而每个结点都由连续的空间存储
在这里插入图片描述代码如下:

struct CTNode {// 链式村粗的孩子结点int child;// 孩子结点在数组的位置struct CTNode *next;// 下一个结点
}
typedef struct {// 顺序存储的每个结点ElemType data;// 数据元素struct CTNode *firstChild;// 指向第一个孩子结点
}CTBox;
typedef struct {// 表示树CTBox nodes[MAX_TREE_SIZE];int n,r;// 结点数和根的位置
}CTree;

1.3.3 链式存储

孩子兄弟表示法:以二叉链表作为树的存储结构。每个结点包含三部分的内容:结点值、指向第一个孩子结点的指针、指向结点下一个兄弟结点的指针
在这里插入图片描述
代码:

typedef struct CSNode {ElemType data;struct CSNode *firdtchild,*nextsibling;// 第一个孩子以及该孩子的第一个右兄弟指针
}CSNode,*CSTree;

1.3.4 拓展 树和森林与二叉树的转换

  1. 树转森林

在这里插入图片描述森林中各个树的根被视为兄弟关系

  • 森林转树
    在这里插入图片描述

2 二叉树

2.1 什么是二叉树

二叉树就是每个结点至多有两颗子树,且左右子树有左右之分,不可以颠倒次序
其定义如下:
二叉树是n(n>=0)个结点的有限集合

  • 或者为空二叉树,即n=0
  • 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一颗二叉树。
    在这里插入图片描述

2.2 几个特殊的二叉树

  1. 满二叉树:二叉树的每一层都是满的,也就是说一个高度为h的满二叉树,其结点有2的h次方-1个;如果按照层序编号,对于一个编号为i的结点,其左孩子的编号为2i,右结点的编号为2i+1,其双亲结点的编号为i/2的向下取整
    在这里插入图片描述

  2. 完全二叉树 :在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层(h从1开始),则该层包含 1~ 2^(h-1) 个节点。
    在这里插入图片描述

  3. 二叉排序树:若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;它的左、右子树也分别为二叉排序树
    在这里插入图片描述

  4. 平衡二叉树:又被称为AVL(Adelson-Velsky and Landis)树,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。它在满足二叉排序树的条件下,还要求任意节点的左右子树的高度差不超过1。也就是说,平衡二叉树是一棵自平衡的二叉排序树。
    在这里插入图片描述

2.3 二叉树的存储结构

2.3.1 顺序存储

1.顺式存储的方式如图:
在这里插入图片描述
2.如果父节点的数组下标是 i,那么它的左孩子就是 i * 2 + 1右孩子就是 i * 2 + 2
3.定义代码如下:

#define MaxSize 100
struct TreeNode {ElemType value;// 结点中的数据元素bool isEmpty;// 结点是否为空
}
TreeNode t[MaxSize];

2.3.2 链式存储

1.链式存储的方式如图:
在这里插入图片描述
2.代码如下:

typedef struct BiTNode {ElemType data;struct BitNode *lchild,*rchild;
}BitNode,*BiTree;
  1. 含有n个结点的二叉链表中,含有n+1个空链域。(2n-(n-1))
    解释:2n个指针域、n-1个边(代表有n-1个指针域不是空的)

2.4 二叉树的遍历

2.4.1 深度优先遍历

在这里插入图片描述

(1)先序遍历:首先访问根结点然后遍历左子树,最后遍历右子树。在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树。】
void preOrder(BiTree T){if(T) {visit(T);// 访问根结点preOrder(T->lchild);// 以此方式访问左子树preOrder(T->rchild);// 以此方式访问右子树}
}
(2)中序遍历:首先访问左子树然后访问根节点,最后访问右子树。在访问左、右子树时,仍然先访问左子树,然后根结点,最后问右子树。
void InOrder(BiTree T){if(T) {InOrder(T->lchild);// 以此方式访问左子树visit(T);// 访问根结点InOrder(T->rchild);// 以此方式访问右子树}
}
(3)后序遍历:首先访问左子树、其次访问右子树,最后访问根结点。在访问左、右子树时,仍然先访问左子树、再访问右子树,最后访问根结点。
void PostOrder(BiTree T){if(T) {PostOrder(T->lchild);// 以此方式访问左子树PostOrder(T->rchild);// 以此方式访问右子树visit(T);// 访问根结点}
}
(4)例子

在这里插入图片描述

(5)由遍历序列构造二叉树
  1. 先序+中序
  2. 后序+中序
  3. 层序+中序
  4. 以上均可确立一颗二叉树

2.4.2 层次优先遍历

在这里插入图片描述算法思想

  1. 初始化一个辅助队列
  2. 根节点入队
  3. 若队列非空,则队头结点出队,访问该结点,并将其左右孩子插入队尾
  4. 重复(3)直到队列为空

代码如下:

void LevelOrder(BiTree T) {LinkQueue Q;InitQueue(Q); // 初始化辅助队列BiTree p;EnQueue(Q,T);// 根节点入队while(!IsEmpty(Q)) {DeQueue(Q,p);// 队头结点出队visit(p);// 访问出队结点if(p->lchild != NULL)EnQueue(Q,p->lchild);// 左孩子入队if(p->rchild != NULL)EnQueue(Q,p->rchild);// 右孩子入队}
}

2.5 线索二叉树

2.5.1 什么是线索二叉树

  1. 为啥要用线索二叉树?跟单向链表类似,在二叉树中想访问一个结点的双亲结点十分不容易,需要重新遍历一次二叉树才可以找到。由于一颗n个结点的二叉树有n+1个空指针域,所以就想到可不可以利用这些空指针域来储存该结点的前驱与后继呢?

以下代码是普通二叉树访问指定结点的双亲结点

// 递归中序遍历
void InOrder(BiTree T) {if(T!=NULL) {InOrder(T->left);// 左visit(T);// 中InOrder(T->right);// 右}
}
// 访问结点q
void visit(BiTNode *q) {if(q == p) // 当前访问的结点等于指定结点p时final = pre;// 找到p的前驱elsepre = q;// pre指向当前访问的结点
}
BiTNode *p;// 目标结点
BiTNode *pre = NULL;// 当前访问结点的前驱
BiTNode *final = NULL:// 当前结点
  1. 所以引用线索二叉树的目的就是为了加快查找结点前驱和后继的速度;遍历二叉树的实质就是以一定规则将二叉树的结点排列成一个线性序列,该序列每个结点(除了首与尾)都有一个直接前驱与后继。
    下面是对线索二叉树结点的定义
typedef struct ThreadNode{ElemType data;// 数据元素struct ThreadNode *lchild,*rchild;// 左右孩子指针int ltag,rtag;// 左右线索标志
}

2.5.2 二叉树线索化

二叉树的线索化就是将二叉链表中的空指针改为指向前驱或后继的线索。而前驱和后继的信息只有在遍历的时候才可以得到。实质上还是遍历一下二叉树。

void InThread(ThreadTree &p,ThreadTree &pre) {if(p!=NULL) {InThread(p->lchild,pre);// 递归线索化左子树// 本层逻辑if(p->lchild == NULL) {// 该结点左孩子为空,则将其指向其父节点、线索标志位置为1p->lchild = pre;p->ltag = 1;}if(pre != NULL&&pre->rchild == NULL) {// 若该结点的前驱结点不为空且前驱节点的右孩子为空,则将其右孩子指针指向该结点、线索标志位置为1pre->rchild = p;pre->rtag = 1;}pre = p;InThread(p->rchild,pre);// 递归线索化右子树}
}void CreateInThread(ThreadTree T) {ThreadTree pre = NULL;if(T != NULL) {InThread(T,pre);// 线索化pre->rchild = NULL;// 处理最后一个结点pre->rtag = 1;}
} 

2.5.3 在线索二叉树中寻找前驱后继

线索二叉树的结点分为两种情况,一个是线索化的结点,一个是没有线索化的结点

  1. 线索化结点:访问这类结点,直接通过其左右孩子指针就可得到其前驱后继
  2. 非线索化结点:这类结点没有被线索化的原因就是其左右指针已经用来指向其左右孩子了。所以想要得到其前驱后继,就只能通过它到底是什么方式遍历的来判断寻找它的前驱后继
  3. 以中序为例:
// 传统方法迭代找到该子树的最左下结点
ThreadNode *Firstnode(ThreadNode *p) {while(p->ltag == 0) p = p->lchild;// 最左下结点、不一定是叶子结点return p;
}
// 寻找后继
ThreadNode *Nextnode(ThreadNode *p) {if(p->rtag == 0) return Firstnode(p->rchild);// 若该结点的右指针没有线索化则通过传统方法迭代找到该子树的最左下结点为其后继else return p->rchild;// 如果线索化的,则直接返回其右指针即可
}
// 中序遍历
void Inorder(ThreadNode *T) {for(TreadNode *p = Firstnode(T); p != NULL; p = Nextnode(p)) {visit(p);}
}

2.6 哈夫曼树

  1. 带权路径长度
    在这里插入图片描述

    (1)结点的权:有某种现实含义的数值
    (2)结点的带权路径长度:从树的根到该结点的路径长度(经过的边数)与该结点上权值的乘积
    (3)的带权路径长度:树中所有叶子结点的带权路径长度之和

  2. 哈夫曼树的定义
    在含有n个带权叶子结点的二叉树中,其中带权路径长度最小的二叉树称为哈夫曼树,也称最优二叉树
    在这里插入图片描述以上4棵树,只有中间的两颗是哈夫曼树

  3. 哈夫曼树的构造:给定n个权值分别为w1,w2,w3,…,wn的结点,构造哈夫曼树的算法描述如下:
    (1)将这n个结点分别作为n课仅仅含一个结点的二叉树,构成森林F
    (2)构造一个新结点,从F中选取两颗根节点权值最小的二叉树作为新节点的左右子树,并且将新节点的权值置为左右子树上的根节点的权值之和
    (3)从F中删除刚才选出的两棵树、同时将新加到的树加入F中
    (4)重复步骤2和3,直到F中只剩下一棵树为止
    在这里插入图片描述

  4. 哈夫曼树的特点:
    (1)每个初始结点最终都会成为叶子结点,且权值越小的结点到根节点的路径长度越大
    (2)哈夫曼树的结点总数为2n-1
    (3)哈夫曼树没有度为1的结点
    (4)哈夫曼树不唯一,但是WPL一定相同且为最优

  5. 哈夫曼编码
    (1)固定长度编码:每个字符用相等长度的二进制位表示
    在这里插入图片描述

(2)可变长度编码:允许对不同字符用不同长度的二进制位表示
在这里插入图片描述
(3)为什么A不可以用1个二进制位去编码呢?
在这里插入图片描述

答:这样就会混淆信息了。这里引申出一个概念:前缀编码(指没有一个编码是另一个编码的前缀),这样的编码方式不会出现歧义

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/94902.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

微信支付报非法的密钥大小: Caused by: java.security.InvalidKeyException: Illegal key size

在Linux环境中出现 java.security.InvalidKeyException: Illegal key size 异常通常是由于Java默认的加密限制引起的。Java默认的加密强度限制了加密算法密钥的最大长度 方式一 1. 找到该目录 /usr/java/jdk1.8.0_121/jre/lib/security 2. 替换local_policy.jar 和 US_export_…

单因素多变量方差分析

多变量方差分析:是对多个独立变量是否受单个或多个因素影响而进行的方差分析。它不仅能够分析多个因素对观测变量的独立影响,更能够分析多个因素的交互作用能否对观测变量产生影响。本章以单因素多变量分析为例,即一个分组变量和多个欲分析的…

怎么开通Tik Tok海外娱乐公会呢?

TikTok作为全球知名的社交媒体平台,吸引了数亿用户的关注和参与。许多公司和个人渴望通过开通TikTok直播公会进入这一领域,以展示自己的创造力和吸引更多粉丝。然而,成为TikTok直播公会并非易事,需要满足一定的门槛和申请找cmxyci…

Kubernetes 调度约束(亲和性、污点、容忍)

目录 一、Pod启动典型创建过程 二、调度流程 三、指定调度节点 1.使用nodeName字段指定调度节点 2.使用nodeSelector指定调度节点 2.1给对应的node节点添加标签 2.2修改为nodeSelector调度方式 3.通过亲和性来指定调度节点 3.1节点亲和性 3.2Pod亲和性与反亲和性 3.2…

【深入探索Docker】:开启容器化时代的技术奇迹

深入探索Docker 深入探索Docker:开启容器化时代的技术奇迹前言1. 容器化:实现快速部署和可移植性2. 虚拟化:提高安全性和可靠性3. 映像:打包应用及依赖项的模板4. 网络管理:连接容器和主机5. 持久化数据:保…

探索心律失常:病因、诊断与治疗以及与肠道菌群的关联

谷禾健康 你是否有时会感到心悸、心慌、胸闷、气短、头晕、乏力?你是否有时感觉自己的心跳过快或过慢? 如果有上述情况,就要引起重视了,你可能存在心律失常。心律失常是最常见的心脏疾病之一,涉及到心脏的电活动节奏异…

2023 CCF BDCI 数字安全公开赛正式开启报名

2023 CCF BDCI 数字安全公开赛重磅来袭! 全新的赛道场景 丰厚的赛事奖励 精彩的周边活动 数字安全守护人的狂欢盛宴 快来报名参加吧 大赛背景 伴随着数智化的持续加深,网络安全、数据安全风险遍布于所有场景之中,包括工业生产、能源、交…

SAP ABAP 直接把内表转换成PDF格式(smartform的打印函数输出OTF格式数据)

直接上代码: REPORT zcycle055.DATA: lt_tab TYPE TABLE OF zpps001. DATA: ls_tab TYPE zpps001.ls_tab-werks 1001. ls_tab-gamng 150.00. ls_tab-gstrp 20201202. ls_tab-aufnr 000010000246. ls_tab-auart 标准生产. ls_tab-gltrp 20201205. ls_tab-matn…

Azure如何启用网络观察应用程序

文章目录 基础概念介绍实操 基础概念介绍 Azure中的网络观察应用程序是一种用于监视和诊断Azure网络的工具。它提供了一种集中管理和监控网络流量、连接性和性能的方式。网络观察应用程序能够提供网络流量分析、连接监视、性能监视和故障诊断等功能,用于帮助管理员…

产业园区数字孪生3d可视化全景展示方案

随着数字经济的发展,数字技术给企业发展带来了机遇的同时,也为企业管理带来挑战。比如园区运维,不仅体量大,复杂的运维管理系统,落地难度也较高。那么如何通过数字化手段重塑园区运营,打通园区各业务数据孤…

如何搭建个人邮件服务hmailserver并实现远程发送邮件

文章目录 1. 安装hMailServer2. 设置hMailServer3. 客户端安装添加账号4. 测试发送邮件5. 安装cpolar6. 创建公网地址7. 测试远程发送邮件8. 固定连接公网地址9. 测试固定远程地址发送邮件 hMailServer 是一个邮件服务器,通过它我们可以搭建自己的邮件服务,通过cpolar内网映射工…

谈谈IP地址和子网掩码的概念及应用

个人主页:insist--个人主页​​​​​​ 本文专栏:网络基础——带你走进网络世界 本专栏会持续更新网络基础知识,希望大家多多支持,让我们一起探索这个神奇而广阔的网络世界。 目录 一、IP地址的概念 二、IP地址的分类 1、A类 …

leetcode15. 三数之和

这里保证1.元素a不会重复。2.所有解都是有序的。3.b和c元素不重复。所以解不会重复。 class Solution { public:vector<vector<int>> threeSum(vector<int>& nums) {std::vector<std::vector<int>> result;if (nums.size() < 3) return …

ADC静态特性测试

测试环境搭建&#xff1a; 码密度分析法的局限性 更新&#xff1a; MATLAB R2020a之后的版本&#xff0c;更新了函数 “inldnl()”&#xff0c;可以自动计算INL和DNL。具体用法看MATLAB说明文档即可。

欧拉OS 使用 CentOS 7 yum repo

一、下载CentOS的repo的yum文件 任何基于CentOS的yum的repo 的url是这样的&#xff1a; 但欧拉OS输出这个变量为&#xff1a;openEuler 20.03 (LTS-SP3) 那明显欧拉想要使用这个yum的url找不到这个版本&#xff0c; 所以直接讲这个变量替换为 7, Centos 7的7 然后执行&…

【24择校指南】华东师范大学计算机考研考情分析

华东师范大学(B) 考研难度&#xff08;☆☆☆☆&#xff09; 内容&#xff1a;23考情概况&#xff08;拟录取和复试分数人数统计&#xff09;、院校概况、23考试科目、23复试详情、各科目及专业考情分析。 正文2563字&#xff0c;预计阅读&#xff1a;3分钟。 2023考情概况…

【数据结构】链表常见题目

文章目录 链表合并两个有序链表反转链表复制带随机指针的链表环形链表环形链表II相交链表移除链表元素链表中倒数第k个节点链表分割链表的回文结构链表的中间节点旋转链表链表排序链表求和 (逆序求)链表求和II (正序求)重排链表奇偶链表反转链表II <==> 链表内指定区间反…

IDEA常用工具配置

IDEA常用工具&配置 如果发现插件市场用不了&#xff0c;可以设置Http Proxy&#xff0c;在该界面上点击”Check connection“并输入的地址&#xff1a;https://plugins.jetbrains.com/ 。 一、常用插件 1、MybatisX Mybaits Plus插件&#xff0c;支持java与xml互转 2、F…

vue上传图片并修改png图片颜色

场景 当涉及到在 Vue 中上传图片并修改 PNG 图片的颜色时&#xff0c;这个任务涵盖了文件上传、图像处理、Canvas 操作等多个方面 在现代 Web 开发中&#xff0c;图片的处理是常见的需求之一。本文将带您深入探讨如何使用 Vue.js 来实现图片上传&#xff0c;并在客户端使用 Can…

LD_RPELOAD环境变量

目录 LD_RPELOAD环境变量 LD_RPELOAD 定义 程序的连接方式 Linux规定动态链接库的文件名规则如下 动态链接库的搜索路径搜索的先后顺序 LD_RPELOAD的劫持 demo 1.定义一个hook.c文件 2.将所写的hook.c 文件编译为动态链接库hook.so 3.劫持检测&#xff0c;查看LD_PREL…