住房和城乡建设部中国建造师网站,住房和城乡建设部资质延期,app软件定制研发,公司网站开发交接注意事项一、树的定义
树是一个有n个#xff08;n0#xff09;结点的有限集合。
如果n0#xff0c;称为空树#xff1b;
如果n0#xff0c;称为非空树#xff0c;有且仅有一个特定的称为根Root的结点#xff08;无直接前驱#xff09;
如果n1,除了根节点外n0结点的有限集合。
如果n0称为空树
如果n0称为非空树有且仅有一个特定的称为根Root的结点无直接前驱
如果n1,除了根节点外其他结点划分为m个互不相交的有限集合记为T1、T2...TM每个集合本身又是一棵树称为根的子树Sub-tree。
每个结点肯定有唯一的前驱除根节点外但是可能有多个后继。
二、树的术语
结点包含一个数据元素及若干指向其子树的分支
结点的度结点拥有的子树个数也即结点包含的分支个数
叶子结点终端结点
度为0的结点 {K,L,F,G,M,I,J}
分支结点非终端结点
度不为0的结点 {A,B,C,D,E,H}
包含根结点
内部结点除根之外的分支结点 {B,C,D,E,H}
孩子结点的子树的根
双亲孩子的直接前驱
兄弟同一个双亲的其他孩子
子孙以某结点为根的树中所有的结点
祖先从该结点到根结点经过所有分支结点
树的层次
根结点为第一层根的孩子为第二层依次类推。
深度树中最大的层次
森林互不相交的树的集合。对于树中每个结点而已其子树的集合就是森林 二叉树 Binary Tree
每个结点最多只有两棵子树 最多两个孩子
二叉树的子树可以分成左右两个部分 称为左子树和右子树 二叉树的性质1
在二叉树的第i层上至多有2i-1个结点
深度为k的二叉树至多有2^k-1个结点
如果二叉树终端结点数为n0,度为2的结点数为n2则non21
证明思路总结点数nnon1n2
考察分支数B除了根之外所有的结点都有且只有一个分支指向它不同度的结点产生不同个数的分支 nB1
不同度的结点产生不同个数的分支Bn12n2
non21 五、满二叉树
一个深度为k且有2^^k-1个结点的二叉树
每层上的结点数都是最大数 可以自上而下、自左至右连续编号
完全二叉树 当且仅当每一个结点都与深度相同的满二叉树中编号从1到n的结点一一一对应的二叉树
叶子结点只在最大两层上出现
以任何一个结点为根结点其左子树深度与右子树深度相等或大于1
具有n个结点的完全二叉树 其深度为log2n取整1
七、二叉树的存储结构顺序存储
用一组连续的存储单元依次自上而下自左至右存储结点
对于一般二叉树空结点的位置也要按照完全二叉树编号 八、二叉树的链式存储结构
1、二叉链表
采用数据域加上左右孩子的指针
2、二叉链表的定义
二叉链表的一个结点的可以用一个结构体表示里面包含的成员有一个数据域两个指针域
struct BiNode binode 双节点 node:节点
{
char data;
BiNode *Ichild,*rchild;
}
3、二叉树的链式存储结构
只能双亲找孩子孩子难以找到双亲
4、二叉树的链式存储结构
三叉链表 遍历二茶树
根据访问根结点的次序
DLR
LDR
LRD
先序
boid PreOrderTraverse(BinTree T)
{
if(T)
{
coutT-data;
PreOrderTraverse(T-IChild);
PreOrderTraverse()T-rChild):
先序中序、中序后序
都可以求出二叉树
而先序和后序不可以
因为不具备确定左右子树的能力。 树的存储结构
双亲表示法 找双亲容易找孩子难 孩子表示法最大的缺点就是空指针链域太多 有些结点有很多孩子 有些结点的孩子很少结构不均衡
n结点的树 度为d 多链表表示法中 空指针必有[d-1n1] 树的路径
路径从树的一个结点到另一个结点之间的分支构成了两个结点之间的路径
路径长度路径上的分支的数目
树的路径长度从根结点到每个结点之间路径长度的和
如果结点权重不一样我们可以计算带权路径长度
从结点到根结点之间的路径长度乘以该结点的权重
树的带权路径长度WPL Weighted path length
树中所有叶子结点的带权路径长度之和度为0
相同的叶子结点数叶子结点也具有相同的权重但是不同的二叉树会产生不同的WOL 引出概念
树的带权路径长度WPL最小的二叉树被称为最优二叉树
Huffman 哈夫曼树
有什么special的place
权值最大的结点离根最近
权值最小的结点离根最远 有了编码
怎么解码
要能唯一解码对编码有什么要求
要求前缀编码
即任何一个字符编码都不是其他字符的前缀
Huffman是一种前缀编码
