数据结构课件chp5.ppt

1、概述 二叉树 (Binary Tree) 二叉树的表示 二叉树遍历 (Binary Tree Traversal) 线索化二叉树 (Threaded Binary Tree) 堆 ( Heap ) 二叉查找树 选择树 树与森林 (Tree public: BinaryTree ( ); BinaryTree ( BinTreeNode * lch, BinTreeNode * rch, Type item ); int IsEmpty ( ); BinTreeNode *LeftChild ( ); BinTreeNode *RightChild ( ); int Insert ( const

2、 Type ,完全二叉树的数组表示 一般二叉树的数组表示,二叉树的表示,数组表示,单支树,链表表示,由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况。,二叉树链表表示的示例,二叉树的数组模拟链表,template class BinaryTree; template Class BinTreeNode friend class BinaryTree; public: BinTreeNode ( ) : leftChild (NULL), rightChild (NULL) private: BinTreeNode *leftChild, *rightCh

3、ild; Type data; ;,二叉树的链表表示的类定义,二叉树遍历 (Binary Tree Traversal),所谓树的遍历，就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。 设访问根结点记作 V 遍历根的左子树记作 L 遍历根的右子树记作 R 则可能的遍历次序有 前序 VLR 镜像 VRL 中序 LVR 镜像 RVL 后序 LRV 镜像 RLV,中序遍历二叉树算法的框架是： 若二叉树为空，则空操作； 否则 中序遍历左子树 (L)； 访问根结点 (V)； 中序遍历右子树 (R)。 遍历结果 a + b * c - d - e / f,中序遍历 (Inorder Tra

4、versal),表达式语法树,二叉树递归的中序遍历算法 emplate void BinaryTree :InOrder ( ) InOrder ( root ); template void BinaryTree : InOrder ( BinTreeNode *current ) if ( current != NULL ) InOrder ( currentleftChild ); cout currentdata; InOrder ( currentrightChild ); ,前序遍历 (Preorder Traversal),前序遍历二叉树算法的框架是 若二叉树为空，则空操作； 否

5、则 访问根结点 (V)； 前序遍历左子树 (L)； 前序遍历右子树 (R)。 遍历结果 - + a * b - c d / e f,二叉树递归的前序遍历算法 template void BinaryTree :PreOrder ( ) PreOrder ( root ); template void BinaryTree: PreOrder ( BinTreeNode *current ) if ( current != NULL ) cout currentdata; PreOrder ( currentleftChild ); PreOrder ( currentrightChild );

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

7、eftChild ); PostOrder ( currentrightChild ); cout currentdata; ,利用二叉树后序遍历计算二叉树结点个数及二叉树的高度,template int BinaryTree: Size ( const BinTreeNode *t ) const if ( t = NULL ) return 0; else return 1 + Size ( tleftChild ) + Size ( trightChild ); ,应用二叉树遍历的事例,template int BinaryTree: Depth ( const BinTreeNode

8、*t ) const if ( t = NULL ) return -1; else return 1 + Max ( Depth ( tleftChild ), Depth ( trightChild ) ); ,迭代中序遍历,二叉树遍历的迭代器 (Tree Iterator) P188,中序迭代器类 中序遍历，在从左子树退出后立即访问根结点，再遍历右子树。 中序遍历要使用一个递归工作栈 s。,Void Tree: NonrecInorder() Stack * st; TreeNode* currentNode=root; While(1) While (currentNode) s.pu

9、sh(currentNode); currentNode=currentNode-leftChild; If (s.IsEmpty() return; currentNode=s.Top(); s.Pop(); Visit(currentNode); currentNode=currentNode-rightChild; ,中序迭代器类的定义 template class InOrder public: InOrder ( BinaryTree 中序迭代器类operator +( )操作的实现 template Type currentNode=currentNode-leftChild; I

10、f (s.IsEmpty() return 0; currentNode=s.Top(); s.Pop(); Type,层次遍历（P190） 从根开始逐层访问， 用FIFO队列实现。,层次遍历,层次迭代器类的实现 template class LevelOrder : public TreeIterator public: LevelOrder ( const BinaryTree ,思考：不使用额外空间的遍历思考题：P191 (12),补充的二叉树操作(P193)二叉树的复制二叉树的检测相等满足性问题,线索化二叉树 (Threaded Binary Tree),线索 (Thread),增加P

11、red指针和Succ指针的二叉树,线索化二叉树及其二叉链表表示,LeftThread = 0, LeftChild为左子女指针 LeftThread = 1, LeftChild为前驱线索 RightThread = 0, RightChild为右子女指针 RightThread = 1, RighrChild为后继指针,中序线索化二叉树的类定义,template class ThreadNode friend class ThreadTree;friend class ThreadInorderIterator;private: int leftThread, rightThread; Th

12、readNode *leftChild, *rightChild; Type data;public: ThreadNode ( const Type item ) : data (item), leftChild (NULL), rightChild (NULL), leftThread (0), rightThread (0) ;,template class ThreadTree friend class ThreadInorderIterator; public: private: ThreadNode *root; ; template class ThreadInorderIter

13、ator public: ThreadInorderIterator ( ThreadTree ,ThreadNode * Next ( ); ThreadNode * Prior ( ); private: ThreadTree ,带表头结点的中序穿线链表,if (currentrightThread =1) if (currentrightChild !=T.root) 后继为 currentrightChild else 无后继 else /currentrightThread !=1 if (currentrightChild !=T.root) 后继为当前结点右子树 的中序下的第一个

14、结点 else 出错情况,寻找当前结点 在中序下的后继,A,B,D,E,C,F,H,I,K,G,J,L,if (currentleftThread =1) if (currentleftChild !=T.root) 前驱为currentleftChild else 无前驱 else /currentleftThread =0 if (currentleftChild !=T.root) 前驱为当前结点左子树的 中序下的最后一个结点 else 出错情况,寻找当前结点 在中序下的前驱,A,B,D,E,C,F,H,I,K,G,J,L,在中序线索化二叉树中的部分成员函数的实现 template Th

15、readNode * ThreadInorderIterator:First ( ) while ( currentleftThread = 0 ) current = currentleftChild; return current; template ThreadNode * ThreadInorderIterator:Next ( ) ThreadNode *p = currentrightChild; if ( currentrightThread = 0 ) while ( pleftThread = 0 ) p = pleftChild;,current = p; if ( cur

16、rent = T.root ) return NULL; else return current; template void ThreadInorderIterator:Inorder ( ) /线索化二叉树的中序遍历 ThreadNode * p; for ( p = First ( ); p != NULL; p = Next ( ) ) cout pdata endl; ,通过中序遍历建立中序线索化二叉树 template void ThreadTree: InThread ( ThreadNode *current, ThreadNode *pre ) if ( current !=

17、 NULL ) InThread ( currentleftChild, pre ); if ( currentleftChild = NULL ) currentleftChild = pre; currentleftThread = 1; if ( prerightChild = NULL ) prerightChild = current; prerightThread = 1; ,pre = current; InThread ( currentrightChild, pre ); template void ThreadTree:CreateInThread ( ) ThreadNo

18、de *pre; root = new ThreadNode; rootleftThread = 1; rootrightThread = 0; if ( this = NULL ) rootleftChild = root; rootrightChild = root; ,else current = rootleftChild = this; rootleftThread = 0; pre = root; InThread ( current, pre ); prerightChild = root; prerightThread = 1; ,前序线索化二叉树,前序序列 A B D C E

19、,在前序线索化二叉树中 寻找当前结点的后继,后序线索化二叉树,后序序列 D B E C A,在后序线索化二叉树中 寻找当前结点的后继,堆 ( Heap ),template class MinPQ public: Virtual void Insert ( const Type 最小优先级队列类的定义,优先级队列 每次出队列的是优先权最高的元素,堆的定义,完全二叉树的数组表示 Ki K2i+1 MinHeap ( Type arr , int n ); MinHeap ( ) delete heap; const MinHeap ,int IsFull ( ) const return Cur

20、rentSize = MaxHeapSize; void MakeEmpty ( ) CurrentSize = 0; private: enum DefaultSize = 10 ; Type *heap; int CurrentSize; int MaxHeapSize; void FilterDown ( int i, int m ); void FilterUp ( int i ); ,堆的建立,template MinHeap : MinHeap ( int maxSize ) /根据给定大小maxSize,建立堆对象 MaxHeapSize = DefaultSize MinHea

21、p : MinHeap ( Type arr , int n ) /根据给定数组中的数据和大小,建立堆对象,MaxHeapSize = DefaultSize = 0 ) /从下到上逐步扩大,形成堆 FilterDown ( currentPos, CurrentSize ); /从currentPos开始,到CurrentSize为止, 调整 currentPos-; ,自下向上逐步调整为最小堆,将一组用数组存放的任意数据调整成堆,最小堆的向下调整算法 template void MinHeap: FilterDown ( const int start, const int EndOfHe

22、ap ) int i = start, j = 2*i+1; / j 是 i 的左子女 Type temp = heapi; while ( j heapj+1.key ) j+;/两子女中选小者 if ( temp.key = heapj.key ) break; else heapi = heapj; i = j; j = 2*j+1; heapi = temp; ,堆的插入,template int MinHeap: Insert ( const Type ,template void MinHeap: FilterUp ( int start ) /从 start 开始,向上直到0,调

23、整堆 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; ,最小堆的向上调整,template int MinHeap : RemoveMin ( Type ,二叉查找树 (P205),二叉查找树或者是一棵空二叉树；或者是具有下列性质的二叉树：（1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若它的右

24、子树不空，则右子树上所有结点的值均大于它的根结点的值。（3）根结点的左右子树分别也是二叉查找树。 二叉查找树可以用来组织一组数据，并且实现在这组数据上的快速检索。,在二叉查找树上查找,如何在二叉查找树上检索给定的值？（限定二叉查找树上任何两个结点均不相同）（1）若二叉查找树为空，查找失败。（2）首先用给定的值和根结点的值进行比较，若相等，则查找成功。（3）若给定的值比根结点的值小，则转根结点的左子树进行查找。（4）若给定的值比根结点的值大，则转根结点的右子树进行查找。,在二叉查找树上查找,递归查找 迭代查找 通过排序查找,向二叉查找树插入结点,向二叉查找树中插入新结点必须保证插入新结点后，二叉

25、树仍然满足二叉查找树的定义。 如何在二叉查找树中插入新结点？（1）若二叉查找树为空，则新结点应作为二叉查找树的根结点。（2）将新结点的值和根结点的值比较，如果相等返回。（此时要插入的结点在树中已存在）（3）如果新结点的值小于根结点的值，则转二叉查找树的左子树继续插入操作。（4）如果新结点的值大于根结点的值，则转二叉查找树的右子树继续插入操作。,向二叉查找树插入结点,依次向一棵空的二叉查找树插入下面的关键字：e、b、d、f、a、g 和 c。,从二叉查找树上删除结点,从二叉查找树上删除结点应保证结点删除后得到的二叉树仍然是二叉查找树。 如何从二叉查找树中删除结点？（1）如果要删除的结点是叶子结点，

26、直接删除并更新父结点指针。（2）如果要删除的结点只有一棵非空子树，则令该非空子树代替被删除的结点作为被删除结点父结点的相应子树。（3）如果要删除的结点的两棵子树均非空，问题比较复杂，此时用要删除结点的中序前趋替换要删除的结点，再运用（1）和(2)中的方法删除处在原来位置上的要删除结点的中序前趋。（或中序后继） 一个结点的中序前趋有什么特点？如何找一个结点的中序前趋？（或中序后继）,从二叉查找树上删除结点,二叉查找树的查找效率,不同的插入顺序导致不同的二叉查找树。例如，按照下列顺序插入构造二叉查找树（1）d、b、a、c、f、e和g（2）a、b、c、d、e、f和g 当插入的结点顺序排列时，二叉查找

27、树蜕变成一棵单链树。 在一棵完全平衡的二叉查找树上成功查找一个结点比较次数最多为 在一棵单链树中成功查找一个结点最多比较次数为n。,二叉查找树的优点和缺点,优点（1）二叉查找树查找效率高于一般顺序表的查找效率。尤其二叉查找树是比较平衡的二叉查找树时如此。（2）二叉查找树为链式存储，插入和删除无需移动大量结点。 缺点（1）由于插入结点的顺序常常无法准确预测，构造出的二叉查找树通常不是平衡的二叉查找树。 需要一种方法保持二叉查找树的平衡性。,顺串是记录的有限序列，且这些记录按关键字的非递减顺序排列。 假设需要将k个顺串归并为一个，这可通过反复输出关键字最小的记录完成。 最小关键字可能在k个顺串的前

28、端记录的任何一个之中，因此需要从k种可能中选出最小。最直接的方法是作k 1次比较。但对于k 2，如果利用上一次比较获得的知识，就可以使本次及以后比较的次数减少。 选择树就是一种能够记载上一次比较获得的知识的数据结构。选择树是一棵完全二叉树，有胜者树和败者树两种。,选择树 (P213),4.6.1 胜者树,胜者树的构造与锦标赛类似，胜者是关键字较小的记录。每个非叶结点表示比赛的胜者，根结点表示总胜者，即树中关键字最小的结点。 作为完全树，胜者树可用顺序方法表示。每个叶结点表示相应顺串的第一个记录。 由于记录一般较大，每个结点实际存放的是其所表示记录的缓冲区下标。 设bufi存放顺串i（0i k）

29、的第一个记录，则bufi对应的叶结点编号是k + i，这意味着叶结点存放的下标可推算得到，不必用空间存储。,下图是一棵k = 8的胜者树：,其中，每个结点旁的数字是该结点的顺序编号。虽然每个非叶结点实际存放胜者记录下标，但为便于直观比较，图中也给出了胜者的关键字。叶结点直接用bufi代替。 由根结点指向的记录（buf3）的关键字最小，可输出。顺串3的下一个记录进入buf3，其关键字为15。为了重构胜者树，需要沿buf3对应的叶结点到根结点进行一系列比赛。 结点10和11比赛的胜者又是结点11（15 20），结点4和5比赛的胜者是结点4（9 15），结点2和3比赛的胜者是结点3（8 9）。,新的

30、胜者树如下图：,其中，粗体字结点是发生了变化的结点。可见，比赛是在兄弟结点之间进行，结果存放在它们的双亲结点中。新一轮比赛在下一个更靠近根的层次进行。 分析：除去叶结点层，树的层数为log2(k + 1)，所以重构树的时间为O(log2k)。对于每一个归并到输出文件的记录都需要重构树，归并n个记录的时间是O(n log2k)。建立初始胜者树的时间是O(k)。因此，归并k个顺串的总时间是O(n log2k)。,败者树,胜者树重构的比赛是沿上次输出的记录缓冲区对应的叶结点到根的路径，与兄弟结点进行的。 可以令非叶结点指向比赛的败者记录而不是胜者记录，从而简化重构过程。 非叶结点存放败者记录下标的选

31、择树称为败者树。实际上，结点p中的败者是与结点p的两个子女对应的比赛的胜者比赛的败者。 下一页是与前面第一棵胜者树对应的败者树。其中增加了结点0，用于表示整个比赛的胜者。,与前面第一棵胜者树对应的败者树,树的存储表示 广义表表示,树的广义表表示 (结点的utype域没有画出),森林(P215), 双亲表示, 左子女-右兄弟表示法,第一种解决方案,第二种解决方案,树的左子女-右兄弟表示,data,child1,child2,child3,childd,data,firstChild,nextSibling,森林与二叉树的转换,森林与二叉树的对应关系,(1) 森林转化成二叉树的规则 若F为空，即n = 0，则 对应的二叉树B为空二叉树。 若F不空，则 对应二叉树B的根root (B)是F中第一棵树T1的根root (T1)； 其左子树为B (T11, T12, , T1m)，其中，T11, T12, , T1m是root (T1)的子树； 其右子树为B