July_algorithm 4.树.pdf

《July_algorithm 4.树.pdf》由会员分享，可在线阅读，更多相关《July_algorithm 4.树.pdf（77页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、树七月算法邹博2015年10月25日10月算法在线班2/77树主要内容二叉查找树增删改查其他结构的基础：如平衡二叉树前序中序后序遍历三种遍历本身通过前序中序求后序平衡二叉树四种分类：左左、左右、右左、右右四种旋转：左旋和右旋；单旋转和双旋转增删改查B树及其变种分裂结点、合并结点R树实践中的应用10月算法在线班3/77树和二叉树 一般地说，树的结点间是无序的，即：一个结点有m个孩子，则L1L2Lm可以互换位置，仍然认为是一颗树。二叉树的两个孩子，一般称为左孩子、右孩子，不能互换位置。之所以这样定义，是因为有些算法，需要严格区分左右孩子，如前序-中序-后序遍历、堆排序等问题。从这个意义上说，树和二

2、叉树是两个概念，不能说二叉树是树的子集。注：这种区分非常弱而且乱，因为树还有“有序树”“无序树”的说法。10月算法在线班4/77树转换成二叉树10月算法在线班5/77树转换得到的二叉树右孩子 任意一颗树转换成二叉树，右孩子为空的数目为原树非叶结点+1。对于一颗树(非二叉树)，因为任何一个非叶结点必然有孩子，所以，它必然有最右孩子。从而，这个最右孩子转换到二叉树结点后，右指针必然为空。同时，根结点必然没有兄弟，所以，根结点转换成二叉树结点后，必然右孩子为空。任意颗树转换成二叉树，右孩子为空的数目为原树非叶结点+1。如果是若干个树转二叉树，这若干个树最右边的那个树，是没有右孩子的。10月算法在线班

3、6/77树基本操作 插入 删除 查找 前序遍历 中序遍历 后序遍历10月算法在线班7/77二叉查找树 二叉查找树(二叉搜索树)是满足以下条件的二叉树：左子树上的所有结点值均小于根结点值，右子树上的所有结点值均不小于根结点值，左右子树也满足上述两个条件10月算法在线班8/77二叉查找树的查找 给定一颗二叉查找树，查找某结点p的过程如下：将当前结点cur赋值为根结点root；若p的值小于当前结点cur的值，查找cur的左子树；若p的值不小于当前结点cur的值，查找cur的右子树；递归上述过程，直到cur的值等于p的值或者cur为空；当然，若结点是结构体，注意定义“小于”“不小于”“等于”的具体函数

4、。10月算法在线班9/77Code10月算法在线班10/77二叉查找树的插入 插入过程如下：若当前的二叉查找树为空，则插入的元素为根结点，若插入的元素值小于根结点值，则将元素插入到左子树中，若插入的元素值不小于根结点值，则将元素插入到右子树中，递归上述过程，直到找到插入点为叶子结点。10月算法在线班11/77Code(recursion)10月算法在线班12/77Code10月算法在线班13/77二叉树的建立 依次插入：15,5,3,12,16,20,23,13,18,10,6,710月算法在线班14/77二叉查找树的删除 记待删除的结点为p，分三种情况进行处理：p为叶子结点 p为单支结点 p

5、的左子树和右子树均不空10月算法在线班15/77待删除点为叶子结点 p为叶子结点，直接删除该结点，再修改p的父结点的指针10月算法在线班16/77待删除点只有一个孩子 若p为单支结点(即只有左子树或右子树)，则将p的子树与p的父亲结点相连，删除p即可10月算法在线班17/77待删除点有两个孩子 若p的左子树和右子树均不空，则找到p的直接后继d(p的右孩子的最左子孙)，因为d一定没有左子树，所以使用删除单支结点的方法：删除d，并让d的父亲结点dp成为d的右子树的父亲结点；同时，用d的值代替p的值；对偶的，可以找到p的直接前驱x(p的左孩子的最右子孙)，x一定没有右子树，所以可以删除x，并让x的父

