树的分类
1.树是N个顶点的有限集合。N=0时，称为空树，满足有且仅有一个特定的称为根的结点。 当N>1时，其余节点可分为m（M>0）个的互不相交的有限集合，其中每个集合本身又是一棵树。
树的广度优先和深度优先
两种算法都需要设置访问标记数组。
广度优先类似于二叉树的层次遍历算法，算法借助一个辅助队列来记忆正在访问的顶点的下一层顶点。
深度优先就是一个递归算法，先访问树中起始顶点，然后访问与它邻接的未被访问过的顶点，不断重复。
树主要有三种存储结构：
1.双亲表示法 2.孩子表示法 3孩子兄弟表示法
2.二叉树
每个节点至多有两个子树（二叉树中不存在度大于2的结点），二叉树有左右之分，不能相互颠倒。
1）满二叉树：一个高度为h，并且有2h-1个结点的二叉树称为满二叉树，即树中的每一层都含有最多的结点
2）完全二叉树 ：设一个高度是H，有N个结点的二叉树，当且仅当其每一个结点都与高度为H的满二叉树中编号为1~N的结点一一对应时，称为满二叉树
3）二叉排序树：一棵二叉树或者空二叉树，或者具有如下性质的二叉树：左子树上所有结点的关键字均小于根节点上的关键字，右子树上所有结点的关键字均大于根节点的关键字，左子树和右子树又各是一棵二叉排序树 。
4）平衡二叉树：树上任一结点的左子树和右子树的深度之差不超过1。
树，森林与二叉树的转化：
左孩子右兄弟
哈夫曼树：在含有N个带权叶子节点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树。
哈夫曼编码：如果没有一个码是其他编码的前缀。称为前缀编码。
排序
image.png
快排的实现过程：
基本思想基于分治法：找一个基准元素，通过一趟排序使得比基准元素小的都在左边，比基准元素大的都在右边。而后分别递归地对子表重复上述过程。直到每部分内都只有一个元素为止。
当初始表基本有序或逆序时最坏情况，O（N的平方）。 最好的是log2(n).
B-树（多路平衡查找树）
1.所有结点的孩子结点数最大值成为B树的阶。
1）树中每个节点至多有M棵子树（即至多含有M-1个关键字）
2）若根节点不是终端节点，则至少有两棵子树
3）除根节点以外的所有非叶节点至少有【M/2】（向上取整）棵子树
4）所有叶节点都出现在同一层
B+树
和B-树相比，
1.它的叶结点包含信息，所有非叶节点都只起了一个索引的租用。
2.叶节点中包含了所有关键字，而且链接成一个链表，可以从最小开始查找到最大。
3.具有N个关键字的结点含有N个子树。
4.所有分支节点（可以看成索引的索引）中仅包含它的各个子节点中的最大值及指向子节点的指针。
散列表
把关键字映射成关键字对应的地址的函数。 当把不同的关键字映射都同一个地址的时候，就称为冲突。
解决冲突的方法
1.开放定址法： H = (H(key)+d)%m
1）线性探测法 d为1，2，3…
2）平方探测法 d 为1的平方 负的（1的平方），2的平方，-（2的平方）
3）再散列法：又称双散列法 需要使用两个散列函数。当第一个冲突的时候，就使用第二个散列函数。4）伪随机数法。d是随机数。
2.拉链法：把所有同义词存储在一个线性链表中。
网友评论