树的有关定和算法.doc

《树的有关定和算法.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、目录二叉树2二叉排序树3几种特殊的二叉排序树41、平衡二叉树42、红黑树73、伸展树10划分树12树13字典树13后缀树15最小生成树算法231、Prim算法232、Kruskal算法24次小生成树24最小k度限制生成树25线段树的入门26树状数组30有关树的定理及算法的串讲二叉树二叉树:是有限个数据元素的集合，该集合或者为空，或者由一个称为根的元素及两个不相交的、被称为根的左子树和根的右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称为一个节点。完全二叉树：若设二叉树的高度为h，除第h层外，其它各层(1～h-1)的节点数都达到最大个数，第h层有叶

2、子节点，并且叶子节点都是从左到右依次排布，这就是完全二叉树。满二叉树：如果一棵二叉树每一层的节点的个数都达到了最大，则这棵二叉树称作满二叉树二叉树的主要性质：(1)在二叉树中，第i层的节点总数不超过2^(i-1)；(2)深度为h的二叉树最多有2^h-1个节点(h>=1)，最少有h个节点；(3)对于任意一棵二叉树，如果其叶节点数为N0，而度数为2的节点总数为N2，则N0=N2+1；(4)具有n个节点的完全二叉树的深度为（log2n）+1二叉树的二叉链式存储结构可描述为：Typedefstructtree{intdata;//存放数据。structtree*lchild,*rchi

3、ld;}node;顺序存储结构呢？二叉树三种遍历方式：　(1)前序遍历访问根；按前序遍历左子树；按前序遍历右子树　　(2)中序遍历　　按中序遍历左子树；访问根；按中序遍历右子树　　(3)后序遍历按后序遍历左子树；按后序遍历右子树；访问根先序遍历得到的结果序列为：ABDECF。中序遍历得到的结果序列为：DBEAFC。后序遍历得到的结果序列为：DEBFCA。二叉排序树1,二叉排序树（BinarySortTree）又称二叉查找树。2,它或者是一棵空树；或者是具有下列性质的二叉树：(1)若左子树不空，则左子树上所有节点的值均小于它的根节点的值；(2)若右子树不空，则右子树上所有节点的值

4、均大于它的根节点的值；(3)左、右子树也分别为二叉排序树；二叉排序树的操作有：查找、查找最大关键元素和最小关键元素、插入、删除。二叉排序树的基本操作的时间与树的高度成正比。对于一棵含有n个节点的完全二叉树，这些操作的最坏运行时间为0（lgn）。优点:查找某个元素的时间复杂度可以达到0（lgn）。几种特殊的二叉排序树1、平衡二叉树平衡二叉树也是一种二叉排序树，又称AVL树。 　一棵空树是平衡二叉树；若T是一棵非空二叉树，其左、右子树为TL和TR，令hl和hr分别为左、右子树的深度。当且仅当　　　①TL、TR都是平衡二叉树； 　　　②｜hl－hr｜≤1；时，则T是平衡二叉树。【例】

5、如图8.4所示。                 （a）平衡二叉树      （b）非平衡二叉树          图8.3平衡二叉树与非平二叉树相应地定义hl－hr为二叉平衡树的平衡因子(balancefactor)。因此，平衡二叉树上所有节点的平衡因子可能是-1，0，1。换言之，若一棵二叉树上任一节点的平衡因子的绝对值都不大于1，则该树是就平衡二叉树。数据结构如下：typedefstructavlnode{datatypedata;//数据元素intbf;//平衡因子structavlnode*lchild,*rchild;//左右孩子指针、}AVLnode;平衡二叉树的优

6、点：二叉查找树的基本操作的时间是由高度来决定的，而平衡二叉树是使其树的高度保持在较低情况，使基本的操作执行得较快。平衡二叉树在进行插入操作的时候可能出现不平衡的情况，AVL树即是一种自平衡的二叉树，它通过旋转不平衡的节点来使二叉树重新保持平衡，并且查找、插入和删除操作在平均和最坏情况下时间复杂度都是O(logn)  AVL树的旋转一共有四种情形，注意所有旋转情况都是围绕着使得二叉树不平衡的第一个节点展开的。1.LL型   平衡二叉树某一节点的左孩子的左子树上插入一个新的节点，使得该节点不再平衡。这时只需要把树向右旋转一次即可，如图所示，原A的左孩子B变为父节点，A变为其右孩子，

7、而原B的右子树变为A的左子树，注意旋转之后Brh是A的左子树。  2.RR型  平衡二叉树某一节点的右孩子的右子树上插入一个新的节点，使得该节点不再平衡。这时只需要把树向左旋转一次即可，如图所示，原A右孩子B变为父节点，A变为其左孩子，而原B的左子树Blh将变为A的右子树。  3.LR型  平衡二叉树某一节点的左孩子的右子树上插入一个新的节点，使得该节点不再平衡。这时需要旋转两次，仅一次的旋转是不能够使二叉树再次平衡。如图所示，在B节点按照RR型向左旋转一次之后，二叉树在A节点仍然不能保持平