技术标签: 树 二叉排序树 二叉树 哈夫曼树 数据结构笔记 数据结构
目录
① 结点的度:结点拥有的子树数量
② 树的度:树内结点度的最大值
③ 叶子:度为0的结点
④ 结点的层次和树的深度:
⑤ 森林:m棵互不相交的树的集合
⑥ 边数+1 = 结点数
① 每个结点至多有2个棵子树,即二叉树中不存在度大于2的结点
没有子树或有一颗子树都是可以的。
② 二叉树的子树有左右之分,且其次序不能颠倒
③ 即使树的某结点只有一颗子树,也要区分它是左子树和右子树
④ 二叉树不是树的特殊情况,它们是两个概念
⑤ 二叉树的结点个数可以为0
① 二叉树的第 i 层最多有 个结点,至少有1个结点;
② 深度为 k 的二叉树至多有 个结点,至少有k个结点;
③ 叶子数为,度为2的结点数为,则 ;
满二叉树
一棵深度为 且有 个结点的二叉树
① 所有分支结点都有左子树和右子树,叶子结点都在最下一层
② 只有度为0和度为2的结点
③ 含n个结点的满二叉树的深度为叶子结点个数为⌊ ⌋ (向下取整)
度为2的结点为⌊ ⌋ (向下取整)
完全二叉树
① 叶子结点只可能出现在层次最大的两层出现
② 最下一层中的叶子结点都依次排列在该层最左边的位置上
③ 如果有度为1的结点,只可能有一个,且该结点最多只有左孩子而无右孩子④ 满二叉树是特殊的完全二叉树
⑤ 度为1的结点最多有1个
⑥ 含n个结点的完全二叉树的深度为⌊ ⌋ +1 (向下取整)
⑦ 含n个结点的完全二叉树,对任意结点 i:
(1)如果i>1,则其双亲是 ⌊ i / 2 ⌋ (向下取整)
(2)如果2i>n,则结点 i 无孩子(结点i为叶子结点);否则其左孩子是结点 2i
(3)如果2i+1>n,则结点 i 无右孩子;否则其右孩子是结点 2i+1
例1、一棵完全二叉树有5000个结点,则其叶结点个数是(2500)
n0+n1+n2=5000,因为n0=n2+1,则2*n2+1+n1=5000,因此n1一定是奇数
因为完全二叉树,其中度为1的结点个数最多为1个,则n1=1,则n2=2499,则n0=2500
例2、二叉链表:n个结点共2n个指针,其中有效指针为n-1,则空指针数为2n-(n-1)=n+1
结点-1 = 有效指针数
三叉链表:n个结点共3n个指针,其中有效指针为n-1,则空指针数为3n-2(n-1)=n+2
① 树的结点个数至少为1,二叉树的结点个数可以为0
② 树的最大度数没有限制,二叉树最大度数不能超过2
③ 树的结点无左右之分,二叉树的结点有左右之分
将树转化为二叉树的目的:
树可采用二叉树的存储结构并利用二叉树的已有算法解决树的有关问题
//按先序遍历创建二叉树
Status CreateBiTree( BiTree &T )
{
char c;
scanf("%c",&c);
if(c == ' ') T = NULL;
else{
if(!(T = (BiTNode*)malloc(sizeof(BiTNode)))) return;
T->data = c;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
1、遍历顺序 (D为根 L为左子树 R为右子树)
① DLR 先序遍历
② LDR 中序遍历
③ LRD 后序遍历
1、先序遍历:根节点 → 左节点 → 右节点;
2、中序遍历:左节点 → 根节点 → 右节点;
3、后序遍历:左节点 → 右节点 → 根节点;
//递归算法
void PreOrderTraverse(BiTree T, int level)
{
if (T)
{
printf("data = %c level = %d\n ", T->data, level);
PreOrderTraverse(T->lchild, level + 1);
PreOrderTraverse(T->rchild, level + 1);
}
}
//递归算法
void InOrderTraverse(BiTree T, int level)
{
if (T)
{
PreOrderTraverse(T->lchild, level + 1);
printf("data = %c level = %d\n ", T->data, level);
PreOrderTraverse(T->rchild, level + 1);
}
}
//非递归算法
void InOrderTraverse(BiTree T)
{
InitStack(S);
p = T;
while(p||!StackEmpty(S))
{
if(p)
{
Push(S,p);
p = p->lchild;
}else{
Pop(S,p);
printf("%c ",p->data);
p = p->rchild;
}
}
}
//递归算法
void PostOrderTraverse(BiTree T, int level)
{
if (T)
{
PreOrderTraverse(T->lchild, level + 1);
PreOrderTraverse(T->rchild, level + 1);
printf("data = %c level = %d\n ", T->data, level);
}
}
c++ queue 队列
queue <元素类型> q1;
q.push() //在队尾插入一个元素 q.pop() //删除队列第一个元素 q.size() //返回队列中元素个数 q.empty() //如果队列空则返回true q.front() //返回队列中的第一个元素 q.back() //返回队列中最后一个元素
void levelOrderTraverse (Bitree T)
{
if(T == NULL) return; //空树
queue <BiTNode*> q; //创建队列
q.push(T); //将根节点入队
while(!q.empty())
{
BiTNode *node = q.front(); //取头结点
printf("%d ",node->data);
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
p.pop(); //头结点出队
}
}
#include <stdio.h>
#include <stdlib.h>
typedef char ElemType;
typedef enum PointerTag{Link,Thread}; //枚举类型 Link=0 Thread=1
typedef struct BiThrNode
{
ElemType data;
struct BiThrNode *lchild,*rchild;
PointerTag ltag,rtag;
}BiThrNode, *BiThrTree;
BiThrTree pre; //全局变量
//前序遍历 创建二叉树
void CreateBiThrTree( BiThrTree *T )
{
char c;
scanf("%c",&c);
if(c == ' ') *T = NULL;
else
{
*T = (BiThrNode*)malloc(sizeof(BiThrNode));
(*T)->data = c;
(*T)->ltag = Link; //初始化左右标识
(*T)->rtag = Link;
CreateBiThrTree(&(*T)->lchild);
CreateBiThrTree(&(*T)->rchild);
}
}
//
void InOrderThreading(BiThrTree *p,BiThrTree T)
{
*p = (BiThrTree)malloc(sizeof(BiThrNode));
(*p)->ltag = Link;
(*p)->rtag = Thread;
(*p)->rchild = *p;
if(!T)
{
(*p)->lchild = *p;
}
else {
(*p)->lchild = T;
pre = *p;
InThreading(T);
pre->rchild = *p;
pre->rtag = Thread;
(*p)->rchild = pre;
}
}
//中序遍历线索化
void InThreading( BiThrTree T )
{
if( T )
{
InThreading( T->lchild ); //递归左孩子线索化
if(!T->lchild)
{
T->ltag = Thread; //没有左孩子 ltag改为1
T->lchild = pre;
}
if(!pre->rchild)
{
pre->rtag = Thread;
pre->rchild = T;
}
pre = T;
InThreading( T->rchild ); //递归右孩子线索化
}
}
int main()
{
BiThrTree P,T = NULL;
CreateBiThrTree(&T);
InOrderThreading( &P, T );
return 0;
}
BiTNode *SearchNode(BiTree &T,ElemType e)
{
if(!T) return;
if(T->data == e) return T;
else
{
BiTNode *p = SearchNode(T->lchild,e);
if(!p) return SearchNode(T->rchild,e);
return p;
}
}
int BiTreeHigh(BiTree &T)
{
int h1,h2;
if(T)
{
h1 = BiTreeHigh(T->lchild);
h2 = BiTreeHigh(T->rchild);
return h1>h2? ++h1:++h2;
}
return 0;
}
int CountLeaf(BiTree &T)
{
if(T)
{
if(!T->lchild && !T->rchild)
return 1;
else
return CountLeaf(T->lchild) + CountLeaf(T->rchild);
}
return 0;
}
int CountNodes(BiTree &T)
{
if(T)
{
if(!T->lchild && !T->rchild)
return 1;
else
return 1 + CountNodes(T->lchild) + CountNodes(T->rchild);
}
return 0;
}
第一步:把树中所有兄弟结点之间加一条连线
第二步:对于每个结点,除保留其长子的连线外,去掉该结点与其他孩子的连线
第三步:调整位置
第一步:将每棵树转换为二叉树
第二步:将每棵二叉树的根节点视为兄弟,从左至右依次相连
第三步:调整位置
第一步:若结点x是其双亲y的左孩子,则把结点x的右孩子、右孩子的右孩子、……都与双亲y连接起来
第二步:去除所有双亲到右孩子之间的连线
第三步:调整位置
1、结点的路径长度:从根结点到该结点路径上的连接数
2、树的路径长度:树中每个叶子结点的路径长度之和
3、结点的带权路径长度:结点路径长度 × 结点权值
4、树的带权路径长度(WPL):树中所有叶子结点带权路径长度之和
5、哈夫曼树:由n个带权叶子结点构成的所有二叉树中带权路径长度最短的二叉树
① 哈夫曼树不存在度为1的结点 只有度为0和2大结点
② n个叶子结点的哈夫曼树有2n-1个结点 (结点数是奇数)
证:哈夫曼树中只有度为0和2的结点,那么度为0的叶子结点为n个,设度为2的
结点个数为y个,根据二叉树的性质,n0 = n2 + 1 ,即n = y+1,y = n-1, 总结点数为2n-1。
eg:w = {5,29,7,8,14,23,3,11}
1、前缀码:如果在一个编码系统中,任一个编码都不是其他任何编码的前缀,则称该编码系统中的编码是前缀码。例如,一组编码01,001,010,100,110就不是前缀码,因为01是010的前缀,若去掉01或010就是前缀码。
2、哈夫曼编码:对一棵具有n个叶子的哈夫曼树,若对树中的每个左分支赋予0,右分支赋予1,则从根到每个叶子的通路上,各分支的赋值分别构成一个二进制串,该二进制串就称为哈夫曼编码。
① 若它左子树不为空,则左子树上所有结点均小于它的根节点的值
② 若它右子树不为空,则右子树上所有结点均大于它的根节点的值
typedef struct BiTNode
{
int data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
(1)若二叉排序树为空,则查找失败,返回空指针。
(2)若二叉排序树非空,将给定值key与根结点的关键字T->data.key进行比较:
① 若key等于T->data.key,则查找成功,返回根结点地址;
② 若key小于T->data.key,则进一步查找左子树;
③ 若key大于T->data.key,则进一步查找右子树。
//指针f指向T的双亲,初始值为NULL
//若查找成功,p指向该节点
//若查找不成功,p指向查找路径上访问的最后一个结点
Status SearchBST( BiTree T, int key, BiTree f, BiTree *p)
{
if(!T) //查找不成功
{
*p = f;
return 0;
}
else if (key == T->data) //查找成功
{
*p = T;
return 1;
}
else if (key < T->data)
return SearchBST(T->lchild,key,T,p); //在左子树中继续查找
else
return SearchBST(T->rchild,key,T,p); //在右子树中继续查找
}
若二叉排序树为空,则插入结点为根节点
当待插入的值大于根结点的值,且根节点的右子树为空时,则将待插入的结点当作右子树插入
当待插入的值小于根节点的值,且根节点的左子树为空时,则将待插入的结点当作左子树插入
Status InsertBST( BiTree *T, int key )
{
BiTree p,s;
if(!SearchBST(*T,key,NULL,&p)) //查找不到才插入
{
s = (BiTree)malloc(sizeof(BiTNode));
s->data = key;
s->lchild = s->rchild = NULL;
//p指向查找路径上访问的最后一个结点
if(!p) *T = s; //如果为空树 插入s为新根节点
else if(key < p->data)
p->lchild = s;
else
p->rchild = s;
return 1;
}
else return 0;
}
平衡因子:任一结点的左右子树高度差
任一结点的平衡因子只能取:-1、0 、1;如果树中任意一个结点的平衡因子的绝对值大于1,则这棵二叉树就失去平衡,不再是 AVL树
非平衡二叉排序树 平衡二叉排序树
上图9这个结点的左子树高度为2,右子树高度为0,高度差为2
如果在一棵AVL树中插入一个新结点,就有可能造成失衡,此时必须重新调整树的结构,使之恢复平衡。我们称调整平衡过程为平衡旋转。
文章浏览阅读331次。第一部分:准备工作1 安装虚拟机2 安装centos73 安装JDK以上三步是准备工作,至此已经完成一台已安装JDK的主机第二部分:准备3台虚拟机以下所有工作最好都在root权限下操作1 克隆上面已经有一台虚拟机了,现在对master进行克隆,克隆出另外2台子机;1.1 进行克隆21.2 下一步1.3 下一步1.4 下一步1.5 根据子机需要,命名和安装路径1.6 ..._创建一个hadoop项目
文章浏览阅读1.7k次。心脏滴血漏洞HeartBleed CVE-2014-0160 是由heartbeat功能引入的,本文从深入码层面的分析该漏洞产生的原因_heartbleed代码分析
文章浏览阅读1.4k次。前言ofd是国家文档标准,其对标的文档格式是pdf。ofd文档是容器格式文件,ofd其实就是压缩包。将ofd文件后缀改为.zip,解压后可看到文件包含的内容。ofd文件分析工具下载:点我下载。ofd文件解压后,可以看到如下内容: 对于xml文件,可以用文本工具查看。但是对于印章文件(Seal.esl)、签名文件(SignedValue.dat)就无法查看其内容了。本人开发一款ofd内容查看器,..._signedvalue.dat
文章浏览阅读1.8w次,点赞29次,收藏313次。整体系统设计本设计主要是对ADC和DAC的使用,主要实现功能流程为:首先通过串口向FPGA发送控制信号,控制DAC芯片tlv5618进行DA装换,转换的数据存在ROM中,转换开始时读取ROM中数据进行读取转换。其次用按键控制adc128s052进行模数转换100次,模数转换数据存储到FIFO中,再从FIFO中读取数据通过串口输出显示在pc上。其整体系统框图如下:图1:FPGA数据采集系统框图从图中可以看出,该系统主要包括9个模块:串口接收模块、按键消抖模块、按键控制模块、ROM模块、D.._基于fpga的信息采集
文章浏览阅读2.5w次。1.背景错误信息:-- [http-nio-9904-exec-5] o.s.c.n.z.filters.post.SendErrorFilter : Error during filteringcom.netflix.zuul.exception.ZuulException: Forwarding error at org.springframework.cloud..._com.netflix.zuul.exception.zuulexception
文章浏览阅读358次。1.介绍图的相关概念 图是由顶点的有穷非空集和一个描述顶点之间关系-边(或者弧)的集合组成。通常,图中的数据元素被称为顶点,顶点间的关系用边表示,图通常用字母G表示,图的顶点通常用字母V表示,所以图可以定义为: G=(V,E)其中,V(G)是图中顶点的有穷非空集合,E(G)是V(G)中顶点的边的有穷集合1.1 无向图:图中任意两个顶点构成的边是没有方向的1.2 有向图:图中..._给定一个邻接矩阵未必能够造出一个图
文章浏览阅读321次。(十二)、WDS服务器安装通过前面的测试我们会发现,每次安装的时候需要加域光盘映像,这是一个比较麻烦的事情,试想一个上万个的公司,你天天带着一个光盘与光驱去给别人装系统,这将是一个多么痛苦的事情啊,有什么方法可以解决这个问题了?答案是肯定的,下面我们就来简单说一下。WDS服务器,它是Windows自带的一个免费的基于系统本身角色的一个功能,它主要提供一种简单、安全的通过网络快速、远程将Window..._doc server2012上通过wds+mdt无人值守部署win11系统.doc
文章浏览阅读219次。python–xlrd/xlwt/xlutilsxlrd只能读取,不能改,支持 xlsx和xls 格式xlwt只能改,不能读xlwt只能保存为.xls格式xlutils能将xlrd.Book转为xlwt.Workbook,从而得以在现有xls的基础上修改数据,并创建一个新的xls,实现修改xlrd打开文件import xlrdexcel=xlrd.open_workbook('E:/test.xlsx') 返回值为xlrd.book.Book对象,不能修改获取sheett_xlutils模块可以读xlsx吗
文章浏览阅读8.2w次,点赞267次,收藏656次。运行Selenium出现'WebDriver' object has no attribute 'find_element_by_id'或AttributeError: 'WebDriver' object has no attribute 'find_element_by_xpath'等定位元素代码错误,是因为selenium更新到了新的版本,以前的一些语法经过改动。..............._unresolved attribute reference 'find_element_by_id' for class 'webdriver
文章浏览阅读198次。一:模态窗口//父页面JSwindow.showModalDialog(ifrmehref, window, 'dialogWidth:550px;dialogHeight:150px;help:no;resizable:no;status:no');//子页面获取父页面DOM对象//window.showModalDialog的DOM对象var v=parentWin..._jquery获取父window下的dom对象
文章浏览阅读1.7w次,点赞15次,收藏129次。算法(algorithm)是解决一系列问题的清晰指令,也就是,能对一定规范的输入,在有限的时间内获得所要求的输出。 简单来说,算法就是解决一个问题的具体方法和步骤。算法是程序的灵 魂。二、算法的特征1.可行性 算法中执行的任何计算步骤都可以分解为基本可执行的操作步,即每个计算步都可以在有限时间里完成(也称之为有效性) 算法的每一步都要有确切的意义,不能有二义性。例如“增加x的值”,并没有说增加多少,计算机就无法执行明确的运算。 _算法
文章浏览阅读1.5k次,点赞18次,收藏26次。网络安全的标准和规范是网络安全领域的重要组成部分。它们为网络安全提供了技术依据,规定了网络安全的技术要求和操作方式,帮助我们构建安全的网络环境。下面,我们将详细介绍一些主要的网络安全标准和规范,以及它们在实际操作中的应用。_网络安全标准规范