数据结构与算法分析lecture6(二叉树)

BinaryTrees(二叉树)TaoLiangCollegeofsoftwareSiChuanUniversity1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A．线性结构B．非线性结构A顺序存储B链式存储线性表栈队树形结构图形结构数据结构的三个主要问题1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A．线性结构B．非线性结构A顺序存储B链式存储线性表栈队树形结构图形结构数据结构的三个主要问题线性结构A,B,C,·······，X,Y,Z学生成绩表86胡孝臣986110395刘忠赏9861107100张卓9861109成绩姓名学号线性表——结点间是以线性关系联结1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A．线性结构B．非线性结构A顺序存储B链式存储线性表栈队列树形结构图形结构数据结构的三个主要问题树形结构全校学生档案管理的组织方式ABCDEFGH树形结构——结点间具有分层次的连接关系HBCDEFGABinaryTreeDefinitionsandPropertiesBinaryTreeTraversalsBinaryTreeNodeImplementionsBinarySearchTreesHeapsandPriorityQueuesHuffmanCodingTreesDefinitionsandProperties二叉树的定义：由结点(node)的有限集合组成，这个集合或者为空(empty)，或由一个根结点(root)和两棵分别称为根的左子树(leftsubtree)和右子树(rightsubtree)的互不相交的二叉数组成。ADHIT3JMBELKT1F介绍几个概念：结点（Node）：树中的元素，包含数据项及若干指向其子树的分支。结点的度（Degree）：结点拥有的子树数。结点的层次：从根结点开始算起，根为第0层。叶子（Leaf）：度为零的结点，也称端结点。孩子（Child）：结点子树的根称为该结点的孩子结点。兄弟（Sibling）：同一双亲的孩子。双亲（Parent）：孩子结点的上层结点，称为这些结点的双亲。结点的深度（Depth)：从根结点到该结点的路径的长度。树的高度（Height）：等于最深结点的深度加1。ACHMBELKDABABTwodifferenttreesAB空AB空满二叉树(fullbinarytree)的每一个结点或者是一个分支结点，并恰有两个非空子结点；或者是叶结点.完全二叉树(completebinarytree)有严格的形状要求:从根结点起每一层从左到右填充.一棵高度为d的完全二叉树除了d-1层以外,每一层都是满的.底层叶结点集中在左边的若干位置上.Thistreeisfull(butnotcomplete)Thistreeiscomplete(butnotfull)TheFullBinaryTreeTheorem(满二叉树定理)Theorem5.1FullBinaryTreeTheorem:Thenumberofleavesinanon-emptyfullbinarytreeisonemorethanthenumberofinternalnodes.Theorem5.2Thenumberofemptysubtreesinanon-emptybinarytreeisonemorethanofnodesinthetree.ADHIT3JMBELKT1FABinaryTreeNodeADTClearlythereareactivitiesthatrelatetonodes(e.g.,reachachildorgetavalue),andactivitiesthatrelatetotrees(e.g.,treeinitialization).SonodesandtreesshouldbeseparateclassesinaC++implementation.//binarytreenodeabstractclasstemplateclassElemclassBinNode{public://returnthenode’selementvirtualElem&val()=0;//setthenode’selementvirtualvoidsetval(constElem&)=0;//returnthenode’sleftchildvirtualBinNode*left()const=0;//setthenode’sleftchildvirtualvoidsetLeft(BinNode*)=0;//returnthenode’srightchildvirtualBinNode*right()const=0;//setthenode’srightchildvirtualvoidsetRight(BinNode*)=0;//returntrueifthenodeisaleafvirtualboolisleaf()=0;};BinaryTreeTraversals(二叉树的遍历)查找某个结点，或对二叉树中全部结点进行某种处理，就需要遍历。（1）遍历定义遍历是指按某条搜索路线寻访树中每个结点，且每个结点只被访问一次。按先左后右的原则，一般使用三种遍历：preordertraversal前序遍历inordertraversal中序遍历posterordertraversal后序遍历前序遍历(DLR):访问根结点，按前序遍历左子树，按前序遍历右子树。ABDCEGFHI中序遍历(LDR):按中序遍历左子树，访问根结点，按中序遍历右子树。BDAGECHFI后序遍历(LRD):按后序遍历左子树，按后序遍历右子树，访问根结点。二叉树为空时，执行空操作，即空二叉树已遍历完。DBGEHIFCAACHMBELKD（2）遍历算法先序遍历：DLR中序遍历：LDR后序遍历：LRDADBCT1T2T3DLRADLRDLRBDCDLR以先序遍历DLR为例演示遍历过程ABDCBDACDBCAtemplateclassElemvoidPreOder(BinNodeElem*subroot){if(subroot==NULL)return;visit(subroot);PreOrder(subroot-left());PreOrder(subroot-right());}/*前序遍历*/主程序Pre(T)返回返回pre(SR);返回返回pre(SR);ACBDSBvisit(B);pre(SL);BSAvisit(A);pre(SL);ASDvisit(D);pre(SL);DSCvisit(C);pre(SL);C返回S左是空返回pre(SR);S左是空返回S右是空返回S左是空返回S右是空返回pre(SR);templateclassElemvoidPreOder(BinNodeElem*subroot){if(subroot==NULL)return;visit(subroot);PreOrder(subroot-left());PreOrder(subroot-right());}/*前序遍历*/templateclassElemvoidPreOder(BinNodeElem*subroot){if(subroot==NULL)return;visit(subroot);PreOrder(subroot-left());PreOrder(subroot-right());}/*前序遍历*/?中序遍历二叉树的递归算法：templateclassElemvoidInOder(BinNodeElem*subroot){if(subroot==NULL)return;InOrder(subroot-left());visit(subroot);InOrder(subroot-right());}}/*中序遍历*/后序遍历二叉树的递归算法：templateclassElemvoidPostOder(BinNodeElem*subroot){if(subroot==NULL)return;PostOrder(subroot-left());PostOrder(subroot-right());visit(subroot);}}/*后序遍历*/Example5.4Afunctionthatcountsthenumberofnodesinabinarytree.templateclassElemintcount(BinNodeElem*subroot){if(subroot==NULL)return0;return1+count(subroot-left())+count(subroot-right());}BinaryTreeNodeImplemention(二叉树的实现)ACEBFDGHIAtypicalpointer-basedbinarytreeimplemention,Eachnodestorestwochildpointersandavalue.Abinarytreenodeclassimplemention(二叉树结点类的实现)//BinarytreenodeclasstemplateclassElemclassBinNodePtr:publicBinNodeElem{private:Elemit;//Thenode'svalueBinNodePtr*lc;//PointertoleftchildBinNodePtr*rc;//Pointertorightchildpublic://Twoconstructors--withandwithoutinitialvaluesBinNodePtr(){lc=rc=NULL;}BinNodePtr(Eleme,BinNodePtr*l=NULL,BinNodePtr*r=NULL){it=e;lc=l;rc=r;}~BinNodePtr(){}//DestructorElem&val(){returnit;}voidsetVal(constElem&e){it=e;}inlineBinNodeElem*left()const{returnlc;}voidsetLeft(BinNodeElem*b){lc=(BinNodePtr*)b;}inlineBinNodeElem*right()const{returnrc;}voidsetRight(BinNodeElem*b){rc=(BinNodePtr*)b;}boolisLeaf(){return(lc==NULL)&&(rc==NULL);}};-**+*cax2x4Anexpressiontreefor4x(2x+a)-cLeavesandinternalnodesusedifferentdefinitionHowtodifferentiateleaffrominternalnodesOnewaytodifferentiateleaffrominternalnodesistousetheC++unionconstruct,asshowninFigure5.9(P152)C++providesabetterapproachtodifferentiatingleaffrominternalnodesthroughtheuseofclassinheritance,asshowninFigure5.10(P153)Anotherwaytodifferentiateleaffrominternalnodesistouseavirtualbaseclassandseparatenodecla