数据结构与算法分析lecture6(二叉树)ppt课件.ppt

《数据结构与算法分析lecture6(二叉树)ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、BinaryTrees(二叉树)TaoLiangCollegeofsoftwareSiChuanUniversity1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A．线性结构B．非线性结构A顺序存储B链式存储线性表栈队树形结构图形结构数据结构的三个主要问题1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A．线性结构B．非线性结构A顺序存储B链式存储线性表栈队树形结构图形结构数据结构的三个主要问题线性结构A,B,C,·······

2、，X,Y,Z学生成绩表86胡孝臣986110395刘忠赏9861107100张卓9861109成绩姓名学号线性表——结点间是以线性关系联结1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A．线性结构B．非线性结构A顺序存储B链式存储线性表栈队列树形结构图形结构数据结构的三个主要问题树形结构全校学生档案管理的组织方式ABCDEFGH树形结构——结点间具有分层次的连接关系HBCDEFGABinaryTreeDefinitionsandPropertiesBinaryTr

3、eeTraversalsBinaryTreeNodeImplementionsBinarySearchTreesHeapsandPriorityQueuesHuffmanCodingTreesDefinitionsandProperties二叉树的定义：由结点(node)的有限集合组成，这个集合或者为空(empty)，或由一个根结点(root)和两棵分别称为根的左子树(leftsubtree)和右子树(rightsubtree)的互不相交的二叉数组成。ADHIT3JMBELKT1F介绍几个概念：结点（

4、Node）：树中的元素，包含数据项及若干指向其子树的分支。结点的度（Degree）：结点拥有的子树数。结点的层次：从根结点开始算起，根为第0层。叶子（Leaf）：度为零的结点，也称端结点。孩子（Child）：结点子树的根称为该结点的孩子结点。兄弟（Sibling）：同一双亲的孩子。双亲（Parent）：孩子结点的上层结点，称为这些结点的双亲。结点的深度（Depth)：从根结点到该结点的路径的长度。树的高度（Height）：等于最深结点的深度加1。ACHMBELKDABABTwodifferenttre

5、esAB空AB空满二叉树(fullbinarytree)的每一个结点或者是一个分支结点，并恰有两个非空子结点；或者是叶结点.完全二叉树(completebinarytree)有严格的形状要求:从根结点起每一层从左到右填充.一棵高度为d的完全二叉树除了d-1层以外,每一层都是满的.底层叶结点集中在左边的若干位置上.Thistreeisfull(butnotcomplete)Thistreeiscomplete(butnotfull)TheFullBinaryTreeTheorem(满二叉树定理)Theo

6、rem5.1FullBinaryTreeTheorem:Thenumberofleavesinanon-emptyfullbinarytreeisonemorethanthenumberofinternalnodes.Theorem5.2Thenumberofemptysubtreesinanon-emptybinarytreeisonemorethanofnodesinthetree.ADHIT3JMBELKT1FABinaryTreeNodeADTClearlythereareactivities

7、thatrelatetonodes(e.g.,reachachildorgetavalue),andactivitiesthatrelatetotrees(e.g.,treeinitialization).SonodesandtreesshouldbeseparateclassesinaC++implementation.//binarytreenodeabstractclasstemplateclassBinNode{public://returnthenode’selemen

8、tvirtualElem&val()=0;//setthenode’selementvirtualvoidsetval(constElem&)=0;//returnthenode’sleftchildvirtualBinNodeleft()const=0;//setthenode’sleftchildvirtualvoidsetLeft(BinNode)=0;//returnthenode’srightchildvirtualBinNoderight()