北京治疗白癜风哪个医院看好 http://pf.39.net/bdfyy/xwdt/7树（tree）
树是n个节点的有限集合。n=0时为空树；在任意的树中有且仅有一个称为根节点的，当n1时，其余节点分为m个互不相交的有限集合（T1,T2......Tm）;每个树的本身又是一棵树，并且称为根的子树；
7.1结点分类：
根节点、叶节点、度
7.2结点关系：
双亲、孩子、兄弟
7.3其他概念
层次、深度、有序树、无序树、森林。
从根节点开始为第一层，孩子为第二层等等，从根到叶子层数为深度或高度。（最大）
树中各子树从做右使有序的，有序树。m个（m=0）个互不相交的树的集合，即森林。
线性结构与树结构
7.4树的存储结构：
顺序存储结构中结点的位置无法反映结点之间的逻辑关系，所有利用顺序存储结构和链式存储结构的特点，可以实现对树的表示。双亲表示法、孩子表示法、孩子兄弟表示法。
7.4.1双亲表示法：除了数据，每个结点设置一个指向双亲节点的位置。
节点结构
找双亲时间复杂度O(1);找孩子需要遍历整个树O(n)。
7.4.2孩子表示法：考虑有多个孩子的情况，用多指针域，指向多个孩子。（多重链表表示法）
方案一：孩子的个数就是树的度。
缺点：度相差大时候浪费空间，因为指针域为空。
优点：度相差小时候节省空间。
方案二：
degree度域表示该结点度，存储孩子结点的个数。
空间利用率高，但是也带来维护度的开销。
孩子表示法：
每个节点的孩子节点用单链表，n个结点有n个孩子单链表，n个头节点组成的顺序表采用顺序存储结构，存放在一个一维数组中。
表头数组的头结点：data数据域，firstchild头指针域
表示孩子结点：child数据域、next指针
要找双亲怎么办？改进的孩子双亲表示法
7.4.3孩子兄弟表示法：当两个指针指向是唯一的。
查找孩子比较容易，查找双亲比较麻烦，可以增加指向双亲指针。
7.5二叉树
7.5.1概念
有一个根节点或者有两颗互不相交的，分别称为根结点的左子树和右子树的二叉树组成。（折半查找）某个阶段只有两种结果的情形（开关、上下、大小、0和1、正和反）都适合用树状结构建模。
7.5.2特点
1.每个结点最多有两个子树，度不大于2；
2.左右子树是有序的；
3.即使只有一个子树，也是有序的；
7.5.3形态
三个结点五种形态：
7.5.4特殊的二叉树
4.斜树：左斜树（只有左子树）、右斜树。
5.满二叉树：叶子出现在最下一层；非叶子结点度必须为2；与同深度树比较，满二叉树叶子节点最多，结点也最多。
6.完全二叉树：完全二叉树结点编号位置与满二叉树结点位置相同。
7.5.5二叉树性质
如下：n2=4,n0=5n1=1;n0=n2+1;(推到过程见书p)
7.5.6存储结构
a、顺序存储结构：用一个一维数组存储二叉树结点。一般只用于完全二叉树。
完全二叉树：
一般二叉树：
极端二叉树：（斜树）
b、链式存储：二叉链表，及一个数据域两个指针域。
7.5.7二叉树遍历
从根节点出发，按照某种次序依次访问二叉树所有结点，每个结点被访问一次且仅访问一次。
访问方法：前序、中序、后续。
a、前序遍历：ABDGHCEIF（先根-左-右）
b、中序遍历：GDHBAEICF（先左-根-右）
c、后序遍历：GHDBIEFCA（先左-右-根）
d、层序遍历：ABCDEFGHI（先根-第一层-......-第n层）
遍历代码算法实现：前序、中序、后序；（递归）
推导遍历：
前序遍历：ABCDEF
中序遍历：CBAEDF
已知前序和中序、中序和后序是能确定一个二叉树的。
7.5.8线索二叉树
指向前驱和后继的指针称为线索。线索链表，线索二叉树。
因为n个结点的二叉树有n+1个空指针
线索化：对二叉树的某种遍历使其变为线索二叉树过程。
7.5.9树、森林与二叉树转换
树转化为二叉树
森林转化为二叉树
二叉树转化为树
二叉树转换为森林
7.6赫夫曼树及其应用
最基本的压缩编码方法-赫夫曼编码。
赫夫曼树（美国数学家赫夫曼年发明赫夫曼编码）在赫夫曼编码中用的特殊的二叉树称为赫夫曼树
7.6.1赫夫曼树定义域原理
路径长度：从树中一个结点到另一个结点之间分支构成两个结点之间的路径，路径上分支数目就称为路径长度。
树的路径长度就是从根到每一个结点的路径长度之和。
例子：学生成绩，A表示不及格、B表示及格、C表示中等、D表示良好、E表示优秀。
路径长度：
a树：1+1+2+2+3+3+4+4=20
b树：1+2+3+3+2+1+2+2=16
带权路径长度WPL最小的二叉树称为赫夫曼树。
a树WPL=5*1+15*2+40*3+30*4+10*4=；
b树WPL=5*3+15*3+40*2+30*2+10*2=;
结论：名学生做分数统计：a树需要次；b树需要00次。
7.6.2赫夫曼树构造：
A5、E10、B15、D30、C40
WPL=40*1+30*2+15*3+10*4+5*4=;
7.6.3赫夫曼编码
主要是为了解决远距离通信（当年电报）数据传输最优化问题。
例子：ABCDEF;字母使用频率A-27、B-8、C-15、D-15、E-30、F-5;
构建好的赫夫曼树，然后将权值替换为左0右1。
对六个字母从根到叶子编码后，如下图
对BADCADFEED编码：
原编码二进制串：0011101100(共30个字符串)
新编码二进制串：100(共25个字符串)
很明显数据压缩了，长度不一容易混淆，前缀编码可解决该问题，即任何一个编码都不其他编码的前缀。同时发送方和接收方需要约定好编码规则。
解码：如代表B,01代表A等等。
