数据结构-chapter6.pdf

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

1、数据结构2017年5月5日星期五第6章树和二叉树特点：非线性结构，一个直接前驱，但可能有多个直接后继（1：n）F6.1树的定义和基本术语F6.2二叉树F6.3遍历二叉树和线索二叉树F6.4树和森林F6.6赫夫曼树及其应用26.1树的定义和基本术语1.树的定义由一个或多个（n≥0）结点组成的有限集合。在任何一棵非空树T中：（1）有且仅有一个结点称为根（root）；（2）当n>1时，其余的结点分为m（m≥0）个互不相交的有限集合T1、T2…Tm。每个集合本身又是棵树，被称作这个根的子树。注：树的定义具有递

2、归性，即树中还有树。36.1树的定义和基本术语只有根结点的树A根ABCDEFGHIJKLM子树46.1树的定义和基本术语树的抽象数据类型定义数据对象D:D是具有相同特性的数据元素的集合。数据关系R:若D是空集，则称为空树；//允许n=0若D中仅含一个数据元素，则R为空集；其他情况下的R存在二元关系：①Root唯一//关于根的说明②D∩D=//关于子树不相交的说明jk③…//关于数据元素的说明数据操作P://至少15个56.1树的定义和基本术语树的表示方法•图形表示法•嵌套集合表示法•广义表表示法•凹

3、入表示法（目录表示法）66.1树的定义和基本术语①图形表示法：根武汉纺织大学管理学院电信学院外语学院…A电子通信电气光电BCD子树EFGH76.1树的定义和基本术语②广义表表示法：根作为由子树森林组成的表的名字写在表的左边A（B，C，D）A（B，C（E,F,G,H），D）③凹入表示法：ABCAEBCDFGEFGHHD86.1树的定义和基本术语④嵌套表示法：AABCDEFBCDGHEFGH96.1树的定义和基本术语A2.若干术语BCD根----根结点（没有前驱）EFGHIJ森林----指m棵不相交的树的

4、集合KLM有序树----结点各子树从左至右有序，不能互换（左为第一）无序树----结点各子树可互换位置双亲----上层的那个结点（直接前驱）孩子----下层结点的子树的根（直接后继）兄弟----同一双亲下的同一层结点（孩子之间互称兄弟）堂兄弟----双亲位于同一层的结点（但并非同一双亲）祖先----从根到该结点所经分支的所有结点子孙----该结点下层子树的任一结点106.1树的定义和基本术语结点----树中的数据元素结点的度----结点拥有的子树的数目（有几个直接后继度就是几）结点的层次----从根到

5、该结点的层数（根结点算第一层）A叶子----度为0的点（终端结点）BCD分支结点----度不为0的点（非终端结点）EFGHIJKLM树的度----所有结点度中的最大值（Max{各结点的度}）树的深度----所有结点中最大的层数（Max{各结点的层次}）（或高度）116.2二叉树ü二叉树的结构最简单，规律性最强；ü可以证明，所有树都能转化为唯一对应的二叉树，不失一般性。1.二叉树的定义2.二叉树的性质3.二叉树的存储结构126.2二叉树---定义①每个结点最多只有两棵子树（不存在度大于2的结点）；②左子

6、树和右子树次序不能颠倒（有序树）。①②③④⑤Æ•具有3个结点的二叉树可能有几种不同形态？普通树呢？136.2二叉树---性质性质1：在二叉树的第i层上至多有2i-1个结点（i>0）。问：第i层上至少有个结点？性质2：深度为k的二叉树至多有2k-1个结点（k>0）。性质3：对于任何一棵二叉树，若度2的结点数有n2个，叶子结点数为n0，则n0=n2+1。146.2二叉树---性质证明性质3：∵二叉树中全部结点数n=n0+n1+n2(叶子数+度1的结数+度为2的结点数)又∵二叉树中全部结点数n=B+1(总分

7、支数+根结点)（除根结点外，每个结点必有一个直接前驱，即一个分支）而总分支数B=n1+2n2(度为1必有1个直接后继，度为2必有2个直接后继)三式联立可得：n0+n1+n2=n1+2n2+1，即n0=n2+1156.2二叉树---特例满二叉树：深度为k且有2k-1个结点的二叉树。1特点：每一层上的结点数都是最大结点数。23可以对满二叉树的结点进行连续编号。456789101112131415完全二叉树：深度为k，有n个结点的1二叉树，当且仅当其每一个结点都与深度23为k的满二叉树中编号从1至n的结点一

8、一4567对应时，称之为完全二叉树。8910特点:（1）叶子结点只可能在层次最大的两层上出现；（2）对任一结点，若其右分支下的子孙的最大层次为h，则其左分支下的子孙的最大层次数必为h或h+1。166.2二叉树---特例1123234567458910111213141567123123456745689101112176.2二叉树---性质对于特殊性质的二叉树，还具备以下2个性质：12345678910186.2二叉树---存储结构0AA1B一、顺序存储