特殊二叉树09课件

第六章特殊二叉树新疆师范大学第六章特殊二叉树新疆师范大学16.1二叉排序树定义：二叉排序树或是一棵空树，或是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值它的左、右子树也分别为二叉排序树6.1二叉排序树2二叉排序树的抽象数据类型操作：Find（查找）Update（更新）Insert（插入）Delete（删除）二叉排序树的抽象数据类型操作：3查找Find递归算法和非递归算法两种1、该递归算法为末尾递归，浪费系统空间资源时间复杂度：O(lbn)------假设该树为理想平衡树空间复杂度：O(lbn)2、该非递归算法时间复杂度：O(lbn))------假设该树为理想平衡树空间复杂度：O(1)查找Find递归算法和非递归算法两种4更新Update与查找Find的区别：1、Update：将item的值赋值给该元素。Find：将该元素的值赋值给item带回。2、Update：参数可是值参或者引用参数（变参）。Find：参数只能是变参。更新Update与查找Find的区别：5例{10，18，3，8，12，2，7，3}10181018310183810183812101838122101838122710183812273中序遍历二叉排序树可得到一个关键字的有序序列插入10若二叉树为空，则item作为根插入。例{10，18，3，8，12，2，7，3}6插入Insert递归算法和非递归算法：1、该递归算法也是末尾递归时间（空间）复杂度=查找算法2、该非递归算法时间（空间）复杂度=查找算法插入Insert递归算法和非递归算法：7建立一棵二叉排序树createBSTree该算法的时间复杂度是？O(n×lbn)建立一棵二叉排序树createBSTreeO(n×lbn)8二叉排序树的删除要删除二叉排序树中的p结点，分三种情况：p为叶子结点只需修改p双亲f的指针f->left=NULL或f->right=NULLp只有左子树或右子树（单分支）p只有左子树，用p的左孩子代替pp只有右子树，用p的右孩子代替pp既有左子树又有右子树（双分支）删除二叉排序树的删除删除9删除双分支结点方法一：1、把待删除结点的右孩子链接到中序前驱结点的右边；2、把待删除结点的左孩子连接到它所在的链接位置。该方法的缺点：容易增加树的深度，使树的结构变坏。双分支结点的中序前驱结点的右孩子一定为空，左孩子可空可不空。删除双分支结点方法一：双分支结点的中序前驱结点的右孩子一定为10删除双分支结点方法二：1、把待删除结点的中序前驱结点的值赋值给该结点；2、删除中序前驱结点(中序前驱只可能是叶子结点或只有左子树的单分支结点)删除双分支结点方法二：11二叉排序树小结二叉排序树的查找，插入，删除运算的时间复杂度相同，都与二叉排序树的深度成正比。时间复杂度平均O(lbn)，最坏情况O(n)。它们的空间复杂度：递归算法平均O(lbn)，最坏情况O(n)，非递归算法都是O(1).二叉排序树小结二叉排序树的查找，插入，删除126.2堆分为大顶堆和小顶堆小顶堆定义：具有如下特性的完全二叉树：1、若树根结点有左孩子，则根的值小于等于左孩子的值；2、若树根结点有右孩子，则根的值小于等于右孩子的值；3、以左右孩子为根的树又各是一个小顶堆。6.2堆分为大顶堆和小顶堆13堆的抽象数据类型操作：insertHeap插入deleteHeap删除堆的抽象数据类型操作：14堆的存储结构堆是一个完全二叉树，那么适于采用哪种存储结构呢？顺序存储结构堆的存储结构堆是一个完全二叉树，那么适于采用哪种存储结构呢？15插入1、将元素写入堆尾2、调整为新的堆：调整是自下而上的，直到以新元素的双亲为根的子树是堆为止；或者一直调整到堆顶为止。插入1、将元素写入堆尾16删除（删除堆顶元素）1、把堆尾元素移动到堆顶2、调整这棵树使其称为堆：调整是自上而下的，直到这棵树是堆为止；或者一直调整到叶子结点为止。

