资料 清华大学本科 数据结构 韩顺平整理 树与森林

1、树和森林的概念 二叉树 二叉树遍历 二叉树的计数 线索化二叉树 堆 树与森林 霍夫曼树,第六章 树与森林,树和森林的概念,树的定义 树是由 n (n 0) 个结点组成的有限集合。如果 n = 0，称为空树；如果 n 0，则 有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱； 除根以外的其它结点划分为 m (m 0) 个 互不相交的有限集合T0, T1, , Tm-1，每个集合又是一棵树，并且称之为根的子树。,树的特点,每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。,0层,1层,3层,2层,height = 3,A,C,G,B,D,E,F,K,L,H,M

2、,I,J,0层,1层,3层,2层,height = 3,A,C,G,B,D,E,F,K,L,H,M,I,J,结点 结点的度 分支结点 叶结点,子女 双亲 兄弟,祖先 子孙 结点层次,树的度 树高度 森林,template class Tree /对象: 树是由n(0)个结点组成的有限集 /合。在类界面中的position是树中结点的 /地址。在顺序存储方式下是下标型, 在链 /表存储方式下是指针型。Type是树结点中存放数据的类型。public: Tree ( ); Tree ( );,树的抽象数据类型,position Root ( ); BuildRoot ( const Type ,二叉

3、树 (Binary Tree),二叉树的定义,二叉树的五种不同形态,一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。,L,L,R,R,性质1 若二叉树的层次从0开始, 则在二叉树的第 i 层最多有 2i 个结点。(i 0) 证明用数学归纳法 性质2 高度为 h 的二叉树最多有 2h+1-1个结点。(h -1) 证明用求等比级数前k项和的公式 20 + 21 + 22 + + 2h = 2h+1-1,二叉树的性质,性质3 对任何一棵二叉树, 如果其叶结点有 n0 个, 度为2的非叶结点有 n2 个, 则有 n0n21 证明

4、：若设度为1的结点有 n1 个，总结点个数为 n，总边数为 e，则根据二叉树的定义， n = n0 + n1 + n2 e = 2n2 + n1 = n - 1 因此，有 2n2 + n1 = n0 + n1 + n2 - 1 n2 = n0 - 1 n0 = n2 + 1,定义1 满二叉树 (Full Binary Tree) 定义2 完全二叉树 (Complete Binary Tree) 若设二叉树的高度为h，则共有h+1层。除第 h 层外，其它各层 (0 h-1) 的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树。,性质4 具有 n (n 0) 个结点的完全二

5、叉树的高度为 log2(n+1) -1 证明：设完全二叉树的高度为 h，则有 2h - 1 n 2h+1 - 1 变形 2h n+1 2h+1 取对数 h log2(n+1) h+1 有 log2(n+1) = h+1 h = log2(n+1) -1,上面h层结点数,包括第h层的最大结点数,23-1,24-1,性质5 如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号0, 1, 2, , n-1，则有以下关系： 若i = 0, 则 i 无双亲 若i 0, 则 i 的双亲为(i -1)/2 若2*i+1 n, 则 i 的左子女为 2*i+1，若2*i+2 n, 则 i 的右子

6、女为2*i+2 若 i 为偶数, 且i != 0, 则其左兄弟为i-1, 若 i 为奇数, 且i != n-1, 则其右兄弟为i+1,0,1,2,3,7,4,5,6,8,9,二叉树的抽象数据类型,template class BinaryTree public: BinaryTree ( ); /构造函数 BinaryTree ( BinTreeNode * lch, BinTreeNode * rch, Type item ); /构造以item为根，lch和rch为左、右 /子树的二叉树 int IsEmpty ( ); /判二叉树空否？ BinTreeNode * Parent ( );

7、 /双亲,BinTreeNode * LeftChild ( ); /取左子女结点地址 BinTreeNode * RightChild ( ); /取右子女结点地址 int Insert ( const Type /取根结点地址 ,完全二叉树 一般二叉树 的顺序表示 的顺序表示,二叉树的顺序表示,0,0 1 2 3 4 5 6 7 8 9,13,0 1 2 3 5 6 7 8 11 13,1,3,7,8,9,4,5,6,2,0,1,2,6,5,3,7,8,11,0,0,2,6,14,2,6,14,30,极端情形: 只有右单支的二叉树,30,二叉树的链表表示,leftChild data ri

8、ghtChild,data,leftChild,rightChild,二叉链表,二叉树的链表表示,leftChild data parent rightChild,parent,data,leftChild,rightChild,三叉链表,二叉树链表表示的示例,A,A,A,B,B,B,C,C,C,D,D,D,F,F,F,E,E,E,root,root,root,二叉树 二叉链表 三叉链表,二叉链表的静态结构,A,B,C,D,F,E,root,data parent leftChild rightChild,0 1 2 3 4 5,A -1 1 -1 B 0 2 3 C 1 -1 -1 D 1

9、4 5 E 3 -1 -1 F 3 -1 -1,template class BinaryTree; template Class BinTreeNode friend class BinaryTree; private: Type data; BinTreeNode * leftChild; BinTreeNode * rightChild; public: BinTreeNode ( ) : leftChild (NULL), rightChild (NULL) ,二叉树的类定义,BinTreeNode ( Type item, BinTreeNode *left = NULL, BinT

10、reeNode *right = NULL ) : data (item), leftChild (left), rightChild (right) Type GetData ( ) const return data; BinTreeNode * GetLeft ( ) const return leftChild; BinTreeNode * GetRight ( ) const return rightChild; void SetData ( const Type ,void SetLeft ( BinTreeNode * L ) leftChild = L; void SetRig

11、ht ( BinTreeNode * R ) rightChild = R; ; template class BinaryTree private: BinTreeNode *root; Type RefValue; void CreateBinTree ( ifstream,BinTreeNode * Parent ( BinTreeNode * start, BinTreeNode * current ); int Insert ( BinTreeNode * /删除,public: virtual BinaryTree ( ) : root (NULL) virtual BinaryT

12、ree ( Type value ) : RefValue (value), root (NULL) virtual BinaryTree ( ) destroy ( root ); virtual int IsEmpty ( ) /判树空否 return root = NULL ? 1 : 0; virtual BinTreeNode * Parent ( BinTreeNode *current ) return root = NULL | root = current？ NULL : Parent ( root, current ); /找current结点的双亲,virtual Bin

13、TreeNode * LeftChild ( BinTreeNode *current ) /取current结点的左子女 return root != NULL ? current-leftChild : NULL; virtual BinTreeNode * RightChild ( BinTreeNode *current ) /取current结点的右子女 return root != NULL ? current-rightChild : NULL; virtual int Insert ( const Type,virtual BinTreeNode * Find ( const

14、Type /取根 friend istream destroy ( current-rightChild ); delete current; ,template BinTreeNode * BinaryTree : Parent ( BinTreeNode * start, BinTreeNode * cuurent ) if ( start = NULL ) return NULL; if ( start-leftChild = current | start-rightChild = current ) return start; BinTreeNode *p; if ( p = Par

15、ent ( start-leftChild, current ) != NULL ) return p; else return Parent(start-rightChild, current); ,template void BinaryTree : Traverse ( BinTreeNode *current, ostream ,template istream ,template ostream ,二叉树遍历,树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。 设访问根结点记作 V 遍历根的左子树记作 L 遍历根的右子树记作 R 则可能的遍历次序有 前序 VLR

16、 镜像 VRL 中序 LVR 镜像 RVL 后序 LRV 镜像 RLV,中序遍历二叉树算法的框架是： 若二叉树为空，则空操作； 否则 中序遍历左子树 (L)； 访问根结点 (V)； 中序遍历右子树 (R)。 遍历结果 a + b * c - d - e / f,中序遍历 (Inorder Traversal),-,-,/,+,*,a,b,c,d,e,f,二叉树递归的中序遍历算法 template void BinaryTree : InOrder ( BinTreeNode *current ) if ( current != NULL ) InOrder ( current-leftChil

17、d ); cout data; InOrder ( current-rightChild ); ,前序遍历二叉树算法的框架是： 若二叉树为空，则空操作； 否则 访问根结点 (V)； 前序遍历左子树 (L)； 前序遍历右子树 (R)。 遍历结果 - + a * b - c d / e f,前序遍历 (Preorder Traversal),-,-,/,+,*,a,b,c,d,e,f,二叉树递归的前序遍历算法 template void BinaryTree : PreOrder ( BinTreeNode * current ) if ( current != NULL ) cout data;

18、 PreOrder ( current-leftChild ); PreOrder ( current-rightChild ); ,后序遍历二叉树算法的框架是： 若二叉树为空，则空操作； 否则 后序遍历左子树 (L)； 后序遍历右子树 (R)； 访问根结点 (V)。 遍历结果 a b c d - * + e f / -,后序遍历 (Postorder Traversal),-,-,/,+,*,a,b,c,d,e,f,二叉树递归的后序遍历算法 template void BinaryTree : PostOrder ( BinTreeNode * current ) if ( current

19、!= NULL ) PostOrder ( current-leftChild ); PostOrder ( current-rightChild ); cout data; ,template void BinaryTree : InOrder ( ) InOrder ( root ); template void BinaryTree : PreOrder ( ) PreOrder ( root ); template void BinaryTree : PostOrder ( ) PostOrder ( root ); ,利用二叉树后序遍历计算二叉树结点个数,template int B

20、inaryTree : Count ( const BinTreeNode * t ) const if ( t = NULL ) return 0; else return 1 + Count ( t-leftChild ) + Count ( t-rightChild ); ,应用二叉树遍历的事例,template int BinaryTree : Height ( const BinTreeNode * t ) const if ( t = NULL ) return -1; else return 1 + Max ( Height ( t-leftChild ), Height ( t

21、-rightChild ) ); ,利用二叉树后序遍历计算二叉树的高度,以递归方式建立二叉树。 输入结点值的顺序必须对应二叉树结点前序遍历的顺序。并约定以输入序列中不可能出现的值作为空结点的值以结束递归, 此值在RefValue中。例如用“”或用“-1”表示字符序列或正整数序列空结点。,利用二叉树前序遍历建立二叉树,如图所示的二叉树的前序遍历顺序为 A B C D E G F ,A,B,C,D,E,G,F,template void BinaryTree : CreateBinTree ( ifstream if ( !in.eof ( ) ) ,in item; /读入根结点的值 if (

22、item != RefValue ) current = new BinTreeNode ( item );/建立根结点 if ( current = NULL ) cerr leftChild ); CreateBinTree ( in, current-rightChild ); else current = NULL; /封闭叶结点 ,利用栈的前序遍历非递归算法,a,b,c,d,e,c,d c,c,访问 a 进栈 c 左进 b,访问 b 进栈 d 左进 空,退栈 d 访问 d 左进 空,退栈 c 访问 c 左进 e,访问 e 左进 空 栈空 结束,template void Binary

23、Tree : PreOrder( ) stack * S; BinTreeNode * p = root; /初始化 S.Push ( NULL ); while ( p != NULL ) cout data rightChild != NULL ) S.Push ( p-rightChild ); /预留右子树指针在栈中,利用栈的前序遍历非递归算法,if ( p-leftChild != NULL ) p = p-leftChild; /进左子树 else p = S.getTop( ); S.Pop( ); /左子树为空, 进右子树 ,利用栈的中序遍历非递归算法,template voi

24、d BinaryTree : InOrder ( ) stack * S;,利用栈的中序遍历非递归算法,a,b,c,d,e,b a,a,d a,a,左空,退栈 访问,左空,退栈 访问,退栈 访问,左空,e c,退栈访问,c,c,右空,退栈访问 栈空结束,BinTreeNode * p = root; /初始化 do while ( p != NULL ) S.Push(p); p = p-leftChild; if ( !S.IsEmpty( ) ) /栈非空 p = S.getTop( ); S.Pop( ); /退栈 cout data rightChild; /向右链走 while (

25、p != NULL | !S.IsEmpty( ) ); ,利用栈的后序遍历非递归算法,后序遍历时使用的栈的结点定义 template struct stkNode BinTreeNode *ptr; enum tag L, R ; /该结点退栈标记 stkNode ( BinTreeNode* N = NULL ) : ptr (N), tag ( L ) /构造函数 ; 根结点的tag = L，表示从左子树退出, 访问右子树。tag = R, 表示从右子树退出, 访问根。,ptr tagL,R,a,b,c,d,e,aL,bL aL,bR aL,dL bR aL,dR bR aL,bR aL

26、,aL,aR,eL cL aR,eR cL aR,cL aR,cR aR,aR,template void BinaryTree : PostOrder ( ) stack st; stkNode w; BinTreeNode * p = root; do while ( p != NULL ) /向左子树走 w.ptr = p; w.tag = L; st.Push ( w ); p = p-leftChild; int continue = 1; /继续循环标记,while ( continue ,二叉树遍历的游标类 (Tree Iterator),二叉树的游标抽象基类 template

27、class TreeIterator public: TreeIterator ( const BinaryTree ,const Type,template const Type ,后序游标类 为记忆走过的结点，设置一个工作栈： S.PopTim = 0, 1或2，表示第几次退栈，用以 判断下一步向哪一个方向走。 后序遍历时，每遇到一个结点，先把它推入 栈中，让 S.PopTim = 0。 在遍历其左子树前，改结点的 S.PopTim = 1， 将其左子女推入栈中。 在遍历完左子树后，还不能访问该结点，要,结点地址 *Node 退栈次数 S.PopTim,a,b,c,d,e,a0,b0 a1

28、,b1 a1,d0 b2 a1,d2 b2 a1,b2 a1,a1,a2,e0 c1 a2,e2 c1 a2,c1 a2,c2 a2,a2,d1 b2 a1,c0,e1 c1 a2,继续遍历右子树，此时改结点的S.PopTim = 2，并把其右子女推入栈中。在遍历完右子树后，结点才退栈访问。,后序遍历游标类的定义 template struct stkNode /后序遍历使用的递归工作栈 结点定义 const BinTreeNode *Node; /结点指针 int PopTim; /退栈次数 stkNode ( BinTreeNode *N = NULL ) : Node (N), PopT

29、im (0) template class PostOrder : public TreeIterator public:,PostOrder ( const BinaryTree /工作栈 后序游标类成员函数的实现,template PostOrder : PostOrder ( const BinaryTree ,template void PostOrder : operator + ( ) if ( st.IsEmpty ( ) ) if ( current = NULL ) cout Cnode; for ( ; ; ) /循环,找后序下的下一个结点 Cnode = st.Pop (

30、 ); if ( +Cnode.PopTim = 3 ) /从右子树退出 current = Cnode.Node; return; ,st.Push ( Cnode ); /否则加一进栈 if ( Cnode.PopTim = 1 ) /左子女进栈 if ( Cnode.Node-GetLeft ( ) != NULL ) st.Push ( StkNode ( Cnode.Node-GetLeft ( ) ) ); else / =2,右子女进栈 if ( Cnode.Node-GetRight ( ) != NULL ) st.Push ( StkNode ( Cnode.Node-Ge

31、tRight ( ) ) ); ,中序游标类 中序遍历与后序遍历走过的路线一样，只是在从左子树退出后立即访问根结点，再遍历右子树。中序遍历也要使用一个递归工作栈 st。,中序游标类的定义 template class InOrder : public PostOrder public: InOrder ( BinaryTree void operator + ( ); ; 中序游标类operator +( )操作的实现 template void InOrder : operator + ( ) if ( st.IsEmpty ( ) ) if ( current = NULL ) cout

32、Cnode;,for ( ; ; ) /循环,找中序下的下一个结点 Cnode = st.Pop ( ); /退栈 if ( +Cnode.PopTim = 2 ) /从左子树退出，成为当前结点 current = Cnode.Node; if ( Cnode.Node-GetRight ( ) != NULL ) st.Push ( StkNode ( Cnode.Node-GetRight ( ) ) ); return; st.Push ( Cnode ); /否则加一进栈,if ( Cnode.Node-GetLeft ( ) != NULL ) st.Push ( StkNode (

33、 /左子女进栈 Cnode.Node-GetLeft ( ) ) ); ,层次序游标类 从根开始逐层访 问，用 FIFO 队列 实现。,遍历顺序,层次序游标类的定义 template class LevelOrder : public TreeIterator public: LevelOrder ( const BinaryTree ,层次序游标类的operator + ( )操作 template LevelOrder : LevelOrder ( const BinaryTree ,template void LevelOrder : operator + ( ) if ( qu.IsE

34、mpty ( ) ) if ( current = NULL ) cout GetLeft ( ) != NULL ) /左子女 qu.EnQueue ( current-GetLeft ( ) ); /进队列 if ( current-GetRight ( ) != NULL ) /右子女 qu.EnQueue ( current-GetRight ( ) ); /进队列 ,二叉树的计数,由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。 例, 前序序列 ABHFDECKG 和中序序列 HBDFAEKCG , 构造二叉树过程如下：,HBDF,EKCG,A,EKCG,A,B,H,DF,KCG

35、,前序序列 ABHFDECKG ,EKCG,A,B,H,DF,EKCG,A,B,H,F,D,E,A,B,H,F,D,E,A,B,H,F,D,C,K,G,如果前序序列固定不变，给出不同的中序序列，可得到不同的二叉树。,6,1,2,3,4,5,7,8,9,6,1,2,3,7,5,8,4,9,固定前序排列,选择所有可能的中序排列,可以可能构造多少种不同的二叉树？,例如, 有 3 个数据 1, 2, 3 ，可得 5 种不同的二叉树。它们的前序排列均为 123，中序序列可能是 123，132，213，231，321。,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,有0个, 1个, 2个,

36、3个结点的不同二叉树如下,b0 =1,b1 =1,b2 =2,b3 =5,b4 =14,计算具有 n 个结点的不同二叉树的棵数,Catalan函数,bi,bn-i-1,1,线索化二叉树 (Threaded Binary Tree),线索 (Thread),增加 Pred 指针和 Succ 指针的二叉树,线索化二叉树及其二叉链表表示,LeftThread=0, LeftChild为左子女指针 LeftThread=1, LeftChild为前驱线索 RightThread=0, RightChild为右子女指针 RightThread=1, RightChild为后继指针,LeftChild,R

37、ightChild,data,LeftThread,RightThread,中序线索化二叉树的类定义,template class ThreadTree;,template class ThreadNode friend class ThreadTree;private: int leftThread, rightThread; ThreadNode *leftChild, *rightChild; Type data;public: ThreadNode ( const Type item ) : data (item), leftChild (NULL), rightChild (NULL

38、), leftThread (0), rightThread (0) ;,template class ThreadTree private: ThreadNode * root; /根 InThread ( ThreadNode * current, ThreadNode * pre ); /建树 public: ThreadTree ( ) : root (NULL) ; /构造函数 ThreadNode * First ( ThreadNode * current ); ThreadNode * Last ( ThreadNode * current );,ThreadNode * Ne

39、xt ( ThreadNode * current ); ThreadNode * Prior ( ThreadNode * current ); ,通过中序遍历建立中序线索化二叉树,template void ThreadTree : InThread ( ThreadNode * current, ThreadNode * /建立当前结点的前驱线索,if ( pre != NULL /递归, 右子树线索化 ,template void ThreadTree : CreateInThread ( ) ThreadNode *pre = NULL; /前驱指针 if ( root != NUL

40、L ) /非空二叉树, 线索化 InThread ( root, pre ); /中序遍历线索化二叉树 pre-rightChild = NULL; pre-rightThread = 1; /后处理, 中序最后一个结点 ,0 A 0, 0 B 0,0 C 0 , 0 D 0 , 0 E 0 ,root,pre = NULL,current,0 A 0, 1 B 0,0 C 0 , 0 D 0 , 0 E 0 ,root,pre = NULL,current,0 A 0, 1 B 0,0 C 0 ,1 D 0 , 0 E 0 ,root,pre,current,0 A 0, 1 B 0,0 C

41、 0 ,1 D 1, 0 E 0 ,root,pre,current,0 A 0, 1 B 0,0 C 0 ,1 D 1,1 E 0 ,root,pre,current,0 A 0, 1 B 0,0 C 0 ,1 D 1,1 E 1,root,pre,current,0 A 0, 1 B 0,0 C 1 ,1 D 1,1 E 1,root,pre,后处理,if (current-rightThread =1) 后继为current-rightChild else /current-rightThread != 1 后继为当前结点右子树 的中序下的第一个结点,寻找当前结点在中序下的后继,A,B,

42、D,E,C,F,H,I,K,G,J,if (current-leftThread=1) 前驱为current-leftChild else /current-leftThread=0 前驱为当前结点左子树 中序下的最后一个结点,寻找当前结点在中序下的前驱,A,B,D,E,C,F,H,I,K,G,J,L,在中序线索化二叉树中部分成员函数的实现 template ThreadNode * ThreadTree : First ( ThreadNode * current ) /函数返回以*current为根在线索化二叉树中 /的中序序列下的第一个结点 ThreadNode * p = curren

43、t; while ( p-leftThread = 0 ) p = p-leftChild;/最左下的结点 return p; ,template ThreadNode * ThreadTree : Next ( ThreadNode * current ) /函数返回在线索化二叉树中结点*current在 /中序下的后继结点 ThreadNode *p = current-rightChild; if ( current-rightThread = 0 ) return First ( p ); /rightThread = 0, 表示有右子女 else return p;/rightThr

44、ead = 1, 直接返回后继线索 ,template void ThreadTree : Inorder ( ) /线索化二叉树的中序遍历 ThreadNode * p; for ( p = First ( ); p != NULL; p = Next ( ) ) cout data endl; ,前序线索化二叉树,前序序列 A B D C E,在前序线索化二叉树中 寻找当前结点的后继,p-leftThread=1?,前驱线索 =, 左子女,p-rightChild = NULL,后继为 p-leftChild,=,无后继,后继为 p-rightChild,A,B,C,E,D,后序线索化二叉

45、树,后序序列 D B E C A,在后序线索化二 叉树中寻找当前 结点的后继,p-rightThread=1?,后继线索 =, 右子女,后继为q的右子树中 后序下第一个结点,后继为 p-rightChild,=,无后继,后继为q,A,B,C,E,D,q=p-parent q=NULL?,Q-rightThread=1 | q-rightChild=p?,=,堆 ( Heap ),template class MinPQ public: Virtual void Insert ( const Type 最小优先级队列类的定义,优先级队列 每次出队列的是优先权最高的元素,完全二叉树 顺序表示 Ki

46、 K2i+1 /存放最小堆元素的数组 int CurrentSize; /最小堆当前元素个数 int MaxHeapSize; /最多允许元素个数 void FilterDown ( int i, int m ); /从 i 到m自顶向下进行调整成为最小堆,void FilterUp ( int i ); /从 i 到0自底向上进行调整成为最小堆 public: MinHeap ( int sz ); /构造函数 : 建立空堆 MinHeap ( Type arr , int n ); /构造函数 MinHeap ( ) delete heap; const MinHeap /删除,int I

47、sEmpty ( ) const /判堆空否 return CurrentSize = 0; int IsFull ( ) const /判堆满否 return CurrentSize = MaxHeapSize; void MakeEmpty ( ) CurrentSize = 0; ,堆的建立,template MinHeap : MinHeap ( int maxSize ) /根据给定大小maxSize,建立堆对象,MaxHeapSize = DefaultSize MinHeap : MinHeap ( Type arr , int n ) /根据给定数组中的数据和大小,建立堆对象,

48、MaxHeapSize = DefaultSize n ? n : DefaultSize; heap = new Type MaxHeapSize; if ( heap = NULL ) cerr “存储分配错!” endl; exit(1); for ( int i = 0; i n; i+ ) /数组传送 heapi = arri; CurrentSize = n; /当前堆大小 int currentPos = (CurrentSize-2)/2; /找最初调整位置:最后的分支结点号,while ( currentPos = 0 ) /从下到上逐步扩大,形成堆 FilterDown (

49、 currentPos, CurrentSize-1 ); /从currentPos开始,到CurrentSize止, /调整 currentPos-; ,自下向上逐步调整为最小堆,将一组用数组存放的任意数据调整成堆,53,53,17,17,78,78,09,23,45,65,87,i,09,23,45,65,87,currentPos = i = 3,currentPos = i = 2,i,53,53,17,17,78,78,09,23,45,65,87,i,09,23,45,65,87,currentPos = i = 1,i,53,53,17,17,78,78,09,23,45,65,

50、87,i,09,23,45,65,87,currentPos = i = 0,i,09,53,53,17,17,78,78,09,23,45,65,87,i,09,23,45,65,87,i,17,最小堆的向下调整算法 template void MinHeap : FilterDown ( int start, int EndOfHeap ) int i = start, j = 2*i+1; / j 是 i 的左子女 Type temp = heapi; while ( j heapj+1.key ) j+; /两子女中选小者,if ( temp.key int MinHeap : Ins

51、ert ( const Type return 0; heapCurrentSize = x; /插在表尾 FilterUp (CurrentSize); /向上调整为堆 CurrentSize+; /堆元素增一 return 1; 最小堆的向上调整算法,template void MinHeap : FilterUp ( int start ) /从 start 开始,向上直到0,调整堆 int j = start, i = (j-1)/2; / i 是 j 的双亲 Type temp = heapj; while ( j 0 ) if ( heapi.key = temp.key ) break; else heapj = heapi; j = i; i = (i -1)/2; heapj = temp; ,53,17,17,78,78,09,23,45,65,87,i,09,23,45,65,87,j,11,在堆中插入新