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