树与二叉树
树的概念
一些术语:
- 结点深度：从根节点开始算
- 结点高度：从叶节点往上算
- 有序树和无序树：节点子树是否有序来区分
一些性质：
- 树的结点数等于所有节点度数+1
- 高度为h的m叉树最多有$\frac{m^h-1}{m-1}$结点
- 高度为h，度为m的树至少有$h+m-1$结点
- 具有n个结点的m叉树最小高度：$log_m(n(m-1)+1)$
二叉树
二叉树主要特征
特殊二叉树
- 满二叉树：高度为h，含有$2^h-1$个结点。按照根节点为一的规律编号，若编号结点为i，双亲为$\lfloor i/2\rfloor$，则左孩子为2i，右孩子为2i+1。
- 完全二叉树：高度为h，结点数量n。每个结点编号都和相应满二叉树的编号一一对应。特点如下：
- 若$i \leq \lfloor \frac{n}{2} \rfloor$，则i为分支节点，否则，为叶子结点。
- 若n为偶数，则有一个节点只有左孩子，若为奇数，都有左右孩子。
- 二叉排序树：左子树关键字都小于根节点关键字，根节点关键字都大于根节点关键字。
- 平衡二叉树：树上任一结点左子树和右子树深度之差不超过1。
二叉树性质
- 非空二叉树叶子节点数量等于度为2的数量加一：$n_0=n_2+1$
- 具有n个结点的完全二叉树高度：$\lceil log_2(n+1)\rceil$或$\lfloor log_2n \rfloor+1$
二叉树存储结构
顺序结构：一般只适用于满二叉树和完全二叉树（最好使用1下标，否则部分性质无法满足。）
链式结构：含有n个结点的二叉链表中，有n+1个空链域
二叉树的遍历
三种遍历的时间复杂度都是O（n）
二叉树的先（后）序遍历和中序遍历可以确定一棵二叉树
层次遍历和中（后）序遍历可以确定一颗二叉树。
树与森林
树的存储结构
双亲表示法
采用连续空间存储每个节点，并且在每个节点增设伪指针，指示双亲结点在数组中的位置。
优点：利用每个节点都只有一个双亲的性质
缺点：但求每个结点孩子都要遍历整个结构
孩子表示法
将每个节点的孩子节点都有单链表接起来形成线性结构，n个节点有n个孩子链表
优点：寻找子女方便
缺点：寻找双亲需要遍历n个结点中孩子链表
孩子兄弟表示法
左孩子右兄弟
优点：灵活、易于找孩子结点
缺点：从当前结点找双亲比较麻烦
树和森林的遍历
先根遍历
先访问根结点，再访问相应结点的每颗子树。
顺序和对应二叉树先序遍历相同
后根遍历
先遍历结点的每颗子树，再访问根节点
顺序和相应二叉树中序遍历一样
森林操作和树类似
树的应用
并查集
- Union(S,Root1Root2):把集合S中的子集合Root2并入子集合Root1。要求Root1和Root2互不相交否则不执行合并
- Find(Sx)查找集合S中单元素κ所在的子集合并返回该子集合的名字
- Initial(S):将集合S中的每个元素都初始化为只有一个单元素的子集合
用树(森林)的双亲表示作为并查集的存储结构,每个子集合以一棵树表示 所有表示子集合的树构成表示全集合的森林存放在双亲表示数组内 通常用数组元素的下标代表元素名用根结点的下标代表子集合名,根结点的双亲结点为负数
二叉排序树
定义：
- 左子树都是小于根节点的值
- 右子树都是大于根节点的值
- 每个子树也都是一颗二叉排序树
进行中序遍历会得到一个排序后的树。
二叉树的查找是一个分支逐层往下比较的过程，如果小于查找的关键字，则查找左子树，反之查找右子树。
二叉树的插入是在查找失败在访问路径最后一个结点的左或右子树建立一个结点。
二叉树的删除有几种情况：
- 删除结点是叶子节点，直接删除
- 删除节点只有左或右子树，则让子树代替原有节点位置
- 删除结点左右都有子树，使用直接前驱或后继顶替删除结点，剩下的结点就转变为前两种情况
二叉查找树的查找效率和具体结构有关： 如果是一棵平衡二叉树是平衡二叉树，平均查找长度$O(log_2n)$，如果只有左/右子树，则为O（n）
平衡二叉树
平衡因子：左子树高度-右子树高度 构建n层平衡二叉树至少需要： n0=0，n1=1，n2=2，nh=1+n（h-1）+n（h-2）
易错点
- 后序遍历可以获得子孙到祖先的路径
- 如果前序后序完全相反,则说明一个节点不能同时有左右子树.
- 线索二叉树是存储结构
- 前序序列和中序序列关系相当于以前序序列入栈,中序序列出栈, 确定一颗二叉树
- 所有非叶结点平衡因子都是1的平衡二叉树，就是满足最小结点的平衡二叉树
- 哈夫曼树没有度为1的结点，也不一定是完全二叉树
- 没有一个编码是另外一个编码的前缀，则称为前缀码 8.AVL删除一个结点又重新加入，最后的树有可能相同也有可能不同