6、亲结点成为x的左子树的父亲结点。10月算法在线班18/77待删除点有两个孩子 任务：删除p 过程：两步走 将p的直接后继的值拷贝到p处 删除p的直接后继10月算法在线班19/77Code10月算法在线班20/77Code10月算法在线班21/77Code split10月算法在线班22/77二叉树的遍历 前序遍历：访问根结点前序遍历左子树前序遍历右子树 中序遍历：中序遍历左子树访问根结点中序遍历右子树 后序遍历：后序遍历左子树后序遍历右子树访问根结点10月算法在线班23/77前序遍历 前序遍历：15,5,3,12,10,6,7,13,16,20,18,2310月算法在线班24/77Code10

7、月算法在线班25/77中序遍历 中序遍历：3,5,6,7,10,12,13,15,16,18,20,23二叉查找树的中序遍历，即为数据的升序过程10月算法在线班26/77Code10月算法在线班27/77Code10月算法在线班28/77后序遍历 后序遍历：3,7,6,10,13,12,5,18,23,20,16,1510月算法在线班29/77Code10月算法在线班30/77Code10月算法在线班31/77根据前序中序，计算后序 如：已知某二叉树的遍历结果如下，求它的后序遍历序列 前序遍历：GDAFEMHZ 中序遍历：ADEFGHMZ 两个步骤：根据前序中序，构造二叉树 后序遍历二叉树10

8、月算法在线班32/77根据前序中序，计算后序 前序遍历：GDAFEMHZ 中序遍历：ADEFGHMZ 根据前序遍历的特点得知，根结点为G；根结点将中序遍历结果ADEFGHMZ分成ADEF和HMZ两个左子树、右子树。递归确定中序遍历序列ADEF和前序遍历序列DAEF的子树结构；递归确定中序遍历序列HMZ和前序遍历序列MHZ的子树结构；10月算法在线班33/77根据前序中序，构造二叉树 前序遍历：GDAFEMHZ 中序遍历：ADEFGHMZ10月算法在线班34/77Code10月算法在线班35/77思考 若已知二叉树的中序和后序遍历序列，如何求二叉树、如何求二叉树的前序遍历序列呢？10月算法在线班

9、36/77根据中序后序遍历，求前序遍历 中序遍历：ADEFGHMZ 后序遍历：AEFDHZMG 提示：后序遍历最后一个结点即为根结点，即根结点为G 递归10月算法在线班37/77Code10月算法在线班38/77思考 给定整数数组，判断该数组有无可能是一颗二叉查找树后序遍历的结果。假定数组中没有重复元素。编程如何实现？以下序列中不可能是一棵二叉查找树的后序遍历结果的是_。1,2,3,4,53,5,1,4,21,2,5,4,35,4,3,2,110月算法在线班39/77算法描述 1,2,5,4,3 由于后序遍历的最后一个元素为根结点，根据该结点，将数组分成前后两段，使得前半段都小于根结点，后半段

10、都大于根结点；如果不存在这样的划分，则不可能是后序遍历的结果。递归判断前后半段是否满足同样的要求。10月算法在线班40/77Code10月算法在线班41/77平衡二叉树 平衡二叉树是第一个引入平衡概念的二叉树 Balanced Binary Tree，1962年由G.M.AdelsonVelsky、E.M.Landis发明，又称AVL树。每个结点的左右子树的高度之差不超过1，如果插入或者删除结点后高差大于1，则进行结点旋转，重新维护平衡状态。解决了二叉查找树退化成链表的问题，插入、查找、删除的时间复杂度最坏情况是O(logN)。最好情况也是O(logN)10月算法在线班42/77AVL实现举例

11、10月算法在线班43/77二叉查找树与平衡二叉树10月算法在线班44/77分析高度不平衡结点 维护不平衡的直接手段是选择不平衡结点X的某孩子C作为父结点，当前结点X作为原子结点C的子结点。这显然会影响到X的子结点、孙结点，因此，分成如下四种情况：高度不平衡结点的两颗子树的高度差210月算法在线班45/77高度不平衡1：左左 6结点的左子树3结点高度比右子树7结点大2，左子树3结点的左子树1结点高度大于右子树4结点，这种情况称为左左。10月算法在线班46/77高度不平衡2：左右 6结点的左子树2结点高度比右子树7结点大2，左子树2结点的左子树1结点高度小于右子树4结点，这种情况成为左右。10月算

