第五章二叉树.ppt

《第五章二叉树.ppt》由会员分享，可在线阅读，更多相关《第五章二叉树.ppt（92页珍藏版）》请在三一文库上搜索。

1、第五章 二叉树 树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界国是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。等等。 5.1 树的定义和基本术语 定义：树(Tree)是n(n=0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件： （1）有且仅有一个特定的称为根(Root)的结点； (2)其余的结点可分为m(m=0)个互不相交的子集T1,T2

2、,T3Tm，其中每个子集又是一棵树，并称其为子树(Subtree)。 5.2 二叉树 二叉树在树结构的应用中起着非常重要的作用， 因为对二叉树的许多操作算法简单，而任何树都可以 与二叉树 相互转换，这样就解决了树的 存储结构及其运算中存在的复杂性。 5.2.1 二叉树的定义 定义：二叉树是由n(n=0)个结点的有限集合构成， 此集合或者为空集，或者由一个根结点及两棵互不相 交的左右子树组成，并且左右子树都是二叉树。 这也是一个递归定义。二叉树可以是空集合，根 可以有空的左子树或空的右子树。 二叉树的相关概念 （1）结点的度。结点所拥有的子树的个数称为该结点的度。 （2）叶结点。度为0的结点称为

3、叶结点，或者称为终端结点。 （3）分枝结点。度不为0的结点称为分支结点，或者称为非终端 结点。一棵树的结点除叶结点外，其余的都是分支结点。 （4）左孩子、右孩子、双亲。树中一个结点的子树的根结点称 为这个结点的孩子。这个结点称为它孩子结点的双亲。具有同一 个双亲的孩子结点互称为兄弟。 （5）路径、路径长度。如果一棵树的一串结点n1,n2,nk有如下 关系：结点ni是ni+1的父结点（1i=1)。 采用归纳法证明此性质。 当i=1时，只有一个根结点，2i-1=20 =1,命题成立。 现在假定多所有的j，1=1). 深度为k的二叉树的最大的结点时为二叉树中每层上 的最大结点数之和，由性质1得到每层

4、上的最大结点 数，： E k I=1（第i层上的最大结点数）= E k I=12 i- 1=2k 1 性质3： 对任何一棵二叉树，如果其终端结点数为 n0，度为2的结点数为n2，则n0n21。 设二叉树中度为1的结点数为n1，二叉树中总结点数 为N，因为二叉树中所有结点均小于或等于2，所以 有：Nn0n1n2 (5-1) 再看二叉树中的分支数，除根结点外，其余结点都 有一个进入分支，设B为二叉树中的分支总数， 则有：NB1。 由于这些分支都是由度为1和2的结点射出的，所有有 ： Bn1+2*n2 NB1n12n21 （52) 由式（51）和（52）得到： n0+n1+n2=n1+2*n2+1

5、n0n21 下面介绍两种特殊形态的二叉树：满二叉树和完全二 叉树。 一棵深度为k且由2k-1个结点的二叉树称为满二叉树 。图5.9就是一棵满二叉树，对结点进行了顺序编号 。 如果深度为k、由n个结点的二叉树中个结点能够 与深度为k的顺序编号的满二叉树从1到n标号的 结点相对应， 2 45 3 6 7 1 图5.9 满二叉树 1 23 4 56 1 2 3 4 5 7 1 2 3 6 7 (a)完全二叉树 (b)非完全二叉树 ( c)非完全二叉树 图5.10 完全二叉树 则称这样的二叉树为完全二叉树，图5.10（b）、 (c）是2棵非完全二叉树。满二叉树是完全二叉树的 特例。 完全二叉树的特点是

6、： （1)所有的叶结点都出现在第k层或k1层。 （2）对任一结点，如果其右子树的最大层次为1， 则其左子树的最大层次为1或l1。 性质4：具有n个结点的完全二叉树的深度为log2n 1。 符号 x 表示不大于x的最大整数。 假设此二叉树的深度为k，则根据性质2及完全二 叉树的定义得到：2k-111，则其双亲是结点 i/2 。 （2）如果2in，则结点i为叶子结点，无左孩子； 否则，其左孩子是结点2i。 （3）如果2i1n，则结点i无右孩子；否则，其右 孩子是结点2i1。 I/2 i I+1 2i2i+1 2(I+1)2i+3 I+1 2(I+1)2i+3 i 2i 2i+1 图5.11 完全二

