数据结构课件树和叉树

《数据结构课件树和叉树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、树型结构不同与线性表、栈、队列、串和广义表结构，是一类重要的非线性数据结构，其中以树和二叉树最为常用。树形结构反映了元素之间的层次关系和分支关系，它非常类似于自然界中的树。1第6章树和二叉树树型结构在现实世界中广泛存在，例如人类社会的族谱和各种社会组织机构都可用树来表示。在计算机领域中，DOS和Windows操作系统中对磁盘文件的管理就采用树型目录结构；在编译程序中，使用树来表示源程序的语法结构；在数据库系统中，树型结构也是信息的重要组织形式之一。6.1树6.2二叉树6.3遍历二叉树6.4二叉线索树6.5树和森林与二叉树的转换6.6赫夫曼树及其应用6.1树6.2二叉树6.3遍历二叉树

2、6.4二叉线索树6.5树和森林与二叉树的转换6.6赫夫曼树及其应用树(tree)结构是一种多分支多层次的数据结构，由一组结点组成。由于它呈现与自然界树类似的结构形式，所以称之为树。在许多算法中，常用树型结构描述问题的求解过程或表示求解的对策等。树的逻辑结构6.1树2树的存储结构树是由n(n≥0)个结点组成的有限集。在任意一棵非空树T中：①有且仅有一个特定的称为根(root)结点；②当n>1时，其余n-1个结点分成m(m>0)个互不相交的有限集T1，T2，…，Tm，其中每一个集合Ti本身又都是一棵树，并且称为根的子树。36.1.1树的逻辑结构1.树的定义AABCABCABDCEGFHI

3、JK(a)(b)(c)(d)452.树的基本操作InitTree(tree);操作结果：构造空树Tree。InsertChild(Tree,p,child);初始条件：树Tree存在，p指向Tree中某个结点，1≤i≤p所指结点的度+1，非空树child与Tree不相交。操作结果：插入child为Tree中p所指结点的子树。树结构中经常会用到一些基本术语。例如：结点结点的度叶结点分支结点树的度双亲及孩子兄弟堂兄弟祖先子孙层次树的深度有序树无序树森林63.树的基本概念7ABDCEFKLGHIJM结点：树结点包含一个数据元素及若干指向其子树的分支A结点的度：结点所拥有的子树的数目叶子

4、结点：度为0的结点，也称终端结点FKLGIJM分支结点：度不为0的结点，也称非终端结点ABDCEH树的度：树内各结点的度的最大值双亲及孩子：一个结点的子树的根称为该结点的孩子，该结点称为孩子的双亲HIJ结点D的孩子D结点H、I、J的双亲兄弟：同一个双亲的孩子之间称为兄弟HIJ堂兄弟：双亲结点在同一层的结点互为堂兄弟FGH祖先：从根到一个结点之间的所有结点叫做这结点的祖先ABEK结点A、B、E是结点K的祖先子孙：以某结点为根的子树中的任一结点为此结点的子孙BEFKL结点E、F、K、L是结点B的子孙层次：一棵树的根结点所在的层次为1。其他结点所在的层次等于它的双亲结点所在的层次加1。根为

5、第一层1234深度：树中结点最大层次称为树的深度4DHJDJH有序树：将树中结点的各个子树看成从左至右是有次序的（即不能互换）DHJDJH无序树：将树中结点的各个子树看成是没有次序的（即可以互换）森林：m(m≥0)棵不相交的树的集合。对树中每个结点而言，其子树的集合即为森林BDCEFKLGHIJM二叉树(binarytree)是另一种树型结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。二叉树的逻辑结构6.2二叉树8二叉树的基本性质二叉树的存储结构二叉树是一个有限的结点的集合，该集合或者为空，或者由满足以下两

6、个条件的树型结构组成⑴每个结点的度都不大于2；⑵每个结点的孩子结点次序不能任意颠倒。96.2.1二叉树的逻辑结构1.二叉树的定义①空二叉树；②仅有根结点的二叉树；③有根结点和左子树，而右子树为空的二叉树；④有根结点、左子树和右子树的二叉树；⑤有根结点和右子树，而左子树为空的二叉树。(a)(b)(c)(d)(e)10二叉树的5种基本形态12436875101211914151311性质1：在二叉树的第i层上至多有2i-1个结点（i≥1）。证明：利用归纳法容易证得此性质。i=1时，只有一个根结点。2i-1=20=1，命题成立。假定对所有的j(1≤j＜i)，命题成立，即第j层上至多有2j-

7、1个结点。那么，可以证明j=i时命题也成立。根据归纳假设，第i-1层上至多有2i-2个结点。由于二叉树的每个结点的度最多为2，所以在第i层上最多的结点数为第i-1层上的2倍，即2×2i-2=2i-1。126.2.2二叉树的基本性质性质2：深度为k的二叉树至多有2k－1个结点（k≥1）。=2k－113证明：由性质1可见，深度为k的二叉树的最大结点数为性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0＝n2+1。14证明：(1)设