12、法在线班47/77高度不平衡3：右左 2结点的左子树1结点高度比右子树5结点小2，右子树5结点的左子树3结点高度大于右子树6结点，这种情况成为右左。10月算法在线班48/77高度不平衡4：右右 2结点的左子树1结点高度比右子树4结点小2，右子树4结点的左子树3结点高度小于右子树6结点，这种情况成为右右。10月算法在线班49/77对称与旋转 左左和右右对称；左右和右左对称 左左和右右两种情况是对称的，这两种情况的旋转算法是一致的，只需要经过一次旋转就可以达到目标，称之为单旋转。左右和右左两种情况也是对称的，这两种情况的旋转算法也是一致的，需要进行两次旋转，称之为双旋转。10月算法在线班50/77

13、左左单旋转 结点K2不满足平衡特性，因为它的左子树k1比右子树Z深2层，而且K1子树中，更深的一层的是K1的左子树X子树，所以属于左左情况。10月算法在线班51/77单旋转：对左孩子做旋转(顺时针)假设K2不平衡：中序遍历X-K1-Y-K2-Z 把K1作为新的根结点 K2K1，所以，把K2置于K1的右子树上 K2YK1，所以，把Y置于K2的左子树上10月算法在线班52/77AVL单旋转 把K1变成根结点 把K2置于K1的右子树 把Y置于K2的左子树10月算法在线班53/77双旋转 对于左右和右左两种情况，单旋转不能使它达到一个平衡状态，要经过两次旋转。左右：结点K3不平衡，左子树K1比右子树D

14、深2层，且K1的子树中更深的是右子树K2。K1右旋，然后K3左旋10月算法在线班54/77Code10月算法在线班55/77平衡二叉树的插入 插入的方法和二叉查找树基本一样，区别是，插入完成后需要从插入的结点开始维护一个到根结点的路径，每经过一个结点都要维持树的平衡。维持树的平衡要根据高度差的特点选择不同的旋转算法。10月算法在线班56/77Code10月算法在线班57/77平衡二叉树的查找 平衡二叉树使用和二叉查找树完全相同的查找方法，不过根据高度基本平衡存储的特性，平衡二叉树能保持O(logN)的稳定时间复杂度，而二叉查找树极端情况会退化成链表。10月算法在线班58/77平衡二叉树的删除

15、删除的方法也和二叉查找树的一致，区别是，删除完成后，需要从删除结点的父亲开始向上维护树的平衡一直到根结点。10月算法在线班59/77Code10月算法在线班60/77Code part110月算法在线班61/77Code part210月算法在线班62/77二叉到多叉的思考 一个结点存一个值，则有2个孩子：W 一个结点存两个值，则有3个孩子：MO 一个结点存三个值，则有4个孩子：MO10月算法在线班63/772-3-4树10月算法在线班64/77查找L10月算法在线班65/77插入B10月算法在线班66/77插入X10月算法在线班67/77插入H10月算法在线班68/77分裂结点10月算法在线

16、班69/77B树的定义 m阶B树需要满足的条件：每个结点至多有m个孩子；除根结点外，其他结点至少有m/2个孩子；根结点至少有2个孩子；所有叶结点在同一层；有个孩子的非叶结点有-1个关键字；结点内部，关键字递增排列。10月算法在线班70/77B树10月算法在线班71/77B树10月算法在线班72/77B树的变种10月算法在线班73/77二维上的B树R树10月算法在线班74/77三维空间中的R树10月算法在线班75/77总结 树是最重要的数据结构，没有之一。从根节点到叶子的过程，是逐渐细化精确的过程，所以，实践中往往作为海量数据索引。树只是数据结构，非存储结构。实践中，可以使用数组来存储树。思考实例Huffman编码、堆排序、并查集等。10月算法在线班76/77我们在这里http:/ 七月题库APP：Android/iOShttp:/ 微信公众号julyedu10月算法在线班77/77感谢大家恳请大家批评指正！