第六章 树

树是n个结点的有限集。n=0时称为空树。在任何一棵非空树：
（1）有且仅有一个特定的称为根root的结点
（2）当n>1时，其余结点可分为m（m>0）个互不相交的有限集t1、t2、……、tm，其中每一个集合
本身又是一棵树，并且称为根的子树SubTree
结点的度：结点拥有的子树数，度为零的称为叶节点（终端结点）
树的度是节点的度的最大值
树中节点的最大层次，称之为树的深度或高度
森林Forest

双亲表示法 数组
孩子表示法 数组+链表
双亲孩子表示法 P161
孩子兄弟表示法： 最大好处，将一颗复杂的数，变成了一颗二叉树
二叉树 Binary Tree
是n个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个跟结点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。
每个节点，最多两颗子树(一颗、两颗或者零颗都可以的)。二叉树中不存在度大于2的结点
斜树：线性表可以理解为树的一种极其特殊的表现形式
满二叉树：所有分支节点，都有左右节点。共2^x个节点，x是度 P167
叶子只能出现在最下面一层
完全二叉树：
满二叉树一定是完全二叉树，但是完全二叉树不一定是满二叉树
叶子结点：只能出现在最下面两层。
最下层叶子，一定集中在左侧连续位置
倒数第二层，若有叶子节点，一定在最右侧
不存在仅有右子树，没有左子树的情况。
同样节点数的二叉树，完全二叉树的深度最小
6.6二叉树的性质：
1.在二叉树的第i层上最多有2 i-1 个节点 。（i>=1）
2.二叉树中如果深度为k,那么最多有2k-1个节点。(k>=1）
3.n0=n2+1 n0表示度数为0的节点 n2表示度数为2的节点
4.在完全二叉树中，具有n个节点的完全二叉树的深度为[log2n]+1，其中[log2n]+1是向下取整。
5.若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：
(1) 若 i=1，则该结点是二叉树的根，无双亲, 否则，编号为 [i/2] 的结点为其双亲结点;
(2) 若 2i>n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点；
(3) 若 2i+1>n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。
二叉树的存储结构
1、顺序存储，用于完全二叉树较好，充分利用空间
2、链式存储
二叉链表
三叉链表 加上指向双亲的指针域
遍历二叉树
traversing binary tree
二叉树的遍历：从根节点出发，按照某种次序依次访问二叉树中所有节点，使得每个结点被访问一次
将树中的节点，变成某种意义的线性序列，方便计算机处理
1．前序遍历
规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。
2．中序遍历
规则是若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。
3．后序遍历
规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点
4．层序遍历
规则是若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。
已知中序遍历序列和后序遍历序列，可以唯一确定一颗二叉树
已知中序遍历序列和前序遍历序列，可以唯一确定一颗二叉树
已知后序遍历序列和前序遍历序列，不能唯一确定一颗二叉树
宽度(广度)优先遍历：层序遍历
深度优先遍历
二叉搜索树
堆：最大堆，最小堆
红黑树：树中的结点，定义为红黑两种颜色，并通过规则确保从根节点到叶节点的最长路径长度不超过最短路径的两倍。
6.9二叉树的建立P187
原二叉树的扩展二叉树
键盘依次输入前序遍历序列，代码按前序遍历的顺序依次构建节点。
6.10线索二叉树
二叉链表，会有很多个空闲的指针域，浪费空间，可以用这些空间来干些什么呢？
空余的指针域用来，存储前驱后继的指针(线索)
线索：指向前驱和后继的指针5
线索链表：加上线索的二叉链表
线索化：将二叉树转变成一个双向链表
对二叉树进行某种次序遍历，使其变为线索二叉树的过程称之为线索化
线索化，其实质是将二叉链表中的空指针，指向前驱或后继的线索
线索化的过程,就是在遍历的过程
6.11数、森林、二叉树的转换
将树转换为二叉树：
1.加线。在所有兄弟结点之间加一条连线。
2.去线。对树中每个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的连线。
3.层次调整。以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。注意第一个孩子是二叉树结点的左孩子，兄弟转换过来的孩子是结点的右孩子。
森林转换成二叉树
二叉树转换成树
二叉树转换成森林
二叉树的根节点有右孩子，则转换出来就是森林；若没有，转换出来就是树
6.12赫夫曼树及其应用
最基础的压缩编码方法：赫夫曼编码
路径长度
带权路径长度 WPL
带权路径长度WPL最小的二叉树称作赫夫曼树
哈夫曼树