数据结构C++5.ppt

数据结构第第5 5章章 二叉树二叉树肖 正信息与智能系统系Data StructureData Structure5.1 定义及主要特性pp逻辑定义逻辑定义逻辑定义逻辑定义 递归定义递归定义递归定义递归定义:二叉树由结点的有限集合组成，这个集合二叉树由结点的有限集合组成，这个集合二叉树由结点的有限集合组成，这个集合二叉树由结点的有限集合组成，这个集合或者为空或者为空或者为空或者为空，或者，或者，或者，或者由一个由一个由一个由一个根结点根结点根结点根结点及两棵不相交的，分别称作这个根的及两棵不相交的，分别称作这个根的及两棵不相交的，分别称作这个根的及两棵不相交的，分别称作这个根的左子树左子树左子树左子树和和和和右子树右子树右子树右子树的的的的二叉树组成。二叉树组成。二叉树组成。二叉树组成。特点：特点：特点：特点：每个结点至多有二棵子树。每个结点至多有二棵子树。每个结点至多有二棵子树。每个结点至多有二棵子树。二叉树的子树有左、右之分，且其次序不能任意颠倒。二叉树的子树有左、右之分，且其次序不能任意颠倒。二叉树的子树有左、右之分，且其次序不能任意颠倒。二叉树的子树有左、右之分，且其次序不能任意颠倒。.Data StructureData Structure基本形态空二叉树A只有根结点的二叉树AB右子树为空AB左子树为空ABC左、右子树均非空.Data StructureData Structure二叉树的相关术语pp从一个结点到它的两个子结点都有从一个结点到它的两个子结点都有边边(edge)(edge)相连，这个结点称为它相连，这个结点称为它的子结点的的子结点的父结点父结点(parent)(parent)。pp如果一棵树的一串结点如果一棵树的一串结点n n1 1,n,n2 2,n,nk k有如下关系有如下关系:结点结点n ni i是是n ni+1i+1的的父结点父结点(1ik),(1ik),就把就把n n1 1,n,n2 2,n,nk k称为一条由称为一条由n n1 1至至n nk k的的路径路径(path)(path)。这条路经的这条路经的长度长度(length)(length)是是k-1(k-1(因为因为k k个结点是用个结点是用k-1k-1条边条边连接起来的连接起来的)。如果有一条路径从结点。如果有一条路径从结点R R至结点至结点M,M,那么那么R R就称为就称为M M的的祖先祖先(ancestor),(ancestor),而而M M称为称为R R的的子孙子孙(descendant)(descendant)。.Data StructureData Structure二叉树的相关术语pp结点结点M M的的深度深度(depth)(depth)就是从根结点到就是从根结点到M M的路径的长度。的路径的长度。树的高度树的高度(height)(height)等于最深的结点的深度等于最深的结点的深度+1+1。任何深度为。任何深度为d d的结点的层数的结点的层数(level)(level)都为都为d d。根结点深度为。根结点深度为0 0，层数也为，层数也为0 0。pp没有非空子树的结点称为没有非空子树的结点称为叶结点叶结点(leaf)(leaf)或终端结点。或终端结点。至少有一个非至少有一个非空子树的结点称为空子树的结点称为分支结点分支结点或或内部结点内部结点(internal node)(internal node)。.Data StructureData Structure二叉树的相关术语pp满二叉树满二叉树满二叉树满二叉树 如果一颗二叉树的如果一颗二叉树的任何结点，或者是树叶，或者恰有两个非空子任何结点，或者是树叶，或者恰有两个非空子女女的分支结点，则此二叉树称为满二叉树。的分支结点，则此二叉树称为满二叉树。(a)(a)满二叉树满二叉树(非完全二叉树非完全二叉树)(b)(b)完全二叉树完全二叉树(非满二叉树非满二叉树).Data StructureData Structure二叉树的相关术语pp完全二叉树完全二叉树完全二叉树完全二叉树 若一颗二叉树最多只有最下面的两层结点度数可以小于若一颗二叉树最多只有最下面的两层结点度数可以小于2 2，并，并且最下面一层的结点都集中在该层最左边的若干位置上，则称此二且最下面一层的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树。叉树为完全二叉树。自根结点起每一层从左至右地填充。一棵高度为自根结点起每一层从左至右地填充。一棵高度为d d的完全二叉的完全二叉除了除了d-1d-1层外，每一层都是满的。底层叶结点集中在左边的若干位层外，每一层都是满的。底层叶结点集中在左边的若干位置上。置上。.Data StructureData Structure完全二叉树1231145891213671014151234567123114589126710123456.Data StructureData Structure二叉树性质1.1.1.1.满二叉树定理：满二叉树定理：满二叉树定理：满二叉树定理：非空满二叉树树叶数等于其分支结点数加非空满二叉树树叶数等于其分支结点数加非空满二叉树树叶数等于其分支结点数加非空满二叉树树叶数等于其分支结点数加1 1 1 1。证明：设二叉树结点数为证明：设二叉树结点数为n n，叶结点数为，叶结点数为m m，分支结点数为，分支结点数为b b。有有n n（总结点数（总结点数=m=m（叶（叶)+b)+b（分支）（分支）(1)(1)每个分支，恰有两个子结点（满），故有每个分支，恰有两个子结点（满），故有2*b2*b条边一颗二叉树，除根结条边一颗二叉树，除根结点外，每个结点都恰有一条边联接父结点，故共有点外，每个结点都恰有一条边联接父结点，故共有n-1n-1条边。即条边。即n-n-1=2*b(2)1=2*b(2)由由(1)(2)(1)(2)得得n-1=m+b-1=2*bn-1=m+b-1=2*b，得出得出m(m(叶叶)=b)=b（分支）（分支）+1+1.Data StructureData Structure二叉树的性质2 2、满二叉树定理的推论满二叉树定理的推论满二叉树定理的推论满二叉树定理的推论:一棵非空二叉树空子树的数目等于其结点数一棵非空二叉树空子树的数目等于其结点数一棵非空二叉树空子树的数目等于其结点数一棵非空二叉树空子树的数目等于其结点数目加目加目加目加1 1 1 1。证明证明1 1：设二叉树设二叉树T T，将其所有空子树换成叶结点，将其所有空子树换成叶结点，把新的二叉树记把新的二叉树记为为TT。所有原来树所有原来树T T的结点现在是树的结点现在是树TT的分支结点。的分支结点。根据满二叉树定理，根据满二叉树定理，新添加的叶结点数目等于树新添加的叶结点数目等于树T T的结点数目加的结点数目加1 1，而每个新添加的叶结点对应树而每个新添加的叶结点对应树T T的一棵空子树的一棵空子树，因此树，因此树T T中空子中空子树的数目等于树树的数目等于树T T中结点数目加中结点数目加1 1。.Data StructureData Structure二叉树的性质证明证明2 2：根据定义，二叉树根据定义，二叉树T T中每个结点都有两个子结点指针（空或非空）中每个结点都有两个子结点指针（空或非空）。因此一个有因此一个有n n个结点的二叉树有个结点的二叉树有2n2n个子结点指针个子结点指针。除根结点外，共有除根结点外，共有n-1n-1个结点，它们都是由其父结点中相应指针指引而个结点，它们都是由其父结点中相应指针指引而来的，换句话说就有来的，换句话说就有n-1n-1个非空子结点指针个非空子结点指针。既然子结点指针数为既然子结点指针数为2n2n，则其中有，则其中有n+1n+1个为空个为空(指针指针)。.Data StructureData Structure二叉树的性质3.3.3.3.任何一颗二叉树，度为任何一颗二叉树，度为任何一颗二叉树，度为任何一颗二叉树，度为0 0 0 0的结点比度为的结点比度为的结点比度为的结点比度为2 2 2 2的结点多一个。的结点多一个。的结点多一个。的结点多一个。证明：证明：设有设有n n个结点的二叉树的度为个结点的二叉树的度为0 0、1 1、2 2的结点数分别为的结点数分别为=n0=n0，n1n1，n2n2，n=n0+n1+n2(n=n0+n1+n2(公式公式1)1)设边数为设边数为e e。因为除根以外，每个结点都有一条边进入，故。因为除根以外，每个结点都有一条边进入，故n=e+1n=e+1。由于这些边是有度为由于这些边是有度为1 1和和2 2的结点射出的，因此的结点射出的，因此e=n1+2*n2e=n1+2*n2，于是，于是n=e+1=n=e+1=n1+2*n2+1n1+2*n2+1（公式（公式2 2）因此由公式（因此由公式（1 1）（）（2 2）得）得 n0+n1+n2=n1+2*n2+1 n0+n1+n2=n1+2*n2+1 即即n0=n2+1n0=n2+1.Data StructureData Structure二叉树的性质4.4.4.4.二叉树的第二叉树的第二叉树的第二叉树的第i i i i层（根为第层（根为第层（根为第层（根为第0 0 0 0层）最多有层）最多有层）最多有层）最多有2 2 2 2i i i i个结点个结点个结点个结点5.5.5.5.高度为高度为高度为高度为k(k(k(k(深度为深度为深度为深度为k-1k-1k-1k-1。只有一个根结点的二叉树的高度为。只有一个根结点的二叉树的高度为。只有一个根结点的二叉树的高度为。只有一个根结点的二叉树的高度为1 1 1 1，深度为，深度为，深度为，深度为0)0)0)0)的二叉树至多有的二叉树至多有的二叉树至多有的二叉树至多有2 2 2 2k k k k-1-1-1-1个结点个结点个结点个结点6.6.6.6.有有有有n n n n个结点的完全二叉树的高度为个结点的完全二叉树的高度为个结点的完全二叉树的高度为个结点的完全二叉树的高度为 loglogloglog2 2 2 2n n n n +1(+1(+1(+1(深度为深度为深度为深度为 loglogloglog2 2 2 2n n n n ).Data StructureData Structure二叉树的抽象数据类型template class BinNode template class BinNode public:public:virtual BinNode*left()const=0;virtual BinNode*left()const=0;virtual BinNode*right()const=0;virtual BinNode*right()const=0;virtual Elem&val()=0;virtual Elem&val()=0;virtual void setVal(const Elem&)=0;virtual void setVal(const Elem&)=0;virtual bool isLeaf()=0;virtual bool isLeaf()=0;.Data StructureData Structure5.2 周游二叉树pp周游：周游：周游：周游：系统地访问数据结构中的结点。每个结点都正好被访问到一系统地访问数据结构中的结点。每个结点都正好被访问到一系统地访问数据结构中的结点。每个结点都正好被访问到一系统地访问数据结构中的结点。每个结点都正好被访问到一次。次。次。次。pp方法：方法：方法：方法：前序周游前序周游前序周游前序周游(preorder traversal)(preorder traversal)：访问根结点；前序周游左子树：访问根结点；前序周游左子树;前前序周游右子树。序周游右子树。中序周游中序周游中序周游中序周游(inorder traversal)(inorder traversal)：中序周游左子树：中序周游左子树;访问根结点访问根结点;中序中序周游右子树。周游右子树。后序周游后序周游后序周游后序周游(postorder traversal)(postorder traversal)：后序周游左子树：后序周游左子树;后序周游右子后序周游右子树树;访问根结点。访问根结点。.Data StructureData Structure先序遍历ADBCD L RAD L RD L RBDCD L R先序遍历序列：先序遍历序列：A B D CA B D C.Data StructureData Structure中序遍历ADBCL D RBL D RL D RADCL D R中序遍历序列：中序遍历序列：B D A CB D A C.Data StructureData Structure后序遍历ADBC L R DL R DL R DADCL R D后序遍历序列：后序遍历序列：D B C A D B C AB.Data StructureData Structure举例-+/a*b-efcd中序遍历：后序遍历：层次遍历：-+a*b-c d/e f-+a*b-cd/ef-+a*b-c d/e f-+a*b-c d/e f先序遍历：.Data StructureData Structure前序遍历算法template template void preorder(BinNode*subroot)void preorder(BinNode*subroot)if(subroot=NULL)return;if(subroot=NULL)return;visit(subroot);visit(subroot);preorder(subroot-leftchild();preorder(subroot-leftchild();preorder(subroot-rightchild();preorder(subroot-rightchild();.Data StructureData Structure遍历算法应用计算二叉树的结点数：计算二叉树的结点数：计算二叉树的结点数：计算二叉树的结点数：template template int count(BinNode*subroot)int count(BinNode*subroot)if(subroot=NULL)return 0;if(subroot=NULL)return 0;/visit(subroot);/visit(subroot);return 1+count(subroot-left()+count(subroot-right();return 1+count(subroot-left()+count(subroot-right();.Data StructureData Structure5.3 二叉树的实现5.3.1 5.3.1 5.3.1 5.3.1 使用指针实现二叉树使用指针实现二叉树使用指针实现二叉树使用指针实现二叉树pp二叉链表二叉链表二叉链表二叉链表(最常用最常用最常用最常用)class BinNodePtr class BinNodePtr class BinNodePtr class BinNodePtr private:private:private:private:Elem it;Elem it;Elem it;Elem it;BinNodePtr*BinNodePtr*BinNodePtr*BinNodePtr*lclclclc;BinNodePtr*BinNodePtr*BinNodePtr*BinNodePtr*rcrcrcrc;好处：运算方便好处：运算方便好处：运算方便好处：运算方便;问题：空指针太多问题：空指针太多问题：空指针太多问题：空指针太多.Data StructureData Structure二叉树的存储pp带父指针的三重链表带父指针的三重链表带父指针的三重链表带父指针的三重链表在某些经常要回溯到父结点的应用中很有效。在某些经常要回溯到父结点的应用中很有效。在某些经常要回溯到父结点的应用中很有效。在某些经常要回溯到父结点的应用中很有效。class BinNodePtr class BinNodePtr class BinNodePtr class BinNodePtr private:private:private:private:Elem it;Elem it;Elem it;Elem it;BinNodePtr*BinNodePtr*BinNodePtr*BinNodePtr*lclclclc;BinNodePtr*BinNodePtr*BinNodePtr*BinNodePtr*rcrcrcrc;BinNodePtr*BinNodePtr*BinNodePtr*BinNodePtr*fatherfatherfatherfather;.Data StructureData Structure二叉树存储（区别叶和分支）pp叶结点和分支结点的分别实现叶结点和分支结点的分别实现叶结点和分支结点的分别实现叶结点和分支结点的分别实现 当叶结点和分支结点差别较大，或出于应用要求而需要区分叶结当叶结点和分支结点差别较大，或出于应用要求而需要区分叶结当叶结点和分支结点差别较大，或出于应用要求而需要区分叶结当叶结点和分支结点差别较大，或出于应用要求而需要区分叶结点和分支结点时点和分支结点时点和分支结点时点和分支结点时 (a)(a)(a)(a)联合联合联合联合 (b)(b)(b)(b)类继承和虚函数类继承和虚函数类继承和虚函数类继承和虚函数.Data StructureData Structure表达式树：联合实现方法class VarBinNode class VarBinNode public:public:Nodetype Nodetype mytypemytype;unionunion struct struct VarBinNode*left;VarBinNode*left;VarBinNode*right;VarBinNode*right;Operator opx;Operator opx;intl;intl;Operand var;Operand var;.Data StructureData Structure用不同的类实现分支和叶class VarBinNode class VarBinNode public:public:virtual virtual bool isLeaf isLeaf()=0;bool isLeaf isLeaf()=0;class LeafNode:public VarBinNode class LeafNode:public VarBinNode private:private:Operand var;Operand var;public:public:LeafNode(const Operand&val)var=val;LeafNode(const Operand&val)var=val;bool isLeaf bool isLeaf()return true;()return true;Operand Operand value()value()return var;return var;.Data StructureData Structure不同类实现的分支结点Class IntlNode:public VarBinNodeClass IntlNode:public VarBinNodeprivate:private:VarBinNode*VarBinNode*leftleft;VarBinNode*VarBinNode*rightright;Operator Operator opxopx;public:public:IntlNode(const Operator&op,VarBinNode*l,VarBinNode*r)opx=op;left=l;IntlNode(const Operator&op,VarBinNode*l,VarBinNode*r)opx=op;left=l;right=r;right=r;isLeaf()return false isLeaf()return false VarBinNode*VarBinNode*leftchild()leftchild()return left;return left;VarBinNode*VarBinNode*rightchild()rightchild()return right;return right;Operator Operator value()value()return opx;return opx;.Data StructureData Structure5.3.2 结构性空间开销分析根据满二叉树定理：一半的指针是空的根据满二叉树定理：一半的指针是空的根据满二叉树定理：一半的指针是空的根据满二叉树定理：一半的指针是空的 如果只有叶结点存储数据，分支结点为内部结构结点（如如果只有叶结点存储数据，分支结点为内部结构结点（如如果只有叶结点存储数据，分支结点为内部结构结点（如如果只有叶结点存储数据，分支结点为内部结构结点（如HuffmanHuffmanHuffmanHuffman树）树）树）树），则取决于二叉树是否满（越满存储效率越高），则取决于二叉树是否满（越满存储效率越高），则取决于二叉树是否满（越满存储效率越高），则取决于二叉树是否满（越满存储效率越高）对于简单的每个结点存两个指针、一个数据域对于简单的每个结点存两个指针、一个数据域对于简单的每个结点存两个指针、一个数据域对于简单的每个结点存两个指针、一个数据域 总空间总空间总空间总空间(2(2(2(2p p p p+d d d d)n n n n 结构性：结构性：结构性：结构性：2 2 2 2pnpnpnpn 如果如果如果如果p p p p=d d d d，则，则，则，则2 2 2 2p p p p/(2/(2/(2/(2p p p p+d d d d)=2/3)=2/3)=2/3)=2/3.Data StructureData Structure结构性空间开销分析去掉满二叉树叶结点中的指针去掉满二叉树叶结点中的指针去掉满二叉树叶结点中的指针去掉满二叉树叶结点中的指针则结构性开销为则结构性开销为则结构性开销为则结构性开销为1/21/21/21/2（假设（假设（假设（假设p p p p=d d d d）如果只在叶结点存数据，则结构性开销为如果只在叶结点存数据，则结构性开销为如果只在叶结点存数据，则结构性开销为如果只在叶结点存数据，则结构性开销为2 2 2 2pnpnpnpn/(2/(2/(2/(2pn pn pn pn+d(n+1)d(n+1)d(n+1)d(n+1)2/3)2/3)2/3)2/3（假设（假设（假设（假设p p p p=d d d d）注意：区分叶结点和分支结点又需要额外的算法时间。注意：区分叶结点和分支结点又需要额外的算法时间。注意：区分叶结点和分支结点又需要额外的算法时间。注意：区分叶结点和分支结点又需要额外的算法时间。.Data StructureData Structure5.3.3 使用数组实现完全二叉树完全二叉树的顺序存储完全二叉树的顺序存储完全二叉树的顺序存储完全二叉树的顺序存储ABCDEFGHIJKLABCDEFGHIJKLABCDEFGHIJKLABCDEFGHIJKL按照二叉树的按照二叉树的按照二叉树的按照二叉树的层次周游层次周游层次周游层次周游次序存储在一个数组中次序存储在一个数组中次序存储在一个数组中次序存储在一个数组中简单，省空间简单，省空间简单，省空间简单，省空间.Data StructureData Structure顺序存储pp非完全二叉树在置空值而转换为完全二叉树存储非完全二叉树在置空值而转换为完全二叉树存储非完全二叉树在置空值而转换为完全二叉树存储非完全二叉树在置空值而转换为完全二叉树存储 CEDJFX/K/G/I/LCEDJFX/K/G/I/LCEDJFX/K/G/I/LCEDJFX/K/G/I/L.Data StructureData Structure完全二叉树的下标对应关系000000000000.Data StructureData Structure完全二叉树的下标公式公式中公式中公式中公式中r r r r表示结点的索引，表示结点的索引，表示结点的索引，表示结点的索引，n n n n表示二叉树结点总数。表示二叉树结点总数。表示二叉树结点总数。表示二叉树结点总数。Parent(r)=(r-1)/2Parent(r)=(r-1)/2Parent(r)=(r-1)/2Parent(r)=(r-1)/2，当，当，当，当0rn0rn0rn0rn时。时。时。时。Leftchild(r)=2r+1Leftchild(r)=2r+1Leftchild(r)=2r+1Leftchild(r)=2r+1，当，当，当，当2r+1n2r+1n2r+1n2r+1n时。时。时。时。Rightchild(r)=2r+2 Rightchild(r)=2r+2 Rightchild(r)=2r+2 Rightchild(r)=2r+2，当，当，当，当2r+2 n 2r+2 n 2r+2 n 2r+2 n 时。时。时。时。Leftsibling(r)=r-1Leftsibling(r)=r-1Leftsibling(r)=r-1Leftsibling(r)=r-1，当，当，当，当r r r r为偶数且为偶数且为偶数且为偶数且0=r=n-10=r=n-10=r=n-10=r=n-1。Rightsibling(r)=r+1Rightsibling(r)=r+1Rightsibling(r)=r+1Rightsibling(r)=r+1，当，当，当，当r r r r为奇数且为奇数且为奇数且为奇数且r+1nr+1nr+1nr+1n。.Data StructureData Structure5.4 二叉查找树定义：定义：定义：定义：二叉检索树或者为空二叉检索树或者为空二叉检索树或者为空二叉检索树或者为空,或者是满足下列条件的非空二叉树或者是满足下列条件的非空二叉树或者是满足下列条件的非空二叉树或者是满足下列条件的非空二叉树:(1 (1 (1 (1若它的左子树非空若它的左子树非空若它的左子树非空若它的左子树非空,则左子树上所有结点的值均小于根结点的值则左子树上所有结点的值均小于根结点的值则左子树上所有结点的值均小于根结点的值则左子树上所有结点的值均小于根结点的值;(2)(2)(2)(2)它的右子树非空它的右子树非空它的右子树非空它的右子树非空,则右子树上所有结点的值均大于或等于根结则右子树上所有结点的值均大于或等于根结则右子树上所有结点的值均大于或等于根结则右子树上所有结点的值均大于或等于根结点的值点的值点的值点的值;(3)(3)(3)(3)左右子树本身又各是一棵二叉检索树。左右子树本身又各是一棵二叉检索树。左右子树本身又各是一棵二叉检索树。左右子树本身又各是一棵二叉检索树。性质性质性质性质:按照按照按照按照中序周游中序周游中序周游中序周游将各结点打印出来，将得到按照将各结点打印出来，将得到按照将各结点打印出来，将得到按照将各结点打印出来，将得到按照由小到大由小到大由小到大由小到大的排列。的排列。的排列。的排列。.Data StructureData StructureBST图示.Data StructureData Structure检索二叉检索树的效率就在于只需检索二个子树之一。从根结点开始，在二叉检二叉检索树的效率就在于只需检索二个子树之一。从根结点开始，在二叉检二叉检索树的效率就在于只需检索二个子树之一。从根结点开始，在二叉检二叉检索树的效率就在于只需检索二个子树之一。从根结点开始，在二叉检索树中检索值索树中检索值索树中检索值索树中检索值K K K K。如果根结点储存的值为如果根结点储存的值为如果根结点储存的值为如果根结点储存的值为K K K K，则检索结束。，则检索结束。，则检索结束。，则检索结束。如果如果如果如果K K K K小于根结点的值，则只需检索左子树小于根结点的值，则只需检索左子树小于根结点的值，则只需检索左子树小于根结点的值，则只需检索左子树 如果如果如果如果K K K K大于根结点的值大于根结点的值大于根结点的值大于根结点的值,就只检索右子树就只检索右子树就只检索右子树就只检索右子树 这个过程一直持续到这个过程一直持续到这个过程一直持续到这个过程一直持续到K K K K被找到或者我们遇上了一个树叶。被找到或者我们遇上了一个树叶。被找到或者我们遇上了一个树叶。被找到或者我们遇上了一个树叶。如果遇上树叶仍没有发现如果遇上树叶仍没有发现如果遇上树叶仍没有发现如果遇上树叶仍没有发现K K K K，那么，那么，那么，那么K K K K就不在该二叉检索树中。就不在该二叉检索树中。就不在该二叉检索树中。就不在该二叉检索树中。.Data StructureData Structure二叉检索树类的定义class BST class BST private:private:BinNode*root;BinNode*root;int nodecount;int nodecount;void clearhelp(BinNode*);void clearhelp(BinNode*);BinNode*inserthelp(BinNode*,const Elem&);BinNode*inserthelp(BinNode*,const Elem&);BinNode*deletemin(BinNode*,BinNode*&);BinNode*deletemin(BinNode*,BinNode*&);BinNode*removehelp(BinNode*,const Key&,BinNode*&);BinNode*removehelp(BinNode*,const Key&,BinNode*&);bool findhelp(BinNode*,const Key&,Elem&)const;bool findhelp(BinNode*,const Key&,Elem&)const;void printhelp(BinNode*,int)const;void printhelp(BinNode*,int)const;.Data StructureData Structure二叉检索树类的定义public:public:BST()root=NULL;nodecount=0;BST()root=NULL;nodecount=0;BST()clearhelp(root);BST()clearhelp(root);void clear()clearhelp(root);root=NULL;nodecount=0;void clear()clearhelp(root);root=NULL;nodecount=0;void insert(const Elem&e)root=inserthelp(root,e);void insert(const Elem&e)root=inserthelp(root,e);nodecount+;return true;nodecount+;return true;void remove(const Key&K,Elem&e)void remove(const Key&K,Elem&e)BinNode*t=NULL;root=removehelp(root,K,t);BinNode*t=NULL;root=removehelp(root,K,t);if(t=NULL)return false;if(t=NULL)return false;e=t-val();nodecount-;delete t;return true;e=t-val();nodecount-;delete t;return true;bool find(const Key&K,Elem&e)const bool find(const Key&K,Elem&e)const return findhelp(root,K,e);return findhelp(root,K,e);bool isEmpty()const return root=NULL;bool isEmpty()const return root=NULL;void print()const void print()const if(root=NULL)cout The BST is empty.n;if(root=NULL)cout The BST is empty.n;else printhelp(root,0);else printhelp(root,0);.Data StructureData Structure检索template class Key,class Elem,template class KEComp,class EECompbool BST:bool BST:findhelp(BinNode*subroot,findhelp(BinNode*subroot,const Key&K,Elem&e)const const Key&K,Elem&e)const if(subroot=NULL)return false;if(subroot=NULL)return false;else if(KEComp:lt(K,subroot-val()else if(KEComp:lt(K,subroot-val()return findhelp(subroot-left(),K,e);return findhelp(subroot-left(),K,e);else if(KEComp:gt(K,subroot-val()else if(KEComp:gt(K,subroot-val()return findhelp(subroot-right(),K,e);return findhelp(subroot-right(),K,e);else e=subroot-val();return true;else e=subroot-val();return true;.Data StructureData Structure插入template class Key,class Elem,template class KEComp,class EECompBinNode*BST:BinNode*BST:inserthelp(BinNode*subroot,inserthelp(BinNode*subroot,const Elem&val)const Elem&val)if(subroot=NULL)/Empty:create node if(subroot=NULL)/Empty:create node return new BinNodePtr(val,NULL,NULL);return new BinNodePtr(val,NULL,NULL);if(EEComp:lt(val,subroot-val()if(EEComp:lt(val,subroot-val()subroot-setLeft(inserthelp(subroot-left(),val);subroot-setLeft(inserthelp(subroot-left(),val);else else subroot-setRight(inserthelp(subroot-right(),val);subroot-setRight(inserthelp(subroot-right(),val);/Return subtree with node inserted/Return subtree with node inserted re