导图社区 ⑤树与二叉树
24自用408数据结构,树是n个结点的有限集(n≥0),树的高度=树的的层数=树的深度,结点数=边数+1=度数之和+1。
编辑于2023-07-03 15:46:17 广东树与二叉树
树的基本概念
定义
n个结点的有限集(n≥0)
特点
递归性
分层性
n个结点有n-1条边
基本术语
树的高度=树的的层数=树的深度
结点的深度
从根节点开始自顶向下逐层累加
结点的高度
从叶子结点自底向上逐层累加
孩子个数为结点的度,最大度数称为树的度
度为0的结点称为叶子结点(终端结点)
有序树
树中的各子树是从左到右有次序的,不能交换。否则称为无序树
路径
两结点之间经过的结点序列,路径长度为经过的边的数量(经过的结点树加1)
路径是自顶向下的,同一双亲的孩子无路径
树的性质
结点数=边数+1=度数之和+1
度为m和m叉树
高度为h
度为m
至少有h+m-1个结点
度为m的树第i层上至多有m'(i-1)个结点(i≥1)
至少有一个结点的度为m
非空
m叉树
至少有h个结点
允许所有结点的度都小于m
可以为空树
具有n个结点的m叉树的最小高度为
二叉树的概念
定义
每个结点至多只有两棵子树,左右顺序不能颠倒
二叉树的性质
非空二叉树的叶子结点数为
度为2的结点数+1
n0=n2+1
非空二叉树第K层上至多有
高为h的二叉树至多有
具有n个结点的完全二叉树的高度为
对于完全二叉树
若有2k(偶数)个结点,则
n1=1,n0=k,n2=k-1
若有2k-1(奇数)个结点,则
n1=0,n0=k,n2=k-1
二叉树的存储结构
顺序存储
用一组连续的存储单元自上而下,自左至右存储完全二叉树
适用于满二叉树和完全二叉树
对于一般二叉树,需要添加空结点来对照完全二叉树,浪费空间
链式存储
左指针域lchild 数据域data 右指针域rchild
n个结点
指针个数
2n
有效指针
n-1
空链域
n+1
如果经常搜索父结点,可以使用三叉链表
左右孩子指针+父结点指针
特殊的二叉树
满二叉树
一棵高度为h,且含有2'h-1个结点的二叉树称为满二叉树
不存在度为1的结点
完全二叉树
高度为h、有n个结点的二叉树,当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时,称为完全二叉树
特点
i≤(n/2向下取整),则结点i为分支结点,否则为叶子结点
叶子结点只可能在最大两层出现,且对于最大层来说,叶子结点依次排列在该层最左边的位置
若有度为1的点,有且仅有一个,且只有左孩子
按层编号,一旦出现i结点只有左孩子或者为叶子结点,则大于i的结点都为叶子结点
若n为奇数,每个分支结点都有左右孩子;若n为偶数,则编号最大的分支结点(编号为n/2)只有左孩子,其余分支结点都有左右孩子
二叉排序树
左子树上所有结点的关键字均小于根结点的关键字;右子树所有的结点的关键字均大于根结点
左子树和右子树又是一棵二叉排序树
平衡二叉树
树上任一结点的左子树和右子树的深度之差不超过1
对于编号为i的结点 完全二叉树和满二叉树
双亲
左孩子
2i
右孩子
2i+1
结点i所在层次
二叉树的遍历和线索二叉树
二叉树的遍历
按某条搜索路径访问树中每个结点,使得每个结点都被访问一次,而且仅被访问一次
先序遍历(先根遍历)
Preorder
前缀表达式
递归算法
visit(T) Preorder(T->lchild) Preorder(T->rchild)
非递归算法
1| 沿着根的左孩子,依次访问,直至左孩子为空
2| 若右兄弟不空,将右兄弟转执行①;否则执行回溯至父结点执行②
中序遍历(中根遍历)
Inorder
中缀表达式
递归算法
Inorder(T->lchild) visit(T) Inorder(T->rchild)
非递归算法
后序遍历(后根遍历)
Postorder
后缀表达式
递归算法
Postorder(T->lchild) Postorder(T->rchild) visit(T)
非递归算法
应用
访问一个结点p时,栈中结点恰好是p结点的所有祖先,从栈底到栈顶结点再加上p结点,刚好构成从根结点到p结点的一条路径
求根到某结点的路径,求两个结点的最近公共祖先
层次遍历
使用队列
步骤
1| 根结点入队,然后出队,并访问出队结点
2| 若有左子树,左子树根结点入队;若有右子树,右子树根结点入队,重复①②
遍历序列构造二叉树
中序序列
+先序序列
+后序序列
+层序序列
线索二叉树
基本概念
利用传统的二叉链表的n+1个空指针
目的
加快查找结点前驱和后继的速度
标志域
ltag
ltag=0
lchild指向左孩子
itag=1
lchild指向前驱
rtag
rtag=0
lchild指向右孩子
rtag=1
lchild指向后继
中序线索二叉树的构造
使用中序遍历的顺序构造二叉树
处理遍历的最后的一个结点需要将其rchild置空
可增设一个头结点,形成一个双向链表
中序线索二叉树的遍历
若结点右标志为′1′,则右链为线索,指示其后继, 否则遍历右子树中第一个访问的结点(右子树中最左下的结点)为后继
第一个结点为最左下结点,不一定为叶结点
最后一个结点为最右下结点,为叶子结点
先序和后序类似
先序找后继
若有左孩子,左孩子即为后继;若无左有有,则右孩子为;若为叶子结点,则右链域直接指示了后继
后序找后继
根结点无后继
若结点为双亲的右孩子,或者是双亲的左孩子且双亲无右孩子,则后继为双亲
若结点为双亲的左孩子,若有右兄弟,后继为右兄弟子树的第一个后序遍历出的结点
后序有时无法找到后继,需采用三叉链表,先找到双亲
后序线索二叉树仍需栈递归
树、森林
树的存储结构
画图
双亲表示法
采用一组连续空间来存储每个结点,同时在每个结点中增设一个伪指针,指示双亲结点在数组中的位置
根结点下标为0,伪指针域为-1
优缺点
优:可以很快找到双亲结点
缺:找孩子结点时需要遍历整个结构
孩子表示法
将每个结点的孩子结点都用单链表链接起来形成一个线性结构
n个结点,n个链表
优缺点
寻找子女简单
寻找双亲的操作需要遍历n个结点中孩子链表指针域所指向的n个孩子链表
孩子兄弟法(二叉树法) 左孩子右兄弟
以二叉树链表作为树的存储结构。三个部分内容:结点值、指向结点第一个孩子结点的指针,及指向结点下一个兄弟结点的指针(沿此域可以找到结点的所有兄弟结点)
优缺点
实现树转换为二叉树的操作,易于找结点的孩子
从当前结点查找其双亲结点比较麻烦
若设置一个指针域指向双亲结点,那么查找双亲结点也很方便
树、森林与二叉树的转换
树转换为二叉树规则
左孩子右兄弟法
每个结点的左指针指向它的第一个孩子,右指针指向它在树中相邻的右兄弟
森林转换为二叉树
与树相似,先把每一个树转为为二叉树,再把每棵树的根结点当作兄弟连接
二叉树转为森林
二叉树的根及左子树为第一棵树,将其断开,二叉树的右子树又可以视为一个新的二叉树,继续重复断开,直至没有右子树为止
二叉树转为森林是唯一的
树和森林的遍历
先根遍历
与先序序列相同
后根遍历
与中序序列相同
树与二叉树的应用
哈夫曼树和哈夫曼编码
哈夫曼树定义
带权路径长度(WPL)最小的二叉树称为哈夫曼树,也称最优二叉树
带权路径长度:从树根到任意结点的路径长度(经过的边数)与该结点上权值的乘积。
哈夫曼树的构造
步骤
特点
1| 每个初始结点最后都是叶结点
2| 权值越小的结点到根结点的路径长度越大
3| 构造过程共新建立了n-1个结点,且新结点都是双分支结点,结点总数为2n-1
4| 不存在度为1的结点
5| 哈夫曼树不唯一
哈夫曼编码
一种被广泛应用而且非常有效的数据压缩编码
数据编码方式
固定长度编码
可变长度编码
可变长子网划分
允许对不同字符用不等长的二进制为表示
可以减少数据存储空间,起到数据压缩的作用
可变比固定好
前缀编码
没有一个编码是另一个编码的前缀
向左为0,还是向右为1,不固定
哈夫曼树不唯一,但是WPL是唯一的
并查集
三要素
逻辑结构
元素之间为“集合”关系
基本操作
初始化
初始化并查集
Find(S[],x):查,查找一个元素
Union(s[],Root1,Root2):并,将Root2并入Root1
存储结构
使用森林的双亲表示法存储,顺序存储,每个组织为一棵树
优化
优化并操作
使用根的绝对值表示一棵的结点总数
将小树合并至大树
树高
不超过(log2n向下取整)+1
查操作时间复杂度
O(log2n)
优化查操作
“压缩路径”策略,每次find操作先找到x所属根结点,再将查找路径上的所有结点都直接挂在根结点下面
查并:时间复杂度O(α(n))