数据结构复习
树
树：是由n个节点构成的有限集合T，n=0为空树，n!=0,满足
- 有root
- 除root外，其他节点被分成互不相交的有限集合，每个集合也是树
结点的度：拥有的子树数目，即有几个分支
叶结点：度为0
分支节点：度不为0
孩子节点：某一结点的直接后继
父亲结点：某一结点的直接前继
结点的层次：root为1层
书的高度：最大层次
有序树：从左到右子树有序，不可交换
无序树：次序不重要
森林：互不相交的树的集合
二叉树
- 有序树
- 左右之分
满二叉树
任意一层的节点个数达到了最大值
高度为k的二叉树有$2^k-1$个结点
完全二叉树
只有最下面两层结点的可以小于2，且最下面一层的结点都在最左边的连续位置
正则二叉树
除了叶节点，所有分支节点度为2
扩充二叉树
在出现空子树的位置填充叶结点
二叉树性质
- 非空二叉树的i层最多有$2^{i-1}$个结点
- 深度为k的二叉树最多有，${2^{k}-1}$个节点
- 任意二叉树,叶节点个数为$n_0$,度为2的分支结点为$n_2$个,则$n_0=n_2-1$
存储结构
顺序存储
链式存储
二叉树遍历
深度优先
D表示访问根节点
R表示遍历右子树
L表示遍历左子树
前序
DLR
中序
LDR
后序
LRD
广度优先
- 根结点入队
- 队列非空循环3~5
- 出队一个结点并访问
- 左孩子入队
- 右孩子入队
树的存储结构
双亲表示法
孩子表示法
孩子兄弟表示法
树的遍历
深度优先
广度优先
树和二叉树的应用
表达式树
哈夫曼树
- 路径:从一个结点到另一个节点的分支序列
- 路径长度
- 结点权值
- 结点的加权路径长度:从根节点到某个结点的路径长度与该结点的权值的乘积
- 树的加长路径长度WPL:$\sum_{i=1}^{n}w_i l_i$
- n个具有权值的叶节点构成的二叉树中,WPL最小的那个
性质
- 有n个叶结点的,总共结点2n-1
- 权值越大的结点离根节点跃进
- 正则二叉树
- 左右子树交换仍然是哈夫曼树