第5章二叉树(1)

1、2021-11-25数据结构与算法数据结构与算法第第5 5章章 二叉树二叉树朱凌朱凌 2021-11-25二叉树知识点二叉树知识点1 1 2 2 3 4 1 2 5 1 2 3 4 6 7 8 线性结构、树形结构、图结构线性结构、树形结构、图结构复习n 数据的逻辑结构可以表示为和： K：。 R：K。 R是KK上的二元关系。：唯一前驱、唯一后继，反映一种关系。：唯一前驱、多个后继，反映一种关系。：不限制前驱的个数，也不限制后继的个数，反映一种关系。树与子树树与子树n 一棵树可以分成几个大的分支（称为），每个大分支再分成几个小分支，小分支再分成更小的分支，。二叉树二叉树n 二叉树是一种，特殊在于：

2、 每个结点最多(称为)，也就是说每个结点的子女结点为0个、1个或2个； 两个子女结点，即使只有1个子女结点，也要区分为是左子女结点还是右子女结点。1 1 二叉树的概念二叉树的概念n 通常用来描述中的一些概念。：若在树中存在从结点k指向结点k的连线，则称k是k的(parent，也称，或简称为)，而k是k的(child，也称，或简称为)。树的：没有父结点的结点称为树的(root)。：若有k指向k和k指向k，则称k和k互为(sibling)。：父结点指向子女结点的连线，称为(edge)。可以认为，由父结点指向子女结点。：若存在结点序列k0, k1, , ks，使得, , , 都是树中的边，则该结点序

3、列称为从结点k0到结点ks的(path)。注意，。：路径中边的数目称为路径长度。和：若存在一条从k到ks的路径，则称k是ks的(ancestor)，ks是k的(descendant)。和：没有子女结点的结点称为(leaf)或，而非终端结点的结点称为或(internal node)。：一个结点的子女结点个数称为该结点的(degree)。：根结点的(level)为0，。：树的(height)为树的深度(即所有结点的最大层次)加1。（，层次和高度的关系类似于数组中元素下标和数组长度的关系)。：所有结点的最大层次，称为树的(depth)。1 1 二叉树的定义及相关概念二叉树的定义及相关概念n 二叉树(

4、binary tree)的：二叉树由结点的有限集合构成，这个有限集合，、分别称为这个根结点的左子树和右子树的。 这是一个的定义。n 二叉树的：2 2 满二叉树、完全二叉树和扩充二叉树满二叉树、完全二叉树和扩充二叉树、是二叉树的几个特殊情形。n 注意： 极少数教材上。是本课件自己定义的概念(目前还没有哪本教材定义了这个概念)，但有的教材将这种二叉树定义为满二叉树。 总之，现有的教材对这3种特殊的二叉树定义比较。本课件对这3种特殊二叉树的，今后的讨论以本课件中的概念和定义方式为准。满二叉树满二叉树：满足以下条件的二叉树，称为满二叉树(full binary tree)。即。 或者：。完全二叉树完全

5、二叉树：满足以下条件的二叉树，称为完全二叉树(complete binary tree)。 或者：。完全满二叉树完全满二叉树：满足以下条件的二叉树，称为完全满二叉树。 第i层有个结点。即。：。(见备注)扩充二叉树扩充二叉树：当二叉树里出现了空的子树，就增加新的、特殊的结点；对于原来二叉树度数为1的分支结点，在它下面增加一个空树叶；对于原来二叉树的树叶，在它下面增加两个空树叶；经过这样的构造得到的二叉树称为。n 在下图中，用表示空树叶。n 8节介绍的就是一种扩充二叉树。，（即树叶）。：从扩充二叉树的根到每个外部结点的路径长度之和。 在下图中，E = 2 + 3 + 3 + 3 + 4 + 4 +

