树和二叉树
树
1.树中概念总结
- 节点的度：一个节点含有的子树的个数成为该节点的度
- 树的度：一棵树中，最大的节点度成为树的度
- 兄弟节点：具有相同父节点的节点互称为兄弟节点
- 节点层次：根为1层，依次递增
- 堂兄弟节点：父节点在同一层的节点互为堂兄弟
- 节点祖先：从根到该节点所经分支上的所有节点，从根节点到此节点的路径中除了此节点本身，其余节点均为此节点的祖先节点，（儿子->父亲->父亲的父亲->…->根）
- 子孙节点：以该节点为根的子树中的任一节点均为该节点的子孙节点
- 深度：对于任意节点n，n的深度为从根到n的唯一路径长度，根的深度定为0
- 高度：对于任意节点n，n的高度为从n到叶节点的最长路径长度，所有叶节点的高度为0
- 森林：由m（m>=0）棵互不相交的树的集合成为森林
- 有序树： 结点各子树从左至右有序，不能互换
- 无序树： 结点各子树可互换位置
2.树的定义
- 树是由n个结点组成的有限集，且对于非空树：
- 有且仅有一个特定的称为根的结点；
- 当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每一个集合本身又是一棵树，称为根的子树。
3.树的性质
- 树有先根遍历和后根遍历两种方法
- 先根遍历：先访问树的根节点，再依次先根遍历子树；
- 后根遍历：先依次后根遍历子树，再访问树的根节点。
- 之所以没有中序遍历是因为树未必就是二叉树，子树有多个，可选择的序列也就有多个（比如根节点下有3个子树，分别为a，b，c，不考虑根节点的遍历顺序，仅这3个子树就是 3! 种遍历顺序），所以仅考虑是先遍历子树还是先遍历根节点这两种方式。而树的先根遍历与对应二叉树的中序遍历结果是一样的，理由我还没想懂。
- 若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用c遍历方法最合适。
- A．前序
- B．中序
- C．后序
- D．按层次
4.输的存储结构
- 双亲表示法
- 孩子表示法
- 孩子兄弟表示法
二叉树
1.二叉树的概念
- n (n≥0)个结点的有限集合。当n=0时称为空树。
- 在一棵非空树T中：
- 有一个特定的称为根的结点；
- 除根结点之外的其余结点被分成两个互不相交的有限集合T1和T2，且T1和T2都是二叉树，并分别称之为根的左子树和右子树。
2.二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。
3.二叉树的基本特点：
- 结点的度小于等于2
- 二叉树的子树有左右之分，其次序不能颠倒。如具有3个结点的二叉树有5种不同形态
4.二叉树的性质：
- 性质1：在二叉树的第 i 层上至多有2i-1个结点, 第 i 层上至少有 1 个结点
- 性质2: 深度为 k 的二叉树至多有2k - 1个结点, 深度为 k 的二叉树至少有k个结点
- 性质3: 对于任何一棵二叉树T，如果其叶子结点数为n0，度为2的结点数为n2，则n0 = n2 + 1。
- 性质4： 具有n个结点的完全二叉树的深度为 log2n下取整加一。
- 性质5： 对于完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，右孩子编号必为2i＋1，双亲的编号必为i / 2。
5.特殊形态的二叉树
- 满二叉树: 一棵深度为k 且有2k -1个结点的二叉树。
- 完全二叉树: 深度为k 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k 的满二叉树中编号从1至n的结点一一对应。(只有最后一层叶子不满，且叶子全部集中在左边)
6.满二叉树的特点：
- 叶子只能出现在最下一层
- 只有度为0和度为2的结点
- 在同样深度的二叉树中叶子结点（结点）个数最多
7.完全二叉树的特点：
- 叶子结点只能出现在最下两层，且最下层的叶子结点都集中在二叉树的左部；
- 完全二叉树中如果有度为1的结点，只可能有一个，且该结点只有左孩子。
- 深度为k的完全二叉树在k-1层上一定是满二叉树。
8.满二叉树和完全二叉树的区别：
- 满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。
9.二叉树的遍历
- 遍历定义：
- 指以一定的次序访问二叉树中的每个节点，并且每个节点仅被访问一次。
- “访问”的含义：
- 输出结点的信息
- 遍历用途：
- 是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。
遍历方式：
由二叉树的先序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树
- 但由先序序列和后序序列却不一定能唯一地确定一棵二叉树。
11.用二叉链表（l_child, r_child）存储包含n个结点的二叉树，结点的指针域中有 n + 1个空指针
二叉树，树，森林转化
1.将树转换成二叉树:
- 加线：在兄弟之间加一连线
- 抹线：对每个结点，除了其左孩子外,去除其与其余孩子之间的关系
- 旋转：将同一孩子的连线绕左孩子旋转45度角。
- 树转换成的二叉树其右子树一定为空
2.将二叉树转换成树:
- 加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都与p的双亲用线连起来
- 抹线：抹掉原二叉树中双亲与右孩子之间的连线
- 调整：将结点按层次排列，形成树结构
- 操作要点：把右孩子变为兄弟！
3.二叉树转换成森林:
- 抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树
- 还原：将孤立的二叉树还原成树
哈夫曼树
1.哈夫曼树的相关术语：
- 路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径
- 路径长度：路径上的分支数目
- 带权路径长度：结点到根的路径长度与结点上权的乘积
- 树的带权路径长度：树中所有叶子结点的带权路径长度之和
2.哈夫曼树的性质
- 一般所说的哈夫曼树只有度为0和2的节点度为m的哈夫曼树
- 只有度数为有0和m的节点的哈夫曼树不一定是完全二叉树
3.哈夫曼树的构造过程：
- 操作要点：对权值的合并、删除与替换，总是合并当前值最小的两个
小结
