第5章 二叉树(1)

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

2、n 二叉树是一种，特殊在于： 每个结点最多(称为)，也就是说每个结点的 子女结点为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, k

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

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

5、满二叉树满二叉树 ：满足以下条件的二叉树，称为满二叉树(full binary tree)。 。即 。 或者：。 完全二叉树完全二叉树 ：满足以下条件的二叉树，称为完全二叉树(complete binary tree)。 。 或者：。 完全满二叉树完全满二叉树 ：满足以下条件的二叉树，称为完全满二叉树。 第i层有个结点。即。 ：。(见备注) 扩充二叉树扩充二叉树 ：当二叉树里出现了空的子树，就增加新的、特殊的结点 ；对于原来二叉树度数为1的分支结点，在它下面增加一个 空树叶；对于原来二叉树的树叶，在它下面增加两个空树叶；经过这 样的构造得到的二叉树称为。 n 在下图中，用表示空树叶。 n 8节

6、介绍的就是一种扩充二叉树。 ， ，（即树叶）。 ：从扩充二叉树的根到每个外部结点的路径长度之和。 在下图中，E = 2 + 3 + 3 + 3 + 4 + 4 + 4 + 4 + 4 + 4 = 35。 ：从扩充二叉树的根到每个内部结点的路径长度之和。 在下图中，I = 1 + 1 + 2 + 2 + 2 + 3 + 3 + 3 = 17。 n 扩充二叉树的： ：。 ：，其中n为扩充二叉树内部结点个数，也就是原二叉树 结点个数。 2 2 二叉树的主要性质二叉树的主要性质 ) 1(log2n ) 1(log2n 3 3 二叉树的抽象数据类型二叉树的抽象数据类型 n 二叉树的的。如： 初始化二叉树

7、； 把两棵二叉树的根结点作为一个新根结点的子结点来合并两棵二叉树。 等等。 n 二叉树的的。如： 访问某个结点的左子结点、右子结点、父结点，或者访问结点中存储的数 据。 n 二叉树的抽象数据类型包括结点类和二叉树类 。 ：二叉树的抽象数据类型：二叉树的抽象数据类型 提供： ：结点的数据域info。 ：丰富的构造函数、返回和设置左右子女结点指针、返回和设 置结点的数据域、判断结点是否为树叶等。 提供： ：二叉树根结点root。 ：丰富的构造函数、析构函数、判断二叉树是否为空树、返回 二叉树的根结点、获取当前结点的父结点、获取当前结点的左兄弟或右 兄弟、丰富的遍历函数等。 二叉树结点类二叉树结点类

8、BinaryTreeNodeBinaryTreeNode /声明声明BinaryTree类，因为在类，因为在BinaryTreeNode类中用到了标识符类中用到了标识符BinaryTree template class BinaryTree; template class BinaryTreeNode/二叉树结点的抽象数据类型二叉树结点的抽象数据类型 friend class BinaryTree;/声明二叉树类为结点类的友元类声明二叉树类为结点类的友元类,便于访问私有数据成员便于访问私有数据成员 private: T info;/二叉树结点数据域二叉树结点数据域 /实现时，可以补充结点的左子

9、结点、右子结点指针作为数据成员实现时，可以补充结点的左子结点、右子结点指针作为数据成员 public: BinaryTreeNode( );/缺省构造函数缺省构造函数 BinaryTreeNode( const T/给定数据的构造函数给定数据的构造函数 /给定了结点值和左右子树的构造函数给定了结点值和左右子树的构造函数 BinaryTreeNode( const T T value( ) const;/返回当前结点的数据返回当前结点的数据 BinaryTreeNode* leftchild( ) const;/返回当前结点的左子树指针返回当前结点的左子树指针 BinaryTreeNode* r

10、ightchild( ) const;/返回当前结点的右子树指针返回当前结点的右子树指针 void setLeftchild( BinaryTreeNode* L );/设置当前结点的左子树指针设置当前结点的左子树指针 void setRightchild( BinaryTreeNode* R );/设置当前结点的右子树指针设置当前结点的右子树指针 void setValue( const T/设置当前结点的数据域设置当前结点的数据域 bool isLeaf( ) const;/判定当前结点是否为叶结点，若是则返回判定当前结点是否为叶结点，若是则返回true BinaryTreeNode ;

11、二叉树类二叉树类BinaryTreeBinaryTree template class 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作为树的左子树，作为树的左子树，r

13、ightTree作为树的右子树作为树的右子树 /构造一棵新的二叉树构造一棵新的二叉树 void CreateTree( const T /以下是深度优先遍历二叉树以下是深度优先遍历二叉树 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, A, F, I, C(实际上是)。也可 以线

15、性化为其他顺序的序列。 两种重要的遍历方法两种重要的遍历方法 ： 本质上是一种，可以采用递归方式实现；但也可以采用非递 归方式实现。 ：是一种。 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

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

19、问当前结点访问当前结点 InOrder( root-rightchild() ); /访问右子树访问右子树 template/递归后序遍历二叉树或其子树递归后序遍历二叉树或其子树 void BinaryTree:PostOrder( BinaryTreeNode* root ) if( root!=NULL ) PostOrder( root-leftchild() );/访问左子树访问左子树 PostOrder( root-rightchild() );/访问右子树访问右子树 Visit(root-Value(); /访问当前结点访问当前结点 2 2 遍历二叉树遍历二叉树 n 栈是实现递归的

20、最常用的数据结构，所以对于递归定义的二叉树遍历 运算，最自然的是 ，。 n 使用栈的算法很简单。 请用示意图描述用非递归方式对下图所示的二叉树进行前序 遍历时栈的存储情况及入栈、出栈操作序列。 遇到一个结点， ，然后下 降去遍历它的左子树；遍历完它的左子 树后，继续 遍历。 演示：非递归前序遍历时栈的使用演示：非递归前序遍历时栈的使用 遇到一个结点，遇到一个结点，然后下降去遍，然后下降去遍 历它的左子树；遍历完它的左子树后，历它的左子树；遍历完它的左子树后，继续遍历。，继续遍历。 (P109)(P109)二叉树类二叉树类BinaryTreeBinaryTree实现：实现： template/非

21、递归前序遍历二叉树或其子树非递归前序遍历二叉树或其子树 void BinaryTree:PreOrderWithoutRecusion( BinaryTreeNode* root ) using std:stack; stack BinaryTreeNode* aStack; /栈中的结点为二叉树结点指针栈中的结点为二叉树结点指针 BinaryTreeNode* pointer = root;/保存输入参数保存输入参数 aStack.push(NULL); while( pointer ) Visit(pointer-Value(); /访问当前结点访问当前结点 if( pointer-rig

22、htchild()!=NULL ) aStack.push( pointer-rightchild() );/非空右孩子入栈非空右孩子入栈 if( pointer-leftchild()!=NULL ) pointer=pointer-leftchild() );/左路下降左路下降 else/左子树访问完毕，转向访问右子树左子树访问完毕，转向访问右子树 pointer = aStack.top( );/栈顶元素退栈栈顶元素退栈 aStack.pop( );/栈顶元素退栈栈顶元素退栈 /end of if /end of while 遇到一个结点，就， ，然后下降去遍历它的左子 树；遍历完它的左

23、子树后， 以输出结点的值作 为访问结点的操作 3 3 遍历二叉树遍历二叉树 n 使用栈的算法也很简单。 请用示意图描述用非递归方式对下图所示的二叉树进行中序 遍历时栈的存储情况及入栈、出栈操作序列。 遇到一个结点， 然后下降去遍历它的左子树；遍历完它 的左子树后， ，然后按它的右指针指示的地址再去 遍历该结点的右子树。 (P109)(P109)二叉树类二叉树类BinaryTreeBinaryTree实现：实现： template/非递归中序遍历二叉树或其子树非递归中序遍历二叉树或其子树 void BinaryTree:InOrderWithoutRecusion( BinaryTreeNode

24、* root ) using std:stack; stack BinaryTreeNode* aStack; /栈中的结点为二叉树结点指针栈中的结点为二叉树结点指针 BinaryTreeNode* pointer = root;/保存输入参数保存输入参数 while( !aStack.empty( ) | pointer ) if( pointer ) aStack.push( pointer );/当前结点地址入栈当前结点地址入栈 pointer = pointer-leftchild();/当前链接结构指向左孩子当前链接结构指向左孩子 else/左子树访问完毕，转向访问右子树左子树访问完

25、毕，转向访问右子树 pointer = aStack.top( ); aStack.pop();/栈顶元素退栈栈顶元素退栈 Visit(pointer-value();/访问当前结点访问当前结点 pointer = pointer-rightchild();/当前链接结构指向右孩子当前链接结构指向右孩子 /end of if /end of while 遇到一个结点， ，然后下降去遍历它的 左子树；遍历完它的左子树后 ， ，然后按它的右指针指示的地 址再去遍历该结点的右子树。 以输出结点的值作 为访问结点的操作 4 4 遍历二叉树遍历二叉树 n 后续遍历二叉树的非递归实现比中序遍历和前序遍历都

26、更复杂。 请用示意图描述用非递归方式对下图所示的二叉树进行后序 遍历时栈的存储情况及入栈、出栈操作序列。 遇到一个结点，去遍历 它的左子树； ，而是 要再按照它的右子树指针所指示的地址 去遍历该结点的右子树； 。 后序遍历二叉树的非递归实现方法后序遍历二叉树的非递归实现方法 n 在实现时，需要给栈中的每个结点加上一个，以 便当从栈顶取出一个结点时（ ），（ ）。 n 约定特征位为时，表示已进入该结点的左子树，将从左子树回来 ；特征位为时，表示已进入该结点的右子树，将从右子树回来 。可以。 enum Tags Left, Right ;/结点的标志结点的标志(枚举类型枚举类型)，Left为为0，

27、Right为为1 template class StackElement/栈中的结点栈中的结点(非递归后续遍历中用到的非递归后续遍历中用到的) public: BinaryTreeNode* pointer; Tags tag; ; (P110)(P110)二叉树类二叉树类BinaryTreeBinaryTree实现：实现： template/非递归后序遍历二叉树或其子树非递归后序遍历二叉树或其子树 void BinaryTree:PostOrderWithoutRecusion( BinaryTreeNode* root ) using std:stack; StackElement ele

28、ment; stack StackElement aStack; BinaryTreeNode* pointer; if （root= NULL) return;/空树即返回空树即返回 else pointer = root; 遇到一个结点，去遍历它的左 子树； ，而是要再按照它的右子树 指针所指示的地址去遍历该结点的右子树； 。 while( !aStack.empty() | pointer ) while( pointer!=NULL )/进入左子树，直到左子树中最下方的树叶进入左子树，直到左子树中最下方的树叶 element.pointer = pointer; element.tag

29、 = Left; aStack.push( element ); pointer = pointer-leftchild(); element = aStack.top( );/取出栈顶元素取出栈顶元素 aStack.pop( ); /弹出栈顶元素弹出栈顶元素 pointer = element.pointer; if (element.tag= Left) /如果从左子树回来如果从左子树回来 element.tag=Right; /则现在进入右子树则现在进入右子树 aStack.push( element ); pointer = pointer-rightchild(); else /如果

30、从右子树回来如果从右子树回来 Visit( pointer-value(); /访问当前结点访问当前结点 pointer=NULL; /end of while( true ) 遇到一个结点，去遍历 它的左子树； ，而是 要再按照它的右子树指针所指示的地址 去遍历该结点的右子树； 。 以输出结点的值作 为访问结点的操作 2 2 广度优先搜索二叉树广度优先搜索二叉树 ：从二叉树的第0层(即根结点)开始，自上而下 逐层遍历，在同一层中按从左到右的顺序对结点逐一访问。因此广度 优先遍历也称为。 n 在进行广度优先遍历时，对二叉树一层结点访问完成之后，要按照它 们的访问次序对各个结点的左子树和右子树按

31、顺序进行访问。因此在 进行广度优先遍历时，。 请用示意图描述用BFS对下 图所示的二叉树进行遍历时队列的 存储情况及入队列、出队列操作序 列。 (P112)(P112)二叉树类二叉树类BinaryTreeBinaryTree实现：实现： template /按层次遍历二叉树或其子树按层次遍历二叉树或其子树(即广度优先遍历即广度优先遍历) void BinaryTree:LevelOrder( BinaryTreeNode* root ) using std:queue; queue BinaryTreeNode* aQueue; BinaryTreeNode* pointer = root;

32、if( pointer )/非空树非空树 aQueue.push( pointer ); while( !aQueue.empty( ) ) pointer = aQueue.front( ); aQueue.pop( ); Visit( pointer-value();/访问当前结点访问当前结点 if( pointer-leftchild()!=NULL ) aQueue.push( pointer-leftchild() ); if( pointer-rightchild()!=NULL ) aQueue.push( pointer-rightchild() ); 二叉树的存储结构二叉树的

33、存储结构 n 二叉树是一种(指)。针对二叉树的各种应用 ，在存储器中有多种不同的表示二叉树的方法(指)，这些方 法都是(顺序、链式、索引、哈希)的组合应用。 1 1 用指针实现二叉树用指针实现二叉树 ：每个结点中除存储结点本身的数据外还有 。 ：在二叉链表的基础上，在每个结点中再增加一个 。有了指向父结点的指针，就给了的 能力。 2 2 用数组实现完全二叉树用数组实现完全二叉树 n 在完全二叉树中，所有结点可以按图(b)所示的蛇形方式排列。 n 因此，可以按存储完全二叉树中的结点： ()将完全二叉树中的每个结点按图(b)所示的顺序存 储在一片连续的存储空间中。 ()根据结点序号推断出父结点、左

34、 右子女结点、左右兄弟结点(见下页)。 二叉搜索树二叉搜索树 n 树形结构的一个重要应用是用来(详见后面的重要性质2)， 用适用于内存储器的一种重要的。 (BST，Binary Search Tree)，也称“二叉排序树”、“ 二叉查找树”、“二叉检索树”等。其定义如下： 或者是一颗； 或者是具有下列性质的二叉树：对于任何一个结点，设其值为K，则 ； ；而且它的左右子树也分别为 二叉搜索树。 说明：此处的“小于”和“大于”可以。 n 二叉搜索树的定义是一种的定义。 二叉搜索树例子二叉搜索树例子 n 设一棵二叉树的每个结点对应一个关键码，整棵二叉树各结点对应的 关键码组成一个。设一个关键码集合K

35、为： ， 则下图所示的二叉树就是一棵二叉搜索树。 二叉搜索树的重要性质二叉搜索树的重要性质(1)(1) n 二叉搜索树的：将各结点的值输出来，将得到 。将关键码集合组织成二叉搜索树，实际上 起了，按中序遍历二叉搜索树就能 得到排好的关键码序列。 n 例如，对下图所示的BST进行中序遍历后得到的序列为： 。 二叉搜索树的重要性质二叉搜索树的重要性质(2)(2) n 二叉搜索树的效率在于：从根结点 开始，在二叉搜索树中检索值K。 如果根结点储存的值为K，则检索结束。 如果K小于根结点的值，则。 如果K大于根结点的值，就。 n 这个过程一直持续到K被找到；或者在查找过程中， 如果遇上树叶仍没有发现K

36、，那么K就不在该二叉搜索树中。 n 设二叉搜索树的，则其高度的数量级为，因此在BST 中查找一个结点的时间复杂度为；如果n为210 10，则最多只需 比较10次就能找到结点或者得出不存在的结论。而其他查找算法一般 为。 ：二叉搜索树抽象数据类型：二叉搜索树抽象数据类型 n 本题中设计的二叉搜索类是 ，所以只需要为BST，主要是 、和的操作。 因为需要在中访问二叉树结点类 的，所以需要在BinaryTreeNode类中将 BinarySearchTree类，并在BinaryTreeNode类提前申明 BinarySearchTree类。方法如下： /提前声明提前声明BinaryTree类和类和B

37、inarySearchTree类类 template class BinaryTree; template class BinarySearchTree; template class BinaryTreeNode/二叉树结点的抽象数据类型二叉树结点的抽象数据类型 friend class BinaryTree; /声明二叉树类为结点类的友元类，便于访问私有数据声明二叉树类为结点类的友元类，便于访问私有数据 friend class BinarySearchTree;/声明二叉搜索树类为结点类的友元类声明二叉搜索树类为结点类的友元类 (1) (1) 二叉搜索树的声明二叉搜索树的声明 #incl

38、ude .BinaryTreeBinaryTree.h template class BinarySearchTree : public BinaryTree public: BinarySearchTree( ) ; virtual BinarySearchTree( ) ; void InsertNode( BinaryTreeNode* root,/插入结点插入结点 BinaryTreeNode* newpointer ); void DeleteNode( BinaryTreeNode* pointer );/删除结点删除结点 void DeleteNodeEx( BinaryTree

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

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

41、 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

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

43、被删除的结点p； (2) 若结点p有左子树，则在左子树里找 按中序遍历的最后一个结点r，并将其 删除,由于此结点r没有右子树,因此删 除此结点r只需用其左子树替代之, 然 后 。 二叉树删除结点二叉树删除结点的实现的实现 template /二叉搜索树删除结点的算法二叉搜索树删除结点的算法(改进改进) void BinarySearchTree:DeleteNodeEx( BinaryTreeNode* pointer ) /如果带删除结点不存在如果带删除结点不存在,返回返回 if( pointer = NULL ) return; BinaryTreeNode * temppointer;/

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

45、子树不为空,就在左子树中寻找最大结点替换待删除结点就在左子树中寻找最大结点替换待删除结点 temppointer=pointer-leftchild(); while (temppointer-rightchild()!=NULL) tempparent=temppointer; temppointer=temppointer-rightchild(); (1)若结点若结点p没有左子树，则用右子树没有左子树，则用右子树 的根代替被删除的结点的根代替被删除的结点p (2)若结点若结点p有左子树，则在左子树里有左子树，则在左子树里 找按中序遍历的最后一个结点找按中序遍历的最后一个结点r， 并将其删

46、除并将其删除,由于此结点由于此结点r没有右子没有右子 树树,因此删除此结点因此删除此结点r只需用其左子只需用其左子 树替代之树替代之, 然后然后 。 /删除替换结点删除替换结点 if( tempparent=NULL ) pointer-left = temppointer-leftchild(); else tempparent-right = temppointer-leftchild(); temppointer-left=pointer-leftchild(); temppointer-right=pointer-rightchild(); /用替换结点去替代真正的删除结点用替换结点去

47、替代真正的删除结点 if( parent=NULL ) root = temppointer; else if( parent-leftchild() = pointer ) parent-left = temppointer; else parent-right = temppointer; delete pointer; pointer = NULL; return; (1)若结点若结点p没有左子树，则用右子树没有左子树，则用右子树 的根代替被删除的结点的根代替被删除的结点p (2)若结点若结点p有左子树，则在左子树里有左子树，则在左子树里 找按中序遍历的最后一个结点找按中序遍历的最后一个

48、结点r， 并将其删除并将其删除,由于此结点由于此结点r没有右子没有右子 树树,因此删除此结点因此删除此结点r只需用其左子只需用其左子 树替代之树替代之, 然后然后 。 7 7 堆与优先队列堆与优先队列 ：是一种。 ：是一种，可以用堆来实现。 1 1 最大堆和最小堆最大堆和最小堆 (MinHeap)的定义：最小值堆是一个 ，它具有如下性质： 1 2 , 1 , 0 22 12 n i KK KK ii ii n 堆实质上，此完全二叉树的每个结点对 应一个，根结点对应关键码。 的特性在此完全二叉树里解释为： 。 n 根结点是完全二叉树中关键码值最小的结点，也就是堆中的最小元 素。 1 2 , 1

49、, 0 22 12 n i KK KK ii ii 堆的创建堆的创建( (如何建堆如何建堆) )筛选法筛选法(Floyd, 1964)(Floyd, 1964) n 首先(此时的完全 二叉树并不具备堆的特性)。 显然，所有 的结点 都没有子女结点，因此以这样 的 为根的子树都，然后从 的结点 开 始，逐步把以 为根的子树排成堆，直到 以为 根的树排成堆，就完成了建堆的过程。 1 2 n i i K 1 2 n i i K i K , 3 2 2 2 1 2 nnn KKK 0 K 考虑将以为根的子树排成堆时，以、为 根的子树已经是堆，所以这时如果有和，则 不必改变任何结点的位置，以为根的子树就

50、已经是堆；否 则要适当调整子树中的结点的位置以满足堆的定义。 由于的左、右子树都已经是堆，根结点是堆中最小的结点， 所以调整后的值必定是原来和中较小的一个。 不妨假定较小，将与交换位置，这样调整后 和，并且以为根的子树原来已经是堆， 不必再做任何调整，只有以为根的子树由于的值发 生变化(与交换了)，所以有可能不满足堆的定义(但的 左右子树都已经是堆)。 这时可重复上述过程，考虑将以为根的子树排成堆。如 此一层层递推下去，最多可能进行到树叶。 注意：由于每步保证将子树最小的结点交换到子树的根结点， 所以。 它就像一样，把最小的关键码一层层地选择出来，因此这 种构造最小堆的方法称为。 此前的连续4

51、幅图说明了对于关键码集合： 用筛选法建堆的过程，其中n = 8， = 3， 所以从K3 = 23开始。 1 2 n 堆的操作堆的操作 操作是。 n 插入和删除操作都必须满足一个：，即插 入结点或删除结点后，仍然满足堆的性质。 n 堆的：将被插入的结点放在堆在最后位置，然后调整。 堆的操作堆的操作 n 从堆中删除一个结点，往往是删除根结点。 (或)的为：用堆中最后一个结点代替根 结点(或其他被删除的结点)，然后调整。 2 2 优先队列优先队列 n 优先队列是这样一种数据结构。 。 STLSTL中的优先队列中的优先队列 n 包含：#include n 使用：using namespace std;

52、 的方法： priority_queue q1; /优先队列中的结点为整型数据 ; /优先队列中的结点为自定义类node对象 ：优先队列和队列的使用方法基本一致。但要注意，因为优 先队列需要，因此，如果优先队 列中的结点是自定义类对象，则在该类中， 以实现结点的大小比较运算。 8 Huffman8 Huffman编码树编码树 n 电影风声中的镜头(1:47:00开始)摩尔斯编码。 编码与摩尔斯编码编码与摩尔斯编码 ：将电报中的字符表示成通信系统可以识别的信号。 ：采用变长的来代表字符。 n 影视剧中发电报：划（ ）和点（ ），或分别叫嗒（Dah）和滴（Dit ），或长和短。 加权平均编码长度最短的编码方案。 ：对，为8位。 n 现已知在英语语言中26个字母(不区分大小写)出现的如下表所示 (指对大量英文文献进行统计分析得到的、每个字母出现的概率)。 字母概率