湖南省长沙市2012-2013学年八年级生物上学期段考试题新人教版

1树和二叉树数据结构与算法2树的（物理）存储结构3内容父指针表示法•树的实现•K叉树•树的顺序表示法4父指针表示法5内容•父指针表示法树的实现子结点表表示法左子结点/右兄弟结点表示法动态结点表示法动态左子结点/右兄弟结点表示法•K叉树•树的顺序表示法6子结点表表示法ListsofChildren7左子结点/右兄弟结点表示法(1)8左子结点/右兄弟结点表示法(2)9内容•树的定义与术语•父指针表示法树的实现子结点表表示法左子结点/右兄弟结点表示法动态结点表示法动态左子结点/右兄弟结点表示法•K叉树•树的顺序表示法10LinkedImplementations(1)11LinkedImplementations(2)12树替换为二叉树左子结点/右兄弟结点表示法本质上使用二叉树来替换树.使用这种方法可以把任意树替换为二叉树.森林是一个或多个树的集合.13内容•树的定义与术语•父指针表示法•树的实现•K叉树树的顺序表示法14树的顺序表示法(1)按照先根周游的顺序访问结点的值.节省空间，但是只允许顺序查找.必须保留重建树结构的信息.例子:对于二叉树,使用一个符号来标记null指针.AB/D//CEG///FH//I//ABDCEGFHI15树的顺序表示法(2)例子:对于满二叉树,标记叶结点或分支结点.A’B’/DC’E’G/F’HI例子:对于树,标记每个子树的结束.RAC)D)E))BF)))ABDCEGFHIRADBCFE16要点回顾•父指针表示法•树的实现•K叉树•树的顺序表示法17二叉树的（物理）存储结构18内容•二叉树的实现使用数组实现二叉树–使用指针实现二叉树19对于满二叉树和完全二叉树，显然可以将二叉树的数据元素映射到一组连续的存贮单元，反之可以按向量的下标值确定相应数据元素在二叉树中的结点位置。BDEACFGHIABCDEFGHI123456789完全二叉树二叉树的数组实现20但对下列二叉树存于一向量中BDEACFGABCDEFG123456789101112131415BCADABC12345678D21显然要浪费大量的存贮单元，此外，若要在二叉树中插入或删除结点时，更为不便。因此，以顺序结构存贮一般的二叉树是不适宜的。通常情况下，采用多重链表结构(对于非满二叉树和非完全二叉树)来作为二叉树的存贮结构。22使用数组来实现完全二叉树(1)Position01234567891011Parent--00112233445LeftChild1357911------------RightChild246810--------------LeftSibling----1--3--5--7--9--RightSibling--2--4--6--8--10----23Parent(r)=(r-1)/2当0rn时Leftchild(r)=2r+1当2r+1n时Rightchild(r)=2r+2当2r+2n时Leftsibling(r)=r-1当r为偶数且0rn时Rightsibling(r)=r+1当r为奇数且r+1n时使用数组来实现完全二叉树(2)24二叉树•二叉树的实现–使用数组实现二叉树使用指针实现二叉树25BinaryTreeImplementation(1)26BinaryTreeImplementation(2)27ADEBCFrootlchilddatarchild结点结构:二叉链表28ADEBCFroot三叉链表parentlchilddatarchild结点结构:290123456B2C0A-1D2E3F4dataparent结点结构:双亲链表LRTagLRRRL30空间代价SpaceOverhead(1)根据满二叉树定理:•一半的指针是空指针.如果叶子只存储数据,那么额外开销依赖于树是否是满的.例:所有的结点采用带有两个指向子结点的指针的相同的结构:•全部的空间需求是(2p+d)n•额外开销:2pn•Ifp=d,thismeans2p/(2p+d)=2/3overhead.31SpaceOverhead(2)在满二叉树中，去掉叶结点中的指针会省下大量空间:n/2(2p)pn/2(2p)+dnp+d如果p=d,结构性开销将达到全部空间的一半.2p/(2p+d)ifdataonlyatleaves2/3overhead.注意一些方法需要区分叶结点和分支结点.=空间开销有n个结点的满二叉树每个结点都存储两个子结点指针和一个数据去掉叶结点中的指针只有叶结点存储数据(分支结点的数据区没有使用)分支结点只存储指针,叶结点只存储数据总共需要空间2pn+dn2pn/2+dn2pn/2+dn2pn/2+dn/2结构性开销在全部开销中所占比例若p=d=2/3=1/2=3/4=2/3dppdnpnpn2222dppdnpnpn)2(2)2(2dpdpdnpndnpn222)2(22)2(2dppdnpnpn222)2(2)2(233要点回顾•使用指针实现二叉树•使用数组实现二叉树•树型结构是一种动态的，非线性的，可描述结构层次特性的数据结构,如何物理存数（二叉）树是非常重要的！•二叉树的性质是很重要的34课后思考•通过对二叉树存储结构的学习，请思考如何把实际问题中的具有树型关系的数据存储到物理存储结构（内存）中？•模拟可能的实际树型关系的数据（如何表示），并设计方法如何用某种选定的树型物理存储结构来存储。请邮件告诉我（[e-mail]）35二叉树的遍历。课后预习