数据结构C++PPT5

数据结构第5章二叉树肖正信息与智能系统系[e-mail]25.1定义及主要特性逻辑定义递归定义:二叉树由结点的有限集合组成，这个集合或者为空，或者由一个根结点及两棵不相交的，分别称作这个根的左子树和右子树的二叉树组成。特点：每个结点至多有二棵子树。二叉树的子树有左、右之分，且其次序不能任意颠倒。DataStructure3基本形态空二叉树A只有根结点的二叉树AB右子树为空AB左子树为空ABC左、右子树均非空DataStructure4二叉树的相关术语从一个结点到它的两个子结点都有边(edge)相连，这个结点称为它的子结点的父结点(parent)。如果一棵树的一串结点n1,n2,…,nk有如下关系:结点ni是ni+1的父结点(1≤ik),就把n1,n2,…,nk称为一条由n1至nk的路径(path)。这条路经的长度(length)是k-1(因为k个结点是用k-1条边连接起来的)。如果有一条路径从结点R至结点M,那么R就称为M的祖先(ancestor),而M称为R的子孙(descendant)。DataStructure5二叉树的相关术语结点M的深度(depth)就是从根结点到M的路径的长度。树的高度(height)等于最深的结点的深度+1。任何深度为d的结点的层数(level)都为d。根结点深度为0，层数也为0。没有非空子树的结点称为叶结点(leaf)或终端结点。至少有一个非空子树的结点称为分支结点或内部结点(internalnode)。DataStructure6二叉树的相关术语满二叉树如果一颗二叉树的任何结点，或者是树叶，或者恰有两个非空子女的分支结点，则此二叉树称为满二叉树。(a)满二叉树(非完全二叉树)(b)完全二叉树(非满二叉树)DataStructure7二叉树的相关术语完全二叉树若一颗二叉树最多只有最下面的两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树。自根结点起每一层从左至右地填充。一棵高度为d的完全二叉除了d-1层外，每一层都是满的。底层叶结点集中在左边的若干位置上。DataStructure8完全二叉树1231145891213671014151234567123114589126710123456DataStructure9二叉树性质1.满二叉树定理：非空满二叉树树叶数等于其分支结点数加1。证明：设二叉树结点数为n，叶结点数为m，分支结点数为b。有n（总结点数=m（叶)+b（分支）(1)∵每个分支，恰有两个子结点（满），故有2*b条边一颗二叉树，除根结点外，每个结点都恰有一条边联接父结点，故共有n-1条边。即n-1=2*b(2)∴由(1)(2)得n-1=m+b-1=2*b，得出m(叶)=b（分支）+1DataStructure10二叉树的性质2、满二叉树定理的推论:一棵非空二叉树空子树的数目等于其结点数目加1。证明1：设二叉树T，将其所有空子树换成叶结点，把新的二叉树记为T‘。所有原来树T的结点现在是树T’的分支结点。根据满二叉树定理，新添加的叶结点数目等于树T的结点数目加1，而每个新添加的叶结点对应树T的一棵空子树，因此树T中空子树的数目等于树T中结点数目加1。DataStructure11二叉树的性质证明2：根据定义，二叉树T中每个结点都有两个子结点指针（空或非空）。因此一个有n个结点的二叉树有2n个子结点指针。除根结点外，共有n-1个结点，它们都是由其父结点中相应指针指引而来的，换句话说就有n-1个非空子结点指针。既然子结点指针数为2n，则其中有n+1个为空(指针)。DataStructure12二叉树的性质3.任何一颗二叉树，度为0的结点比度为2的结点多一个。证明：设有n个结点的二叉树的度为0、1、2的结点数分别为=n0，n1，n2，n=n0+n1+n2(公式1)设边数为e。因为除根以外，每个结点都有一条边进入，故n=e+1。由于这些边是有度为1和2的结点射出的，因此e=n1+2*n2，于是n=e+1=n1+2*n2+1（公式2）因此由公式（1）（2）得n0+n1+n2=n1+2*n2+1即n0=n2+1DataStructure13二叉树的性质4.二叉树的第i层（根为第0层）最多有2i个结点5.高度为k(深度为k-1。只有一个根结点的二叉树的高度为1，深度为0)的二叉树至多有2k-1个结点6.有n个结点的完全二叉树的高度为log2n+1(深度为log2n)DataStructure14二叉树的抽象数据类型templateclassElemclassBinNode{public:virtualBinNode*left()const=0;virtualBinNode*right()const=0;virtualElem&val()=0;virtualvoidsetVal(constElem&)=0;virtualboolisLeaf()=0;};DataStructure155.2周游二叉树周游：系统地访问数据结构中的结点。每个结点都正好被访问到一次。方法：前序周游(preordertraversal)：访问根结点；前序周游左子树;前序周游右子树。中序周游(inordertraversal)：中序周游左子树;访问根结点;中序周游右子树。后序周游(postordertraversal)：后序周游左子树;后序周游右子树;访问根结点。DataStructure16先序遍历ADBCDLRADLRDLRBDCDLR先序遍历序列：ABDCDataStructure17中序遍历ADBCLDRBLDRLDRADCLDR中序遍历序列：BDACDataStructure18后序遍历ADBCLRDLRDLRDADCLRD后序遍历序列：DBCABDataStructure19举例-+/a*b-efcd中序遍历：后序遍历：层次遍历：-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef先序遍历：DataStructure20前序遍历算法templateclassElemvoidpreorder(BinNodeElem*subroot){if(subroot==NULL)return;visit(subroot);preorder(subroot-leftchild());preorder(subroot-rightchild());}DataStructure21遍历算法应用计算二叉树的结点数：templateclassElemintcount(BinNodeElem*subroot){if(subroot==NULL)return0;//visit(subroot);return1+count(subroot-left())+count(subroot-right());}DataStructure225.3二叉树的实现5.3.1使用指针实现二叉树二叉链表(最常用)classBinNodePtr{private:Elemit;BinNodePtr*lc;BinNodePtr*rc;…};好处：运算方便;问题：空指针太多DataStructure23二叉树的存储带父指针的三重链表在某些经常要回溯到父结点的应用中很有效。classBinNodePtr{private:Elemit;BinNodePtr*lc;BinNodePtr*rc;BinNodePtr*father;…};DataStructure24二叉树存储（区别叶和分支）叶结点和分支结点的分别实现当叶结点和分支结点差别较大，或出于应用要求而需要区分叶结点和分支结点时–(a)联合–(b)类继承和虚函数DataStructure25表达式树：联合实现方法classVarBinNode{public:Nodetypemytype;union{struct{VarBinNode*left;VarBinNode*right;Operatoropx;}intl;Operandvar;};…}DataStructure26用不同的类实现分支和叶classVarBinNode{public:virtualboolisLeafisLeaf()=0;};classLeafNode:publicVarBinNode{private:Operandvar;public:LeafNode(constOperand&val){var=val;}boolisLeaf(){returntrue;}Operandvalue(){returnvar;}};DataStructure27不同类实现的分支结点ClassIntlNode:publicVarBinNode{private:VarBinNode*left;VarBinNode*right;Operatoropx;public:IntlNode(constOperator&op,VarBinNode*l,VarBinNode*r){opx=op;left=l;right=r;}isLeaf(){returnfalse}VarBinNode*leftchild(){returnleft;}VarBinNode*rightchild(){returnright;}Operatorvalue(){returnopx;}};DataStructure285.3.2结构性空间开销分析根据满二叉树定理：一半的指针是空的如果只有叶结点存储数据，分支结点为内部结构结点（如Huffman树），则取决于二叉树是否满（越满存储效率越高）对于简单的每个结点存两个指针、一个数据域–总空间(2p+d)n–结构性：2pn–如果p=d，则2p/(2p+d)=2/3DataStructure29结构性空间开销分析去掉满二叉树叶结点中的指针则结构性开销为1/2（假设p=d）如果只在叶结点存数据，则结构性开销为2pn/(2pn+d(n+1))2/3（假设p=d）注意：区分叶结点和分支结点又需要额外的算法时间。(2)2(2)2nppnpdpdnDataStructure305.3.3使用数组实现完全二叉树完全二叉树的顺序存储ABCDEFGHIJKL按照二叉树的层次周游次序存储在一个数组中简单，省空间DataStructure31顺序存储非完全二叉树在置空值而转换为完全二叉树存储CEDJFX//K/G/I/////LDataStructure32完全二叉树的下标对应关系Position01234567891011Parent--00112233445LeftChild1357911------------RightChild246810--------------LeftSibling----1--3--5--7--9--RightSibling--2--4--6--8--10----000000000000DataStructure33完全二叉树的下标公式公式中r表示结点的索引，n表示二叉树结点总数。Parent(r)=(r-1)/2，当0rn时。Leftchild(r)=2r+1，当2r+1n时。Rightchild(r)=2r+2，当2r+2n时。Leftsibling(r)=r-1，当r为偶数且0=r=n-1。Rightsibling(r)=r+1，当r为奇数且r+1n。DataStructure345.4二叉查找树定义：二叉检索树或者为空,或者是满足下列条件的非空二叉树:(1若它的左子树非空,则左子树上所有结点的值均小于根结点的值;(2)它的右子树非空,则右子树上所有结点的值均大于或等于根结点的值;(3)左右子树本身又各是一棵二叉检索树。性质:按照中序周游将各结点打印出来，将得到按照由小到大的排列。DataStructure35BST图示DataStructure36检索二叉检索树的效率就在于只需检索二个子树之一。从根结点开始，在二叉检索