文档章节

数据结构—树

devbird
 devbird
发布于 2017/02/04 14:58
字数 1304
阅读 12
收藏 2

一、树的基本概念

1、树的概念

树(Tree)是n(n>=0)个节点的有限集。n=0时称为空树。在任意一棵非空树中:①有且仅有一个特定的称为根(Root)的借点;②当n>1时,其余节点可分为m(m>0)个互不相交的有限集,其中每一个集合本身又是一棵树,并且称为根的子树(SubTree)。

2、节点的度

结点拥有的子树数称为结点的度。度为0的结点称为叶子结点或终端结点,度不为0的结点称为非终端结点或分支结点。除根结点以外,分支结点也称为内部结点。树的度是树内各结点的度的最大值。
节点的度

3、层次与深度

节点的层次从根开始起定义,根为第一层,根的孩子为第二层,后面的依此类推,树中节点的最大层次称为树的深度或高度。
树的深度


二叉树的基本概念和性质

1、二叉树概念

二叉树(Binary Tree)是n(n>=0)个节点的有限集合,该集合或则为空集(称为空二叉树),或则由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。
二叉树

2、满二叉树概念

在一棵二叉树中,如果所有分支节点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称为满二叉树。
满二叉树

3、完全二叉树概念

对一棵具有n个节点的二叉树按层序编号,如果编号为i(i>=1 && i<=n)的节点与同样深度的满二叉树中编号为i的节点在二叉树中位置完全相同,则这棵二叉树称为完全二叉树。
完全二叉树

4、二叉树的性质

二叉树的性质

性质3证明:
设n为总结点数,n1为度为1的结点数,n2为度为2的结点数,n0为终端结点数。用代数表达就是分支总数=n-1=n1+2n2,因为刚才有等式n=n0+n1+n2,所以推导出n0+n1+n2-1=n1+2n2,所以得出结论n0=n2+1。
图片说明


三、树、森林、二叉树的转换

1、树转换为二叉树

① 加线。在所有兄弟节点之间加一条线。
② 去线。对树中每个节点,只保留它与第一个孩子节点的连线,删除它与其他孩子节点之间的连线。
③ 层次调整。以树的根节点为轴心,将整棵树顺时针旋转一定的角度,使之结构层次分明。注意第一个孩子是二叉树节点的左孩子,兄弟转换过来的孩子是节点的右孩子。
树转换为二叉树
####2、森林转化为二叉树
① 把每棵树转为二叉树
② 第一棵二叉树不动,从第二棵二叉树开始,依次把后一棵二叉树的根节点作为前一棵二叉树的根节点的右孩子,用线连接起来。当所有的二叉树连接起来后就得到了由森林转换来的二叉树。
森林转化为二叉树

3、二叉树转换为树

① 加线。若某节点的左孩子节点存在,则将这个左孩子的右孩子节点、右孩子的右孩子节点、右孩子的右孩子的右孩子节点......,即左孩子的n个右孩子节点都作为此节点的右孩子。将该节点与这些右孩子节点用线连接起来。
② 去线。删除原二叉树中所有节点与其右孩子节点的连线。
③ 层次调整。使之层次结构分明。
二叉树转换为树


四、哈夫曼树

给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。

1、哈夫曼树基本术语

① 路径和路径长度:在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1,则从根结点到第L层结点的路径长哈夫曼树度为L-1。
② 结点的权及带权路径长度:若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权。结点的带权路径长度为:从根结点到该结点之间的路径长度与该结点的权的乘积。
③ 树的带权路径长度:树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为WPL。

2、哈夫曼树的构造

哈夫曼树的构造
哈夫曼树的构造
哈夫曼树构造示意图
哈夫曼树构造示意图
哈夫曼树构造过程
####3、哈夫曼编码
哈夫曼编码哈夫曼编码哈夫曼编码
哈夫曼编码
哈夫曼编码

© 著作权归作者所有

上一篇: 二叉树
devbird
粉丝 0
博文 10
码字总数 16271
作品 0
奉节
程序员
私信 提问
Java 程序员必须掌握的 8 道数据结构面试题,你会几道?

瑞士计算机科学家Niklaus Wirth在1976年写了一本书,名为《算法+数据结构=编程》。 40多年后,这个等式仍被奉为真理。这就是为什么在面试过程中,需要考察软件工程师对数据结构的理解。 几乎...

JAVA高级架构开发
2018/10/07
0
0
应对程序员面试,你必须知道的八大数据结构

瑞士计算机科学家Niklaus Wirth在1976年写了一本书,名为《算法+数据结构=编程》。 40多年后,这个等式仍被奉为真理。这就是为什么在面试过程中,需要考察软件工程师对数据结构的理解。 几乎...

技术小能手
2018/08/29
0
0
算法之树(二,B+树、哈夫曼树、堆、红黑树)(Java版)-持续更新补充

接着来搞树! 支持云栖社区,也希望大家能支持下我的独立博客——白水东城 文章地址: 算法之树(二,B+树、哈夫曼树、堆、红黑树)(Java版)-持续更新补充 一、B+树 B+树的特征 有k个子树的中...

kissjz
2018/08/16
0
0
每周一练 之 数据结构与算法(Tree)

这是第六周的练习题,最近加班比较多,上周主要完成一篇 GraphQL入门教程 ,有兴趣的小伙伴可以看下哈。 下面是之前分享的链接: 1.每周一练 之 数据结构与算法(Stack) 2.每周一练 之 数据...

pingan8787
05/20
0
0
【译】Swift算法俱乐部-字典树

本文是对 Swift Algorithm Club 翻译的一篇文章。 Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目,目前在GitHub上有18000+⭐️,我初略统计了一下...

Andy_Ron
07/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

为构建社交关系链手淘都做了啥?

作者|王卫(泓冰) 出品|阿里巴巴新零售淘系技术部 01、淘宝社交关系推荐的背景 1、互联网下半场到来:互联网的下半场,人口红利消失,各大平台需要对用户做精细化运营,用户的增长和留存是每一...

阿里云官方博客
16分钟前
3
0
Iaas/Paas/Saas有何区别,一个故事告诉你

云计算有三种服务模式,IaaS,PaaS和SaaS。单从英文全称去理解,他们分别是“基础设施即服务”“平台即服务”和“软件即服务”。 这样翻译过来可不好理解,但是我们可以举个例子。现在我们就以...

JEPaaS云平台
24分钟前
3
0
温度传感器怎么测好坏

  温度传感器也就是负温度系数热敏电阻,温度越高,电阻越小,测量时先看其阻值能不能根据温度的变化而变,再看其变化的阻值是不是在标定的范围之内。   有以下四种方法;   1、若是有...

仙溪
24分钟前
3
0
zk中ZooKeeperServer解析

内部类 ChangeRecord 处理PrepRP和FinalRP之间的信息 static class ChangeRecord { ChangeRecord(long zxid, String path, StatPersisted stat, int childCount, List<ACL> acl) {......

writeademo
35分钟前
3
0
LNMP---安装worrdpress、discuz,域名重定向,用户认证,nginx访问日志

4.34 安装wordpress 4.35 安装discuz 4.36 域名重定向 4.37 用户认证 4.38 nginx访问日志 一、安装wordpress 创建博客: 添加一个博客的虚拟主机 blog.tobe.com.conf 做如下更改 安装博客wor...

tobej
36分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部