数据结构--树

参考青岛大学-王卓老师

一、关于树的定义

树是n个结点的有限集合(是一种递归的表示)
树的表示方式:嵌套集合 、广义表、凹入表示
树中的亲子关系 :
在这里插入图片描述
树一定是森林,森林不一定只有一颗树

二、关于二叉树的定义

二叉树的优点:结构简单、规律性强;所有数都能转换成唯一对应的二叉树。
二叉树:根结点(最多仅有两个孩子)、左子树、右子树(左右顺序有区分)组成。
二叉树的性质和存储结构
性质:

    二叉树的i层至多有2`(i-1)个结点,最少1个结点 深度为k的二叉树最多有2`k-1个结点 对于任何一个二叉树T,其叶子数为n0,度为2的结点数为n2,则n0=n2+1 具有n个结点的完全二叉树深度为?log2n?+1 结点之间编号的关系
    在这里插入图片描述
    存储结构:
    顺序存储,更适合满二叉树或者完全二叉树存储
    链式存储,
    在这里插入图片描述
    三叉链表可以指向双亲

三、遍历二叉树和线索二叉树

1.遍历二叉树

按层遍历
先序:DLR先根遍历
中序:LDR中根遍历
后序:LRD后根遍历
在这里插入图片描述
先:按照根左右的顺序:ABELADHMIJ
中:按照左根右的顺序:ELBAMHIDJ
后:按照左右根的顺序:LEBMIHJDA
由二叉树的先序和中序或者后序和中序可以确定唯一的二叉树
在这里插入图片描述
算法:
递归算法:在这里插入图片描述
栈算法:
在这里插入图片描述
层次遍历算法:
在这里插入图片描述
将其转换为字符的算法:
在这里插入图片描述
复制二叉树:
在这里插入图片描述
计算二叉树的深度:
在这里插入图片描述

2.线索二叉树

在这里插入图片描述
tag=0指向孩子
tag=1指向前驱

在这里插入图片描述

四、树和森林

树的存储结构:

    双亲表示法:数据域和双亲域,特点:找双亲容易,找孩子难 孩子链表:特点:找孩子容易,找双亲难
    在这里插入图片描述 孩子兄弟表示法(二叉树表示法、二叉链表表示法)
    数据域左侧为第一个孩子,右侧为兄弟
    在这里插入图片描述

将树转换成二叉树的步骤

    加线:在兄弟之间加一条连线 抹线:对每个结点,除了左孩子之外,去除其与其余孩子之间的联系 旋转:以树的根结点为轴,将整个树顺时针旋转45度

将树转换成二叉树的步骤:兄弟相连留长子
在这里插入图片描述

将二叉树转换成树的步骤:左孩右右连双亲,去掉原来右孩线
在这里插入图片描述

森林转换为二叉树:树变二叉根相连
在这里插入图片描述

二叉树转换为森林:去掉全部右孩线(将与根结点相连的右孩子的连线删除),孤立二叉再还原
在这里插入图片描述

树的遍历:先根遍历、后根遍历、按层遍历
森林的遍历:
先序遍历:遍历森林中第一棵树的根结点,先序遍历森林中第一棵树的子树森林,先序遍历森林中其他树构成的森林
中序遍历:中序遍历森林中第一棵树的子树森林,访问森林中第一棵树的根结点,中序遍历其余树构成的森林

五、哈夫曼树及应用

带权路径长度:路径长度*权重之和
哈夫曼树是带权路径长度最短的树,最优二叉树(权大的离根远)
哈夫曼树构造的方法:
构造森林全是根;选用两小造新树。
删除两小添新人;重复二三剩单根。
在这里插入图片描述
哈夫曼编码
左0右1
在这里插入图片描述
文件编码和解码
1.编码:
a.输入各字符极其权重
b.构造哈夫曼树HT[i]
c.进行哈夫曼编码HC[i]
d.查HC[i],得到各个字符的哈夫曼编码
2.解码:
a.构造哈夫曼树
b.依次读入二进制码
c.读入0则走向左孩子,读入1则走向右孩子
d.一旦到达某叶子时,即可译出字符
e.从根出发继续译码,指导结束