7、叉树中结点I和i+1 (a)I和i+1结点在同一层 (b)I和i+1结点不在同一层 如图5.11所示为完全二叉树上结点及其 左右孩子结点之间的关系。 在此过程中，可以从（2）和（3）推出（1），所 以先证明（2）和（3）。 对于i1，由完全二叉树的定义，其左孩子是结 点2，若2n，即不存在结点2，此是，结点i无孩子。 结点i的由孩子也只能是结点3，若结点3不存在，即 3n，此时结点i无右孩子。 对于i1，可分为两种情况： （1）设第j（1n，则无左孩子： 其右孩子必定为第j1层的第二个结点，编号为2i1 。若2i+1n，则无右孩子。 （2）假设第j（11时，如果i为 左孩子，即2（i/2)=i

8、,则i/2是i的双亲；如果i为右 孩子，i2p+1,i的双亲应为p，p（i1） /2=i/2. 证毕。 二叉树的抽象数据类型 二叉树结点的ADT template class BinNode public: virtual Elem virtual void setVal(const Elem virtual BinNode* left()=0; virtual BinNode* right()=0; virtual void setLeft(BinNode*)=0; virtual void setLeft(BinNode*)=0 ; virtual bool isLeaf()=0; 5.2

9、.3 二叉树的存储结构 1.顺序存储结构 它是用一组连续的存储单元存储二叉树的数 据元素。因此，必须把二叉树的所有结点安排成 为一个恰当的序列，结点在这个序列中的相互位 置能反映出结点之间的逻辑关系，用编号的方法 ： #define max-tree-size 100 Typedef telemtype sqbitreemax-tree-size; Sqbitree bt 从树根起，自上层至下层，每层自左至右的 给所有结点编号缺点是有可能对存储空间造成极 大的浪费，在最坏的情况下，一个深度为H且只 有H个结点的右单支树确需要2h-1个结点存储空 间。而且，若经常需要插入与删除树中结点时， 顺序

10、存储方式不是很好！ A B C D EFG H IJK L 1 2 3 4 5 6 7 8 9 10 11 12 完全二叉树 a b c d ef g hijkl A B C D E F G 表示该处没有元素 存在仅仅为了好理解 ABCDEFG 一般二叉树 （2）二叉树的二叉动态链式存储表示 1、结点结构和示例 leftChild data rightChild A B CD EF root A B CD EF root 二叉树的二叉链表存储表示 template class BinaryTree; template class BinTreeNode firend class BinaryT

11、ree; private: Elem data; BinTreeNode * lchild; BinTreeNode * rchild; public: BinTreeNode()lchild=rchild=NULL; BinTreeNode(Elem e,BinNodePtr*l=NULL, BinNodePtr*r=NULL) data=e; lchild=l; rchild=r; BinTreeNode() 二叉树的二叉链表存储表示 Elem val()return data; void setVal(const Elem e)data=e; inline BinTreeNode* le

12、ft()return lchild; inline BinTreeNode* right()return rchild; void setLeft(BinTreeNode* left)lchild=left; void setRight(BinTreeNode* right)rchild=right; bool isLeaf() return (lchild=NULL) ; 有时也可用数组的下标来模拟指针,即开辟三个一维数组Data ,lchild,rchild 分别存储结点的元素及其左,右指针域; template class BinaryTree private: BinTreeNode

13、*root; Elem Refvalue; BinTreeNode *Parent (BinTreeNode *start, BinTreeNode *current); void Traverse (BinTreeNode *current, ostream public: Virtual BinaryTree (Elem value): root (NULL), Refvalue (value) Virtual BinaryTree( ) destroy (root); Virtual bool IsEmpty( ) return root = = NULL ? true :false;

14、Virtual BinTreeNode *Parent (BinTreeNode *current) return Parent (root, current); 3、部分成员函数的实现 template void BinaryTree : destroy (BinTreeNode *current) /删除以current为根的子树 if (current != NULL) destroy (current - leftChild); /删除current的左子树 destroy (current - rightChild); /删除current的右子树 delete current; /

15、删除current 算法中，、两递归调用语句可互换，它只关系到左 右子树中，哪一个先删，哪一个后删。 语句不能同和语句互换，因为那样将导致一个子 树甚至两个子树无法删。 template BinTreeNode *BinaryTree : Parent (BinTreeNode *start, BinTreeNode *current) if (start = = NULL | | current = = start) return NULL; if (start - leftChild = = current | | start - rightChild = = current) retur

16、n start; /start是双亲 BinTreeNode *p; if (p = Parent (start - leftChild, current) != NULL) return p; /在左子树找 else return Parent (start - rightChild, current); /在右子树找 template void Binary Tree : Traverse (BinTreeNode *current, ostream /搜索并输出左子树 Traverse (current - rightChild, out); /搜索并输出右子树 5.3 遍历二叉树（Tr

17、aversal Binary Tree） 一、TBT概述 1、定义 按某种次序，访问所有结点，使每个节点都被访问且 尽访问一次的运算叫TBT。 “访问”包括输出结点值，修改值，统计等以不破坏BT 的结构为原则。 TBT是对二叉树进行运算的基础性操作。 一、TBT概述 2、次序（V根，L左子树，R右子树） 先序遍历 中序遍历 后序遍历 先右后左：VRLRVLRLV 先左后右：VLRLVRLRV bt A BC D EF GH IJ VLR输出序列：A B D E G HI J C F LVR输出序列：D B G EI H J A C F LRV输出序列：D G I JH E B F C A 二、

18、TBT的递归算法 1、中序遍历（ inorder traversal） template void BinaryTree : InOrder ( ) InOrder (root); /公共函数，调用私有函数完成遍历 template void BinaryTree : InOrder (BinTreeNode *current) if (current != NULL) /当current = = NULL，则递归终结 InOrder (current - leftChild); /中序遍历左子树 cout data; /访问根结点 InOrder (current - rightChild)

19、; /中序遍历右子树 / a b cd ef 对 a+b*(c-d)-e/f 表达式的语 法树，中序遍历得到其中缀表 示： a + b * c d e / f 2、先序遍历（ preorder Traversal） template void BinaryTree : PreOrder (BinTreeNode *current) /私有函数 if (current != NULL) cout data; PreOrder (current - leftChild); PreOrder (current - rightChild); / a b cd ef 对表达式a+b*(c-d)-e/f

20、的语 法树进行先序遍历得到其前缀 表示： + a * b c d / e f 二、TBT的递归算法 3、后序遍历（ postorder traversal） template void BinaryTree : PostOrder (BinTreeNode *current) /私有函数 if (current != NULL) PostOrder (current - leftChild); PostOrder (current - rightChild); cout data; 二、TBT的递归算法 / a b cd ef 对表达式 a+b*(c-d)-e/f 的语 法树进行后序遍历得到其

21、后缀 表示： a b c d * + e f / 三、TBT的非递归算法 1、递归算法中栈的使用 TBT递归算法的简化 traversal (BinTreeNode *current) if (current != NULL) traversal (current - leftChild); traversal (current - rightChild); 三、TBT的非递归算法 1、递归算法中栈的使用 执行过程中栈的情况和current的变化举例 当左向递归则current的值进栈 若current = = NULL，则出栈，current以栈顶值去执行右向递归 直到栈空（top = -1

22、）和current = = NULL为止 current top ad1ad2ad3ad4ad5 stack A B C D E ad1 ad2 ad3 ad4 ad5 -1 0 1 2 3 2、利用栈的前序和中序遍历非递归算法 template void BinaryTree : PreOrder ( ) stack * st; BinTreeNode *p = root; do while (p != NULL) cout data; st. Push (p); p = p -leftChild; if ( St. length()!=0) st. pop (p ); p = p - ri

23、ghtChild; while (p != NULL | | st.length ( )!=0); 算法描述 p不空则p进栈，沿左子树方向传递指针 若p空但栈不空，出栈，p以栈顶值沿右子树方向传递指针 循环下去，直到p和栈都空为止 执行中栈的情况和指针的变化与递归程序相同 对于中序遍历只需调整输出语句位置即可 三、TBT的非递归算法 3、层次遍历 template void BinaryTree : LevelOrder ( ) queue * qu; BinTreeNode *p = root; qu.Enqueue(p); while (qu.DeQueue (p ) cout data

24、leftChild != NULL) qu.EnQueue (p - leftChild); if (p - rightChild != NULL) qu.EnQueue (p - rightChild); 三、TBT的非递归算法 层次遍历是指直上至下，从左到右访问结点 只有采用队列来存放结点地址才能实现层次遍历 3、层次遍历 fr p ad1ad2ad3ad4ad5ad6 0 1 2 3 4 5 6 7 A BC DEF root ad1 ad2ad3 ad4ad5ad6 5.4 线索化二叉树 一、概述 1、问题提出 遍历是二叉树最基本的运算，为避免再次遍历的 麻烦，可将首次遍历得到的信息存

25、于一个线性结构中 。 具有n个结点的链式存贮的二叉树中，有n+1个链 域是空的，能否充分利用这些空的链域来存放结点的 前趋指针和后继指针呢？ 一、概述 2、实现策略 结点中增加两个标记域 两标记域取值范围是0，1。各只占一个二进制位 ，只增加很少的额外空间开销。 rightChildleftChild leftThread data rightThread 指向左孩子 0 指向前驱 1 指向右孩子0 指向后继1 3、线索二叉树 指向前驱和指向后继的指针叫做线索（Thread）。 具有线索的二叉树叫做线索二叉树。 因遍历的次序有三种，所以线索二叉树也分前、中 、后序这三种。 中序遍历线索二叉树结

26、构示例 若根的左子树不空，侧其最左下角的结点为中序遍 历的第一个结点，否则根为中序遍历的第一个结点。 若根的右子树不空，侧其最右下角的结点为中序遍 历的最后一个结点，否则根为中序遍历的最后一个结点 。 0E0 0B0 1F0 0D1 1G1 1C1 1A1 root E DG root B A F C NULL NULL 二、中序线索二叉树的类定义 1、类声明 template class ThreadTree; template class ThreadNode friend class ThreadTree ; private: int leftThread, rightThread; T

27、hreadNode * leftChild, rightChild; Elem data; public: ThreadNode (const Elem item) : data (item), leftChild (NULL), rightChild (NULL), leftThread (0), rightThread (0) Elem getData ( ) const return data; template class ThreadTree private : ThreadNode *root; InThread (ThreadNode *current, ThreadNode *

28、pre); public : ThreadTree( ) : root(NULL) ; ThreadNode *First(ThreadNode *current); ThreadNode *Last(ThreadNode * current); ThreadNode *Next(ThreadNode *current); ThreadNode *Prior(ThreadNode *current); void Inorder( ); /从第一个结点开始沿着后继方向遍历二叉树 2、成员函数的实现 template ThreadNode * ThreadTree: First(ThreadNod

29、e * current) /返回以current为根指针的线索二叉树中序序列下的第一个结点 ThreadNode * p = current; while(p - leftThread = = 0) p = p - leftChild; /找最左下角的结点 return p; template ThreadNode * ThreadTree : Next (ThreadNode * current) ThreadNode *p = current - rightChild; if (current - rightThread = = 0) return first (p); else retu

30、rn p; current p next template ThreadNode * ThreadTree: last(ThreadNode * current) ThreadNode * p = current; while(p - rightThread = = 0) p = p - rightChild; /找右下角结点 return p; template ThreadNode * ThreadTree : Prior (ThreadNode * current) ThreadNode *p = current - leftChild; if (current - leftThread

31、 = = 0) return last (p); else return p; p current prior template void ThreadTree : InOrder ( ) ThreadNode * p;/在线索二叉树中进行中序遍历 for (p = first(root); p != NULL; p = Next(p) cout data void ThreadTree : InThread (ThreadNode * current, ThreadNode * pre) /通过中序遍历对以current为根的二叉树进行线索化 if (current != NULL) InT

32、hread (current - leftChild, pre); /左子树线索化 if (current - leftChild = = NULL) current - leftChild = pre; current - leftThread = 1; /建立当前结点的前驱线索 if (pre != NULL pre - rightThread = 1; /建前驱的后继线索 pre = current; InThread (current - rightChild, pre); /右子树线索化 5.5 二叉搜索树（Binary Search Tree） 一、基本概念 1、定义或是空、或是具

33、有下列性质的二叉树： 每个结点有一个作为搜索依据的关键码（Key）。 左子树上所有关键码小于根结点关键码。 右子树上所有关键码大于根结点关键码。 2、举例 中序遍历结果： 09，17，23，45，53，65，78，81 ，87，94 显然是有序的，故又称二叉排序树 。 53 65 81 870945 23 1778 94 一、基本概念 3、BST是基于二叉树的动态搜索结构，其删除和插入 结点可能要改变树的结构。 4、BST类定义特点 类定义基于二叉链存贮表示 与一般二叉树类定义十分相似 可以继承一般二叉树类的定义 基本运算Find, Insert 和 Remove 都用递归实现所以在 类定义中

34、包括私有和公用两种性质的声明 二叉查找树的C+类说明 template class BST: public Dictionary private: BinTreeNode * root; Elem RefValue int nodecount; void clearhelp(BinTreeNode*); BinTreeNode* inserthelp(BinTreeNode*,const Elem BinTreeNode* deletemin(BinTreeNode*,BinTreeNode* BinTreeNode* removehelp(BinTreeNode*, const Key bo

35、ol findhelp(BinTreeNode*, int) const; void printhelp(BinTreeNode* ,int) const; public: BST( ) root=NULL; nodecount=0; BST()clearhelp(root); void clear()clearhelp(root); root=NULL; nodecount=0; bool insert(const Elem nodecount+; return true; bool remove(const Key root=removehelp(root, K, t); e=t-val(

36、); nodecount-; delete t; return true; bool removeAny(Elem root=deletemin(root, t); e=t-val(); delete t; nodecount-; return true; bool find(counst Key int size()return nodecount; void print()const if(root=NULL) count bool BST: findHelp (BinNode*subroot, constKey else if (KEComp:lt(K,subroot-val() ret

37、urn findHelp (subroot-left(),K,e); else if (KEComp:gt(K,subroot-val() return findHelp (subroot-rightt(),K,e); else e=subroot-val(); return true; 该算法的递归调用语句都于程序的最尾，称为尾递归 返回时返回到上一层调用处的下条语句去执行 因为是最尾语句，程序结束，不必用栈保存返回地址 和局部变量的值 该算法可以不用栈，采用迭代方法改写成非递归程序 二、BST上的搜索 4、迭代算法 template bool BST: findHelp (BinTreeN

38、ode*subroot, constKey while (temp != NULL) if (KEComp:eq(K, temp-val() e=temp-val(); return true; if (KEComp:gt(K, temp-val() temp = temp -right(); else temp = temp - left(); return false; 一般对尾递归或单向递归的情形，都可利用迭代方法， 不使用栈将递归过程改为非递归过程 二、BST上的搜索 三、BST中的插入 1、方法 先搜索BST中有无该结点，只有无才插入 插入是作为叶子插入，插入后仍满足BST 插入位置

39、应是搜索操作停止（指针ptr为空）的地方 2、算法 template BinNode* BST: inserthelp(BinNode* subroot, const Elem if (EEComp:lt(val, subroot-val() subroot-setLeft(inserthelp(subroot-left(), val); else subroot-setRight( inserthelp(subroot-right(), val); / Return subtree with node inserted return subroot; 3、建BST 逐次输入关键码序列建一棵B

40、ST，是从空开始逐步插 入结点 每次从根开始搜索插入位置，然后将新结点作为叶 子插入 关键码集合相同但输入序列不同得到的BST也不同 若输入次序： 81, 65, 78, 94, 87, 88, 23, 45 , 09, 17, 53 81 87 17 2378 09 6594 45 53 88 三、BST中的插入 四、BST中的结点删除 1、原则 删除结点所断开的链要重新接起来 删除链接后仍是BST 重新链接后树的高度不增加 2、方法 被删结点为叶子，只需将双亲结点的相应指针置为空 被删结点无右子树，拿左孩子结点顶替它的位置 被删结点无左子树，拿右孩子结点顶替它的位置 被删结点左右子树都有，

41、在右子树中找中序遍历第一 个结点，用它的值填补到被删结点，然后再来删这个结点 结点删除是一个递归的过程 3、有左右子树的结点删除举例 删除关键码78的结点 右子树中序第一结点是81 81复盖78 81结点无左子树，用右孩 子88顶替 53 65 81 940945 23 1778 88 81 四、BST中的结点删除 81 88 template BinTreeNode* BST: deletemin(BinTreeNode*subroot,BinTreeNode* return subroot-right(); else subroot-SetLeft(deletemin(subroot-le

42、ft(),min) template BinTreeNode* BST: removehelp(BinTreeNode*subroot, constKey else if(KEComp:lt(K,subroot-val() subroot-setLeft(removehelp(subroot-left(),K,t); else if(KEComp:gt(K,subroot-val() subroot-setRight(removehelp(subroot-right(),K,t); else BinTreeNode*temp; t=subroot; if(subroot-left()=NULL

43、) subroot=subroot-right(); else if(subroot-right()=NULL)subroot=subroot-left(); else subroot-setRight(deletemin(subroot-right(),temp); Elem te=subroo-val(); subroot-setVal(temp-val(); temp-setVal(te); t=temp return subroot; 5.6 AVL树 一、AVL树（高度平衡的BST）概念 1、定义AVL或是空树，或是具有下列性质的BST： 它的左、右子树都是AVL树，且左右子树的高度

44、之差的绝 对值不超过1。 2、举例 是二叉搜索树 树和所有子树的左右子树 高度之差绝对值不超过1 属AVL树 11 15 14 2639 718 16 1 0 00 0 0 0 0 1 3、平衡因子（balance factor） 结点右子树高度减去左子树高度所得高度差 AVL树中所有结点的平衡因子只能取0，1，1 AVL树的ASL可保持在O(log2n) 二、平衡化旋转 1、向AVL树插入结点可能造成不平衡，此时要调整树的 结构使之重新达到平衡 2、平衡化旋转方法 从插入位置沿通向根的路径回溯检查各结点的平衡 因子 若发现不平衡结点，则从该结点起沿刚才回溯路径 取直接下两层结点 若三个结点在

45、一条直线上，则采用单旋转进行平衡 化；若三结点在一条折线上，则采用双旋转进行平衡化 3、平衡化旋转示例 左单旋转 h hh A B C DE 0 1 (a)AVL树 h h h+1 A B C DE 1 2 (b)E子树中插入结点 hh h+1 A B C D E 0 0 (c)左向旋转后的AVL树 二、平衡化旋转 右单旋转 h hh A BC DE 0 - 1 (a)AVL树 h h h+1 A B C DE - 1 - 2 (b)D子树中插入结点 hh h+1 A B C D E 0 0 (c) 右向旋转后的AVL树 3、平衡化旋转示例 二、平衡化旋转 先左后右双旋转 h h h-1 h

46、A B C D E FG 插入 (a)F子树插入结点 高度变为h - 2 1 - 1 hh h-1 h A B C D E F G (b)绕E，将B 逆时针转后 hh h-1 h A B CD E FG (c)绕E，将A 顺时针转后 0 3、平衡化旋转示例 二、平衡化旋转 先右后左旋转 h h h-1 h A BC DE FG 插入 (a)G子树插入结点 高度变为h 2 1 - 1 hh h-1 h A B C D E F G (b)绕D，C顺时 针转之后 hh h-1 h A B C D EFG (c)绕D，A逆时 针转之后 0 3、平衡化旋转示例 二、平衡化旋转 三、AVL树的建立 对于一

47、组关键码的输入序列，从空开始不断插入 结点，最后构成AVL树 每插入一个结点后就应判断从该结点到根的路径 上有无结点发生不平衡 如有不平衡问题，利用旋转方法进行树的调整， 使之平衡化 建AVL树过程是不断插入结点和必要时进行平衡 化的过程 5.7 堆（Heap） 一、堆的定义 1、什么是堆？ 若有n个关键字的集合K=k0,k1,k2, ,kn-1将其所有元素按完 全二叉树的顺序存贮方式存于一个一维数组中，并且满足以下 条件，则该集合称为最小堆（或最大堆）。 kik2i+1和kik2i+2 或 kik2i+1和kik2i+2 (其中，i = 0,1, (n 2) / 2 ) 举例 09 17 65 23 45 78 87 53 31 0 1 2 3 4 5 6 7 8 最小堆 87 78 53 45 65 09 31 17 23 0 1 2 3 4 5 6 7 8 最大堆 09 1765 23457887 5331 0 12 34 56 78 堆顶元素值最小 87 7853 45650931 1723 0 12 34 56 78 堆顶元素值最大 2、最小堆的类声明 template class MinHeap priv