删除（删除堆顶元素）1、把堆尾元素移动到堆顶17堆小结堆的删除算法和插入算法的时间复杂度为O(lbn)堆结构的使用范围：当每次需删除或取出的是最大或最小元素。堆小结堆的删除算法和插入算法的时间复杂度为18哈夫曼树基本术语：路径：结点序列k1，k2，…..kj是k1到kj的路径。路径长度：从k1到kj的路径中的分支数。也是结点数减1.结点的权：结点上赋予的有意义的值。结点的带权路径长度：从树根到某结点的路径长度×结点的权。树的带权路径长度：树中所有叶子结点的带权路径长度之和。哈夫曼树基本术语：19哈夫曼树哈夫曼树：又称最优二叉树，指n个带权叶子结点构成的二叉树中WPL最小的二叉树。完全二叉树或满二叉树不一定是最优二叉树，权值越大的结点但离树根越近的二叉树才是最优二叉树。哈夫曼树哈夫曼树：完全二叉树或满二叉树不一定是最优二叉树，20构造哈夫曼树关键：权值越大的叶子结点应该离根越近构造方法：已知:有n个叶子结点，权值为W=｛w1,w2,….wn｝1、找出权值最小的两个结点作为左、右孩子构成一棵二叉树，该二叉树的根结点的权是两个叶子结点权值之和。2、从W中删除这两个结点，并将该二叉树的根结点的权加入W中。3、重复1和2，直到W中只有一个元素为止。构造哈夫曼树关键：权值越大的叶子结点应该离根越近21构造哈夫曼树的算法存储结构CreateHuffman和WeightPathLength二叉链表构造哈夫曼树的算法存储结构二叉链表22哈夫曼编码是哈夫曼树的一种应用举例：采用二进制数对字符A,B,C,D,E,F进行编码。方案一：等长编码WPL=75方案二：哈夫曼编码WPL=61哈夫曼编码是哈夫曼树的一种应用23线索二叉树一、概念1、中序前驱、中序后继2、线索、前驱（左）线索、后继（右）线索3、线索二叉树二、结点类型定义StructTTreeNode{ElemTypedata;Boolltag,rtag;TTreeNode*left,*right;}线索二叉树一、概念24平衡二叉树一、概念1、平衡二叉树：有别于理想平衡树2、平衡因子：平衡树中平衡因子{-1，0，1}3、最小不平衡子树平衡二叉树一、概念25作业247-6-1（1，2，3，4，5）上机作业：247-6-2（2，3）作业247-6-1（1，2，3，4，5）26第六章特殊二叉树新疆师范大学第六章特殊二叉树新疆师范大学276.1二叉排序树定义：二叉排序树或是一棵空树，或是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值它的左、右子树也分别为二叉排序树6.1二叉排序树28二叉排序树的抽象数据类型操作：Find（查找）Update（更新）Insert（插入）Delete（删除）二叉排序树的抽象数据类型操作：29查找Find递归算法和非递归算法两种1、该递归算法为末尾递归，浪费系统空间资源时间复杂度：O(lbn)------假设该树为理想平衡树空间复杂度：O(lbn)2、该非递归算法时间复杂度：O(lbn))------假设该树为理想平衡树空间复杂度：O(1)查找Find递归算法和非递归算法两种30更新Update与查找Find的区别：1、Update：将item的值赋值给该元素。Find：将该元素的值赋值给item带回。2、Update：参数可是值参或者引用参数（变参）。Find：参数只能是变参。更新Update与查找Find的区别：31例{10，18，3，8，12，2，7，3}10181018310183810183812101838122101838122710183812273中序遍历二叉排序树可得到一个关键字的有序序列插入10若二叉树为空，则item作为根插入。例{10，18，3，8，12，2，7，3}32插入Insert递归算法和非递归算法：1、该递归算法也是末尾递归时间（空间）复杂度=查找算法2、该非递归算法时间（空间）复杂度=查找算法插入Insert递归算法和非递归算法：33建立一棵二叉排序树createBSTree该算法的时间复杂度是？O(n×lbn)建立一棵二叉排序树createBSTreeO(n×lbn)34二叉排序树的删除要删除二叉排序树中的p结点，分三种情况：p为叶子结点只需修改p双亲f的指针f->left=NULL或f->right=NULLp只有左子树或右子树（单分支）p只有左子树，用p的左孩子代替pp只有右子树，用p的右孩子代替pp既有左子树又有右子树（双分支）删除二叉排序树的删除删除35删除双分支结点方法一：1、把待删除结点的右孩子链接到中序前驱结点的右边；2、把待删除结点的左孩子连接到它所在的链接位置。该方法的缺点：容易增加树的深度，使树的结构变坏。双分支结点的中序前驱结点的右孩子一定为空，左孩子可空可不空。删除双分支结点方法一：双分支结点的中序前驱结点的右孩子一定为36删除双分支结点方法二：1、把待删除结点的中序前驱结点的值赋值给该结点；2、删除中序前驱结点(中序前驱只可能是叶子结点或只有左子树的单分支结点)删除双分支结点方法二：37二叉排序树小结二叉排序树的查找，插入，删除运算的时间复杂度相同，都与二叉排序树的深度成正比。时间复杂度平均O(lbn)，最坏情况O(n)。它们的空间复杂度：递归算法平均O(lbn)，最坏情况O(n)，非递归算法都是O(1).二叉排序树小结二叉排序树的查找，插入，删除386.2堆分为大顶堆和小顶堆小顶堆定义：具有如下特性的完全二叉树：1、若树根结点有左孩子，则根的值小于等于左孩子的值；2、若树根结点有右孩子，则根的值小于等于右孩子的值；3、以左右孩子为根的树又各是一个小顶堆。6.2堆分为大顶堆和小顶堆39堆的抽象数据类型操作：insertHeap插入deleteHeap删除堆的抽象数据类型操作：40堆的存储结构堆是一个完全二叉树，那么适于采用哪种存储结构呢？顺序存储结构堆的存储结构堆是一个完全二叉树，那么适于采用哪种存储结构呢？41插入1、将元素写入堆尾2、调整为新的堆：调整是自下而上的，直到以新元素的双亲为根的子树是堆为止；或者一直调整到堆顶为止。插入1、将元素写入堆尾42删除（删除堆顶元素）1、把堆尾元素移动到堆顶2、调整这棵树使其称为堆：调整是自上而下的，直到这棵树是堆为止；或者一直调整到叶子结点为止。

删除（删除堆顶元素）1、把堆尾元素移动到堆顶43堆小结堆的删除算法和插入算法的时间复杂度为O(lbn)堆结构的使用范围：当每次需删除或取出的是最大或最小元素。堆小结堆的删除算法和插入算法的时间复杂度为44哈夫曼树基本术语：路径：结点序列k1，k2，…..kj是k1到kj的路径。路径长度：从k1到kj的路径中的分支数。也是结点数减1.结点的权：结点上赋予的有意义的值。结点的带权路径长度：从树根到某结点的路径长度×结点的权。树的带权路径长度：树中所有叶子结点的带权路径长度之和。哈夫曼树基本术语：45哈夫曼树哈夫曼树：又称最优二叉树，指n个带权叶子结点构成的二叉树中WPL最小的二叉树。完全二叉树或满二叉树不一定是最优二叉树，权值越大的结点但离树根越近的二叉树才是最优二叉树。哈夫曼树哈夫曼树：完全二叉树或满二叉树不一定是最优二叉树，46构造哈夫曼树关键：权值越大的叶子结点应该离根越近构造方法：