树和二叉树副本知识讲解.ppt

《树和二叉树副本知识讲解.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、树和二叉树副本树是一类重要的非线性数据结构，是以分支关系定义的层次结构。树结构在客观世界中广泛存在，如人类社会的族谱和各种组织机构都可以用树来形象表示。族谱组织机构定义定义：树(tree)是n(n>=0)个结点的有限集T，在任意一棵非空树中：有且仅有一个特定的结点，称为树的根(root)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)特点：树中有一个结点——根树中各子树是互不相交的集合5.1树的定义和基本术语A只有根结点的树ABCDEFGHIJ

2、KLM有子树的树根子树T1T2T32021年9月8日5.1树的定义和基本术语树是n个结点的有限集T1T2T3有子树的树和线性结构的比较线性结构              树结构第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素              树中其它结点(一个前驱、一个后继)      (一个前驱、多个后继)2021年9月8日ADTTree{数据对象D:数据关系R:基本操作P：}ADTTree若D为空集，则称为空树；//允许n=0若D中仅含一个数据元素，则R为空集；其他情

3、况下的R存在二元关系：①root唯一//关于根的说明②Dj∩Dk=Φ//关于子树不相交的说明③……//关于数据元素的说明D是具有相同特性的数据元素的集合。//至少有15个树的抽象数据类型定义2021年9月8日凹入表示嵌套集合广义表树的其它表示方式2021年9月8日根叶子森林——即根结点(没有前驱)——即终端结点(没有后继)——指m棵不相交的树的集合(例如删除A后的子树个数)基本术语基本术语——即树的数据元素——结点挂接的子树数结点结点的度结点的层次终端结点分支结点树的度树的深度(或高度)——从根到该结点的层数（根结点算第一层）——即

4、度为0的结点，即叶子——即度不为0的结点（也称为内部结点）——所有结点度中的最大值——指所有结点中最大的层数层次1234——即上层的那个结点(直接前驱)——即下层结点的子树的根(直接后继)——同一双亲下的同层结点（孩子之间互称兄弟）——即双亲位于同一层的结点（但并非同一双亲）——即从根到该结点所经分支的所有结点——即该结点下层子树中的任一结点双亲孩子兄弟堂兄弟祖先子孙基本术语有序树：若从树中结点的各个子树看是从左到右有序的（不可互换），则称为有序树，否则为无序树。ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0叶

5、子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层次：1结点M的层次：4树的深度：4结点F，G为堂兄弟结点A是结点F，G的祖先2021年9月8日5.2二叉树普通树（多叉树）若不转化为二叉树，则运算很难实现为何要重点研究每结点最多只有两个“叉”的树？二叉树的结构最简单，规律性最强；可以证明，所有树都能转为唯一对应的二叉树，不失一般性。二叉树的定义二叉树是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分

6、别称为左子树和右子树的互不相交的二叉树构成特点每个结点至多有二棵子树(结点的度小于等于2）有序树：二叉树的子树有左、右之分，且其次序不能任意颠倒2021年9月8日二叉树的五种不同形态2021年9月8日具有3个结点的二叉树可能有几种不同形态？普通树呢？练习5种/2种2021年9月8日ADTBinaryTree{数据对象D:数据关系R:基本操作P：}ADTBinaryTree若D=Φ，则R=Φ；若D≠Φ，则R={H}；存在二元关系：①root唯一//关于根的说明②Dj∩Dk=Φ//关于子树不相交的说明③……//关于数据元素的说明④……/

7、/关于左子树和右子树的说明D是具有相同特性的数据元素的集合。//至少有20个二叉树的抽象数据类型定义2021年9月8日性质1:在二叉树的第i层上至多有2i-1个结点二叉树的性质提问：第i层上至少有个结点？1证明：用归纳法证明之i=1时，只有一个根结点，是对的假设对所有j(1j

8、结点提问：深度为k时至少有个结点？k证明：由性质1，可得深度为k的二叉树最大结点数是2021年9月8日性质3:对于任何一棵二叉树，若2度的结点数有n2个，则叶子数n0必定为n2＋1（即n0=n2+1）性质3：对任何一棵二叉树T，如果其