6、 4 + 4 + 4 + 4 = 35。：从扩充二叉树的根到每个内部结点的路径长度之和。 在下图中，I = 1 + 1 + 2 + 2 + 2 + 3 + 3 + 3 = 17。n 扩充二叉树的：。：，其中n为扩充二叉树内部结点个数，也就是原二叉树结点个数。2 2 二叉树的主要性质二叉树的主要性质) 1(log2n) 1(log2n3 3 二叉树的抽象数据类型二叉树的抽象数据类型n 二叉树的的。如： 初始化二叉树； 把两棵二叉树的根结点作为一个新根结点的子结点来合并两棵二叉树。 等等。n 二叉树的的。如： 访问某个结点的左子结点、右子结点、父结点，或者访问结点中存储的数据。n 二叉树的抽象数据

7、类型包括结点类和二叉树类。：二叉树的抽象数据类型：二叉树的抽象数据类型提供：结点的数据域info。：丰富的构造函数、返回和设置左右子女结点指针、返回和设置结点的数据域、判断结点是否为树叶等。提供：二叉树根结点root。：丰富的构造函数、析构函数、判断二叉树是否为空树、返回二叉树的根结点、获取当前结点的父结点、获取当前结点的左兄弟或右兄弟、丰富的遍历函数等。二叉树结点类二叉树结点类BinaryTreeNodeBinaryTreeNode/声明声明BinaryTree类，因为在类，因为在BinaryTreeNode类中用到了标识符类中用到了标识符BinaryTreetemplate class B

8、inaryTree;templateclass BinaryTreeNode/二叉树结点的抽象数据类型二叉树结点的抽象数据类型friend class BinaryTree;/声明二叉树类为结点类的友元类声明二叉树类为结点类的友元类,便于访问私有数据成员便于访问私有数据成员private:T info;/二叉树结点数据域二叉树结点数据域/实现时，可以补充结点的左子结点、右子结点指针作为数据成员实现时，可以补充结点的左子结点、右子结点指针作为数据成员public:BinaryTreeNode( );/缺省构造函数缺省构造函数BinaryTreeNode( const T& ele );/

9、给定数据的构造函数给定数据的构造函数/给定了结点值和左右子树的构造函数给定了结点值和左右子树的构造函数BinaryTreeNode( const T& ele, BinaryTreeNode *l, BinaryTreeNode *r );T value( ) const;/返回当前结点的数据返回当前结点的数据BinaryTreeNode* leftchild( ) const;/返回当前结点的左子树指针返回当前结点的左子树指针BinaryTreeNode* rightchild( ) const;/返回当前结点的右子树指针返回当前结点的右子树指针void setLeftchild(

10、BinaryTreeNode* L );/设置当前结点的左子树指针设置当前结点的左子树指针void setRightchild( BinaryTreeNode* R );/设置当前结点的右子树指针设置当前结点的右子树指针void setValue( const T& val );/设置当前结点的数据域设置当前结点的数据域bool isLeaf( ) const;/判定当前结点是否为叶结点，若是则返回判定当前结点是否为叶结点，若是则返回trueBinaryTreeNode &operator=(const BinaryTreeNode & Node);二叉树类二叉树类Bi

11、naryTreeBinaryTreetemplateclass BinaryTree/二叉树的抽象数据类型二叉树的抽象数据类型protected:BinaryTreeNode* root;/二叉树根结点二叉树根结点public:BinaryTree( ) root = NULL; /缺省构造函数缺省构造函数BinaryTree( ) DeleteBinaryTree( root ); /析构函数析构函数bool isEmpty( ) ;/判定二叉树是否为空树判定二叉树是否为空树BinaryTreeNode* Root( ) return root; /返回二叉树根结点返回二叉树根结点/返回返回

12、current结点的父结点结点的父结点BinaryTreeNode* Parent( BinaryTreeNode * current );/返回返回current结点的左兄弟结点的左兄弟BinaryTreeNode* LeftSibling( BinaryTreeNode * current );/返回返回current结点的右兄弟结点的右兄弟BinaryTreeNode* RightSibling( BinaryTreeNode * current );/以以val作为根结点，作为根结点，leftTree作为树的左子树，作为树的左子树，rightTree作为树的右子树作为树的右子树/构造一

13、棵新的二叉树构造一棵新的二叉树void CreateTree( const T& info, BinaryTree& leftTree,BinaryTree& rightTree );/以下是深度优先遍历二叉树以下是深度优先遍历二叉树void PreOrder( BinaryTreeNode * root );/前序遍历二叉树或其子树前序遍历二叉树或其子树void InOrder( BinaryTreeNode * root );/中序遍历二叉树或其子树中序遍历二叉树或其子树void PostOrder( BinaryTreeNode * root );/后序遍历二叉树

14、或其子树后序遍历二叉树或其子树/以下是按层次遍历二叉树或其子树以下是按层次遍历二叉树或其子树(即广度优先遍历即广度优先遍历)void LevelOrder( BinaryTreeNode * root );void DeleteBinaryTree( BinaryTreeNode * root );/删除二叉树或其子树删除二叉树或其子树;4 4 二叉树的遍历二叉树的遍历(traversal)：也称为(search)，指按一定次序系统地访问二叉树中的所有结点，使得每个结点恰被访问一次。n 二叉树是一种非线性的数据结构。遍历二叉树的过程实际上就是，或者说。可以线性化为：D, B, G, E, H,

15、 A, F, I, C(实际上是)。也可以线性化为其他顺序的序列。两种重要的遍历方法两种重要的遍历方法： 本质上是一种，可以采用递归方式实现；但也可以采用非递归方式实现。：是一种。1 1 深度优先搜索二叉树深度优先搜索二叉树n 二叉树的基本结构如下图所示。一棵二叉树(在此用 表示)、和三部分组成。n 如果。则按照根结点的访问顺序可以将深度优先遍历分为以下3种方式：( )：访问三部分的顺序为。( )：访问顺序为。( )：访问顺序为。分别按前序、中序、后序遍历右图所示的二叉树，将得到怎样的结点序列？的为：访问根结点；按前序遍历左子树；按前序遍历右子树。的为：按中序遍历左子树；访问根结点；按中序遍历

16、右子树。的为：按后续遍历左子树；按后续遍历右子树；访问根结点。1 1 深度优先搜索二叉树的递归实现深度优先搜索二叉树的递归实现n 二叉树的深度优先搜索是的。n 以为例，要遍历一棵二叉树，首先访问根结点，然后进入根结点的左子树，在左子树中又是先访问根，然后向左下降进入左子树；如此进行下去，直到遇到树叶，也就是说。的为：访问根结点；按前序遍历左子树；按前序遍历右子树。深度优先搜索深度优先搜索n 要设计一个实现二叉树深度优先遍历的算法，就必须设计一个数据结构，以便当遍历完一个根的左子树后能顺利的转移到这个根结点的右子树继续遍历下去。n 这个数据结构通常是一个。对(即)，系统为程序分配一个()；如果要

17、采用，则用户需要。(以前序遍历为例演示)的为：访问根结点；按前序遍历左子树；按前序遍历右子树。隐式和显式另外一个实例隐式和显式另外一个实例thisthis指针指针n 在类的成员函数里有两种方法：实际上也是通过this指针来访问的，地使用this指针。：地使用this指针。(P108)(P108)二叉树类二叉树类BinaryTreeBinaryTree实现：实现：template /递归前序遍历二叉树或其子树递归前序遍历二叉树或其子树void BinaryTree:PreOrder( BinaryTreeNode* root )if( root!=NULL )Visit(root-Value()

18、;/访问当前结点访问当前结点PreOrder( root-leftchild() ); /访问左子树访问左子树PreOrder( root-rightchild() );/访问右子树访问右子树template/递归中序遍历二叉树或其子树递归中序遍历二叉树或其子树void BinaryTree:InOrder( BinaryTreeNode* root )if( root!=NULL )InOrder( root-leftchild() );/访问左子树访问左子树Visit(root-Value(); /访问当前结点访问当前结点InOrder( root-rightchild() ); /访问右

19、子树访问右子树template/递归后序遍历二叉树或其子树递归后序遍历二叉树或其子树void BinaryTree:PostOrder( BinaryTreeNode* root )if( root!=NULL )PostOrder( root-leftchild() );/访问左子树访问左子树PostOrder( root-rightchild() );/访问右子树访问右子树Visit(root-Value(); /访问当前结点访问当前结点2 2 遍历二叉树遍历二叉树n 栈是实现递归的最常用的数据结构，所以对于递归定义的二叉树遍历运算，最自然的是，。n 使用栈的算法很简单。请用示意图描述用非

20、递归方式对下图所示的二叉树进行前序遍历时栈的存储情况及入栈、出栈操作序列。遇到一个结点，然后下降去遍历它的左子树；遍历完它的左子树后，继续遍历。演示：非递归前序遍历时栈的使用演示：非递归前序遍历时栈的使用遇到一个结点，遇到一个结点，然后下降去遍，然后下降去遍历它的左子树；遍历完它的左子树后，历它的左子树；遍历完它的左子树后，继续遍历。，继续遍历。(P109)(P109)二叉树类二叉树类BinaryTreeBinaryTree实现：实现：template/非递归前序遍历二叉树或其子树非递归前序遍历二叉树或其子树void BinaryTree:PreOrderWithoutRecusion( Bi

21、naryTreeNode* root )using std:stack;stack BinaryTreeNode* aStack; /栈中的结点为二叉树结点指针栈中的结点为二叉树结点指针BinaryTreeNode* pointer = root;/保存输入参数保存输入参数aStack.push(NULL);while( pointer )Visit(pointer-Value(); /访问当前结点访问当前结点if( pointer-rightchild()!=NULL )aStack.push( pointer-rightchild() );/非空右孩子入栈非空右孩子入栈 if( point

22、er-leftchild()!=NULL ) pointer=pointer-leftchild() );/左路下降左路下降else/左子树访问完毕，转向访问右子树左子树访问完毕，转向访问右子树pointer = aStack.top( );/栈顶元素退栈栈顶元素退栈aStack.pop( );/栈顶元素退栈栈顶元素退栈/end of if/end of while遇到一个结点，就，然后下降去遍历它的左子树；遍历完它的左子树后，以输出结点的值作为访问结点的操作3 3 遍历二叉树遍历二叉树n 使用栈的算法也很简单。请用示意图描述用非递归方式对下图所示的二叉树进行中序遍历时栈的存储情况及入栈、出栈

23、操作序列。遇到一个结点，然后下降去遍历它的左子树；遍历完它的左子树后，然后按它的右指针指示的地址再去遍历该结点的右子树。(P109)(P109)二叉树类二叉树类BinaryTreeBinaryTree实现：实现：template/非递归中序遍历二叉树或其子树非递归中序遍历二叉树或其子树void BinaryTree:InOrderWithoutRecusion( BinaryTreeNode* root )using std:stack;stack BinaryTreeNode* aStack; /栈中的结点为二叉树结点指针栈中的结点为二叉树结点指针BinaryTreeNode* pointe

24、r = root;/保存输入参数保存输入参数while( !aStack.empty( ) | pointer )if( pointer )aStack.push( pointer );/当前结点地址入栈当前结点地址入栈pointer = pointer-leftchild();/当前链接结构指向左孩子当前链接结构指向左孩子else/左子树访问完毕，转向访问右子树左子树访问完毕，转向访问右子树pointer = aStack.top( );aStack.pop();/栈顶元素退栈栈顶元素退栈Visit(pointer-value();/访问当前结点访问当前结点pointer = pointer

25、-rightchild();/当前链接结构指向右孩子当前链接结构指向右孩子/end of if/end of while遇到一个结点，然后下降去遍历它的左子树；遍历完它的左子树后，然后按它的右指针指示的地址再去遍历该结点的右子树。以输出结点的值作为访问结点的操作4 4 遍历二叉树遍历二叉树n 后续遍历二叉树的非递归实现比中序遍历和前序遍历都更复杂。请用示意图描述用非递归方式对下图所示的二叉树进行后序遍历时栈的存储情况及入栈、出栈操作序列。遇到一个结点，去遍历它的左子树；，而是要再按照它的右子树指针所指示的地址去遍历该结点的右子树；。后序遍历二叉树的非递归实现方法后序遍历二叉树的非递归实现方法n

26、 在实现时，需要给栈中的每个结点加上一个，以便当从栈顶取出一个结点时（），（）。n 约定特征位为时，表示已进入该结点的左子树，将从左子树回来；特征位为时，表示已进入该结点的右子树，将从右子树回来。可以。enum Tags Left, Right ;/结点的标志结点的标志(枚举类型枚举类型)，Left为为0，Right为为1template class StackElement/栈中的结点栈中的结点(非递归后续遍历中用到的非递归后续遍历中用到的)public:BinaryTreeNode* pointer;Tags tag;(P110)(P110)二叉树类二叉树类BinaryTreeBinary

27、Tree实现：实现：template/非递归后序遍历二叉树或其子树非递归后序遍历二叉树或其子树void BinaryTree:PostOrderWithoutRecusion( BinaryTreeNode* root )using std:stack;StackElement element;stack StackElement aStack;BinaryTreeNode* pointer;if （root= NULL) return;/空树即返回空树即返回else pointer = root;遇到一个结点，去遍历它的左子树；，而是要再按照它的右子树指针所指示的地址去遍历该结点的右子树；。

28、while( !aStack.empty() | pointer )while( pointer!=NULL )/进入左子树，直到左子树中最下方的树叶进入左子树，直到左子树中最下方的树叶element.pointer = pointer;element.tag = Left;aStack.push( element );pointer = pointer-leftchild();element = aStack.top( );/取出栈顶元素取出栈顶元素aStack.pop( ); /弹出栈顶元素弹出栈顶元素pointer = element.pointer;if (element.tag= L

29、eft) /如果从左子树回来如果从左子树回来element.tag=Right; /则现在进入右子树则现在进入右子树aStack.push( element );pointer = pointer-rightchild();else /如果从右子树回来如果从右子树回来Visit( pointer-value(); /访问当前结点访问当前结点pointer=NULL;/end of while( true )遇到一个结点，去遍历它的左子树；，而是要再按照它的右子树指针所指示的地址去遍历该结点的右子树；。以输出结点的值作为访问结点的操作2 2 广度优先搜索二叉树广度优先搜索二叉树：从二叉树的第0层

30、(即根结点)开始，自上而下逐层遍历，在同一层中按从左到右的顺序对结点逐一访问。因此广度优先遍历也称为。n 在进行广度优先遍历时，对二叉树一层结点访问完成之后，要按照它们的访问次序对各个结点的左子树和右子树按顺序进行访问。因此在进行广度优先遍历时，。请用示意图描述用BFS对下图所示的二叉树进行遍历时队列的存储情况及入队列、出队列操作序列。(P112)(P112)二叉树类二叉树类BinaryTreeBinaryTree实现：实现：template /按层次遍历二叉树或其子树按层次遍历二叉树或其子树(即广度优先遍历即广度优先遍历)void BinaryTree:LevelOrder( BinaryT

31、reeNode* root )using std:queue;queue BinaryTreeNode* aQueue;BinaryTreeNode* pointer = root;if( pointer )/非空树非空树aQueue.push( pointer );while( !aQueue.empty( ) )pointer = aQueue.front( );aQueue.pop( );Visit( pointer-value();/访问当前结点访问当前结点if( pointer-leftchild()!=NULL )aQueue.push( pointer-leftchild() )

32、;if( pointer-rightchild()!=NULL )aQueue.push( pointer-rightchild() );二叉树的存储结构二叉树的存储结构n 二叉树是一种(指)。针对二叉树的各种应用，在存储器中有多种不同的表示二叉树的方法(指)，这些方法都是(顺序、链式、索引、哈希)的组合应用。1 1 用指针实现二叉树用指针实现二叉树：每个结点中除存储结点本身的数据外还有。：在二叉链表的基础上，在每个结点中再增加一个。有了指向父结点的指针，就给了的能力。2 2 用数组实现完全二叉树用数组实现完全二叉树n 在完全二叉树中，所有结点可以按图(b)所示的蛇形方式排列。n 因此，可以按

33、存储完全二叉树中的结点： ()将完全二叉树中的每个结点按图(b)所示的顺序存储在一片连续的存储空间中。 ()根据结点序号推断出父结点、左右子女结点、左右兄弟结点(见下页)。二叉搜索树二叉搜索树n 树形结构的一个重要应用是用来(详见后面的重要性质2)，用适用于内存储器的一种重要的。(BST，Binary Search Tree)，也称“二叉排序树”、“二叉查找树”、“二叉检索树”等。其定义如下： 或者是一颗； 或者是具有下列性质的二叉树：对于任何一个结点，设其值为K，则；而且它的左右子树也分别为二叉搜索树。 说明：此处的“小于”和“大于”可以。n 二叉搜索树的定义是一种的定义。二叉搜索树例子二叉

34、搜索树例子n 设一棵二叉树的每个结点对应一个关键码，整棵二叉树各结点对应的关键码组成一个。设一个关键码集合K为： ，则下图所示的二叉树就是一棵二叉搜索树。二叉搜索树的重要性质二叉搜索树的重要性质(1)(1)n 二叉搜索树的：将各结点的值输出来，将得到。将关键码集合组织成二叉搜索树，实际上起了，按中序遍历二叉搜索树就能得到排好的关键码序列。n 例如，对下图所示的BST进行中序遍历后得到的序列为：。二叉搜索树的重要性质二叉搜索树的重要性质(2)(2)n 二叉搜索树的效率在于：从根结点开始，在二叉搜索树中检索值K。 如果根结点储存的值为K，则检索结束。 如果K小于根结点的值，则。 如果K大于根结点的

35、值，就。n 这个过程一直持续到K被找到；或者在查找过程中，如果遇上树叶仍没有发现K，那么K就不在该二叉搜索树中。n 设二叉搜索树的，则其高度的数量级为，因此在BST中查找一个结点的时间复杂度为；如果n为21010，则最多只需比较10次就能找到结点或者得出不存在的结论。而其他查找算法一般为。：二叉搜索树抽象数据类型：二叉搜索树抽象数据类型n 本题中设计的二叉搜索类是，所以只需要为BST，主要是、和的操作。因为需要在中访问二叉树结点类的，所以需要在BinaryTreeNode类中将BinarySearchTree类，并在BinaryTreeNode类提前申明BinarySearchTree类。方法

36、如下：/提前声明提前声明BinaryTree类和类和BinarySearchTree类类template class BinaryTree;template class BinarySearchTree;templateclass BinaryTreeNode/二叉树结点的抽象数据类型二叉树结点的抽象数据类型friend class BinaryTree; /声明二叉树类为结点类的友元类，便于访问私有数据声明二叉树类为结点类的友元类，便于访问私有数据friend class BinarySearchTree;/声明二叉搜索树类为结点类的友元类声明二叉搜索树类为结点类的友元类(1) (1) 二叉

37、搜索树的声明二叉搜索树的声明#include .BinaryTreeBinaryTree.htemplate class BinarySearchTree : public BinaryTree public:BinarySearchTree( ) ;virtual BinarySearchTree( ) ;void InsertNode( BinaryTreeNode* root,/插入结点插入结点BinaryTreeNode* newpointer );void DeleteNode( BinaryTreeNode* pointer );/删除结点删除结点void DeleteNodeEx

38、( BinaryTreeNode* pointer );/删除结点删除结点(改进改进)/查找结点值为查找结点值为t的结点，找到则返回其指针，否则返回的结点，找到则返回其指针，否则返回NULLBinaryTreeNode* Search( BinaryTreeNode* root, const T& t );(2) (2) 二叉搜索树的实现二叉搜索树的实现(1)(1)：插入结点：插入结点n 往二叉搜索树里插入新结点，要保证插入后。将待插入结点的关键码值与树根的关键码值比较，若待插入的关键码值，则，；在子树里又与子树的根比较，如此进行下去，直到把新结点插入到二叉树里。二叉搜索树的二叉搜索树

39、的n 对于给定的关键码集合，为建立二叉搜索树，可以。template /插入结点插入结点(root为为BST的根结点的根结点)void BinarySearchTree:InsertNode( BinaryTreeNode* root,BinaryTreeNode* newpointer )BinaryTreeNode* pointer = NULL;/初始化初始化if(root = NULL )/空树空树/用指针用指针newpointer初始化二叉搜索树树根，赋值实现初始化二叉搜索树树根，赋值实现Initialize( newpointer ); return;else pointer =

40、root;while( 1 )if( newpointer-value=pointer-value )return;/相等则不用插入相等则不用插入else if( newpointer-valuevalue )/作为左子树作为左子树if( pointer-left=NULL )pointer-left = newpointer; return;else pointer = pointer-left;else/作为右子树作为右子树if( pointer-right=NULL )pointer-right = newpointer; return;else pointer = pointer-ri

41、ght;将待插入结点的关键码值与树根的关键码值比较，若待插入的关键码值，则，；在子树里又与子树的根比较，如此进行下去，直到把新结点插入到二叉树里。二叉搜索树的实现二叉搜索树的实现(2) (2) ：删除结点：删除结点n 从二叉搜索树里删除一个结点时，不能把以这个结点为根的子树都删除掉，并且还要。设p、p1、r是指针变量，则删除可以按如下规定进行：，则；，则在左子树里找按，然后。(即把p的右子树下降为r的右子树)BSTBST删除算法存在的删除算法存在的n 在前面的算法中，有可能。(1) 若结点p没有左子树，则用右子树的根代替被删除的结点p；(2) 若结点p有左子树，则在左子树里找按中序遍历的最后一

42、个结点r，并将其删除,由于此结点r没有右子树,因此删除此结点r只需用其左子树替代之, 然后。二叉树删除结点二叉树删除结点的实现的实现template /二叉搜索树删除结点的算法二叉搜索树删除结点的算法(改进改进)void BinarySearchTree:DeleteNodeEx( BinaryTreeNode* pointer )/如果带删除结点不存在如果带删除结点不存在,返回返回if( pointer = NULL )return;BinaryTreeNode * temppointer;/保存要替换上来的结点保存要替换上来的结点BinaryTreeNode * tempparent =

43、NULL;/保存要替换上来的结点的父结点保存要替换上来的结点的父结点/保存要删除结点的父结点保存要删除结点的父结点BinaryTreeNode * parent = Parent( pointer );/如果待删除结点的左子树为空如果待删除结点的左子树为空,就将它的右子树代替它即可就将它的右子树代替它即可if( pointer-leftchild() = NULL )temppointer=pointer-rightchild();else /当待删除结点左子树不为空当待删除结点左子树不为空,就在左子树中寻找最大结点替换待删除结点就在左子树中寻找最大结点替换待删除结点temppointer=p

44、ointer-leftchild(); while (temppointer-rightchild()!=NULL) tempparent=temppointer; temppointer=temppointer-rightchild();(1)若结点若结点p没有左子树，则用右子树没有左子树，则用右子树的根代替被删除的结点的根代替被删除的结点p(2)若结点若结点p有左子树，则在左子树里有左子树，则在左子树里找按中序遍历的最后一个结点找按中序遍历的最后一个结点r，并将其删除并将其删除,由于此结点由于此结点r没有右子没有右子树树,因此删除此结点因此删除此结点r只需用其左子只需用其左子树替代之树替代

45、之, 然后然后。/删除替换结点删除替换结点if( tempparent=NULL ) pointer-left = temppointer-leftchild();else tempparent-right = temppointer-leftchild();temppointer-left=pointer-leftchild();temppointer-right=pointer-rightchild();/用替换结点去替代真正的删除结点用替换结点去替代真正的删除结点if( parent=NULL ) root = temppointer;else if( parent-leftchild(

46、) = pointer ) parent-left = temppointer;else parent-right = temppointer;delete pointer; pointer = NULL;return;(1)若结点若结点p没有左子树，则用右子树没有左子树，则用右子树的根代替被删除的结点的根代替被删除的结点p(2)若结点若结点p有左子树，则在左子树里有左子树，则在左子树里找按中序遍历的最后一个结点找按中序遍历的最后一个结点r，并将其删除并将其删除,由于此结点由于此结点r没有右子没有右子树树,因此删除此结点因此删除此结点r只需用其左子只需用其左子树替代之树替代之, 然后然后。7

47、7 堆与优先队列堆与优先队列：是一种。：是一种，可以用堆来实现。1 1 最大堆和最小堆最大堆和最小堆(MinHeap)的定义：最小值堆是一个 ，它具有如下性质：12, 1 , 02212niKKKKiiiin 堆实质上，此完全二叉树的每个结点对应一个，根结点对应关键码。的特性在此完全二叉树里解释为：。n 根结点是完全二叉树中关键码值最小的结点，也就是堆中的最小元素。12, 1 , 02212niKKKKiiii堆的创建堆的创建( (如何建堆如何建堆) )筛选法筛选法(Floyd, 1964)(Floyd, 1964)n 首先(此时的完全二叉树并不具备堆的特性)。显然，所有 的结点 都没有子女结

48、点，因此以这样的 为根的子树都，然后从 的结点 开始，逐步把以 为根的子树排成堆，直到以为 根的树排成堆，就完成了建堆的过程。12niiK12niiKiK,322212nnnKKK0K考虑将以为根的子树排成堆时，以、为根的子树已经是堆，所以这时如果有和，则不必改变任何结点的位置，以为根的子树就已经是堆；否则要适当调整子树中的结点的位置以满足堆的定义。由于的左、右子树都已经是堆，根结点是堆中最小的结点，所以调整后的值必定是原来和中较小的一个。不妨假定较小，将与交换位置，这样调整后和，并且以为根的子树原来已经是堆，不必再做任何调整，只有以为根的子树由于的值发生变化(与交换了)，所以有可能不满足堆的

49、定义(但的左右子树都已经是堆)。这时可重复上述过程，考虑将以为根的子树排成堆。如此一层层递推下去，最多可能进行到树叶。注意：由于每步保证将子树最小的结点交换到子树的根结点，所以。它就像一样，把最小的关键码一层层地选择出来，因此这种构造最小堆的方法称为。此前的连续4幅图说明了对于关键码集合：用筛选法建堆的过程，其中n = 8， = 3，所以从K3 = 23开始。12n堆的操作堆的操作操作是。n 插入和删除操作都必须满足一个：，即插入结点或删除结点后，仍然满足堆的性质。n 堆的：将被插入的结点放在堆在最后位置，然后调整。堆的操作堆的操作n 从堆中删除一个结点，往往是删除根结点。(或)的为：用堆中最

50、后一个结点代替根结点(或其他被删除的结点)，然后调整。2 2 优先队列优先队列n 优先队列是这样一种数据结构。STLSTL中的优先队列中的优先队列n 包含：#include n 使用：using namespace std;的方法：priority_queue q1; /优先队列中的结点为整型数据; /优先队列中的结点为自定义类node对象：优先队列和队列的使用方法基本一致。但要注意，因为优先队列需要，因此，如果优先队列中的结点是自定义类对象，则在该类中，以实现结点的大小比较运算。8 Huffman8 Huffman编码树编码树n 电影风声中的镜头(1:47:00开始)摩尔斯编码。编码与摩尔斯编码编码与摩尔斯编码：将电报中的字符表示成通信系统可以识别的信号。：采用变长的来代表字符。n 影视剧中发电报：划（ ）和点（ ），或分别叫嗒（Dah）和滴（Dit），或长和短。加权平均编码长度最短的编码方案。：对，为8位。n 现已知在英语语言中26个字母(不区分大小写)出现的如下表所示