数据结构第五章(上)

5 树和二叉树

树形结构与线性结构的不同就是，线性结构的前驱和后继是一对一的，树状结构属于非线性结构，有多个后继。前驱与后继是一对n的

树是个n个结点的有限集：
- 若n=0，称为空树；
- 若n>0，则他满足如下两个条件：
  1. 有且仅有一个特定的称为根的结点
  2. 其余结点可分为吗（m>=0）个互不相交的有限集T1,T2,T3。。

根结点：非空树中无前驱结点的结点。
结点的度：结点拥有的子树数。
树的度：树内各结点的度的最大值。
结点的子树的根称为该结点的孩子，该结点称为该孩子的双亲，还有结点的祖先，结点的子孙就不展开描述了。
有序树：树中结点的各子树从左至右有次序（最左边的为第一个孩子）。
无序树：树中结点的各子树无次序。
森林：是m棵互不相交的树的集合
- 把根结点删除树就变成了森林
- 一棵树可以看成是一个特殊的森林，树一定是森林，森林不一定是树
- 给森林中各子树加上一个双亲节点，森林就变成了树

二叉树的结构最简单，规律性最强，可以证明所有树都能转化为唯一对应的二叉树，不失一般性。

二叉树：是n个结点的有限集，他或者是空集或者是由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成
- 特点：每个节点最多两个孩子
- 子树有左右之分(即使只有一棵子树也进行区分)，次序不能颠倒
- 二叉树可以是空集合，根可以有空的左子树或空的右子树。
- 具有三个结点的树可能有几种形态？

将数据文件转换成由0、1组成的二进制串，称之为编码

具体的方法到哈夫曼树和哈弗曼编码那里学习，这里暂且按下不表

以二叉树表示表达式的递归定义如下：
1. 若表达式为数或简单变量，则相应二叉树中仅有一个根结点，其数据域存放该表达式信息；
2. 若表达式为 “ 第一操作数运算符第二操作数” 的形式，则相应的二叉树中以左子树表示第一操作数，右子树表示第二操作数，根结点存放运算符，其中错作数本身又为表达式。

具体实现，我们会在[5.8 案例分析与实现](####5.8 案例分析与实现)进行讲解

在二叉树的第i层上之多有$\large 2^{i-1}$个结点
深度为k的二叉树至多有$\large 2^k-1$个结点
对任何一棵二叉树T，如果其叶子树为$\large n_0$,度为2的结点数为$\large n_2$，则$\large n_0=n_2+1$
- 总边数$\large B=n-1 = B=n_22+n_11$
- 总结点数为$\large n=n_22+n_11+1$ 又 $n=n_2+n_1+n_0$
- 推导出$\large n_0=n_2+1$
具有n个结点的完全二叉树的深度为[log_2n]（向下取整）+1

性质4表明了完全二叉树结点数n与完全二叉树深度k之间的关系
如果对一棵有 n个结点的完全二叉树，其结点按层序编号（从第 1 层到第[log2n]+ 1 层，每层从左到右），则对任一结点(n=>i>=1), 有如果i=1，无双亲，如果i>1.则其双亲是结点[$\large i/2$]。
1. 性质5表明了完全二叉树中双亲结点编号与孩子结点编号之间的关系