数据结构第章树与二叉树ppt课件.ppt

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

1、第5章树和二叉树（Tree&BinaryTree）特点：非线性结构，一个直接前驱，但可能有多个直接后继。（一对多或1:n）5.1树的概述5.2二叉树定义和性质5.3遍历二叉树5.4线索二叉树5.5树和森林5.6哈夫曼及其应用15.1树的基本概念1.树的定义2.若干术语3.逻辑结构4.存储结构5.树的运算21.树的定义注1：树的定义具有递归性，即“树中还有树”。由一个或多个(n≥0)结点组成的有限集合T，有且仅有一个结点称为根（root），当n>1时，其余的结点分为m(m≥0)个互不相交的有限集合T1,T2，…，Tm。每个集合本身又是棵树，被称作这个根的子树。3树的

2、表示法主要有5种：图形表示法嵌套集合表示法广义表表示法凹入表示法左孩子－右兄弟表示法4图形表示法：教师学生其他人员2002级2003级2004级2005级……华科大武昌分校电信系计算机系自控系……叶子根子树5嵌套集合表示法6广义表表示法(A(B(E(K,L),F),C(G),D(H(M),I,J))根作为由子树森林组成的表的名字写在表的左边datalink1link2...linkn麻烦问题：应当开设多少个链域?7凹入表示法(又称目录表示法)8左孩子－右兄弟表示法ABCDEFGHIJKLM数据左孩子右兄弟92.若干术语——即树的数据元素——结点挂接的子树数结点结点

3、的度结点的层次终端结点分支结点树的度树的深度(或高度)——从根到该结点的层数（根结点算第一层）——即度为0的结点，即叶子——即度不为0的结点（也称为非终端结点）——所有结点度中的最大值（Max{各结点的度}）——指所有结点中最大的层数（Max{各结点的层次}）问：右上图中的结点数＝；树的度＝；树的深度＝1334（有几个直接后继就是几度，亦称“次数”）ABCGEIDHFJFLK103.树的逻辑结构一对多（1:n），有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且子树之间互不相交。4.树的存储结构讨论1：树是非线性结构，该怎样存储？特点：——仍然有顺序存储

4、、链式存储等方式。115.2二叉树为何要重点研究每结点最多只有两个“叉”的树？二叉树的结构最简单，规律性最强；可以证明，所有树都能转为唯一对应的二叉树，不失一般性。1.二叉树的定义2.二叉树的性质3.二叉树的存储结构（二叉树的运算见5.3节）121.二叉树的定义定义：是n（n≥0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。逻辑结构：一对二（1:2）基本特征:①每个结点最多只有两棵子树（不存在度大于2的结点）；②左子树和右子树次序不能颠倒。问：具有3个结点的二叉树可能有几种不同形态？有5种基本形态：一般的树有几种？132.

5、二叉树的性质(3+2)讨论1：第i层的结点数最多是多少？（利用二进制性质可轻松求出）性质1:在二叉树的第i层上至多有2i-1个结点（i>0）。性质2:深度为k的二叉树至多有2k-1个结点（k>0）。再提问：第i层上至少有个结点？1讨论2：深度为k的二叉树，最多有多少个结点？（利用二进制性质可轻松求出）2i-1个2k-1个14讨论3：二叉树的叶子数和度为2的结点数之间有关系吗？性质3:对于任何一棵二叉树，若2度的结点数有n2个，则叶子数（n0）必定为n2＋1（即n0=n2+1）证明：∵二叉树中全部结点数n＝n0+n1+n2(叶子数＋1度结点数＋2度结点数)又∵二叉树

6、中全部结点数n＝B+1(总分支数＋根结点)（除根结点外，每个结点必有一个直接前趋，即一个分支）而总分支数B=n1+2n2(1度结点必有1个直接后继，2度结点必有2个)三式联立可得：n0+n1+n2=n1+2n2+1,即n0=n2+1物理意义：叶子数＝2度结点数＋1152.深度为Ｋ的二叉树的结点总数，最多为个。Ａ)２k-1Ｂ)log2kＣ)２k－１Ｄ)２k1.树Ｔ中各结点的度的最大值称为树Ｔ的。Ａ)高度Ｂ)层次Ｃ)深度Ｄ)度DCC3.深度为9的二叉树中至少有个结点。Ａ)２9Ｂ)２8Ｃ)９Ｄ)２9－1课堂练习：16满二叉树：一棵深度为k且有2k-1个结点的二叉树。（特

7、点：每层都“充满”了结点）完全二叉树：深度为k的、有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应。AOBCGEKDJFIHNML深度为4的满二叉树完全二叉树ABCGEIDHFJ为何要研究这两种特殊形式？完全二叉树的特点是只有最后一层叶子不满，且全部集中在左边。但这其实是顺序二叉树的含义。而图论中的“完全二叉树”是指n1=0的情况。因为它们在顺序存储方式下可以复原！17对于两种特殊形式的二叉树（满二叉树和完全二叉树）,还特别具备以下2个性质：性质4:具有n个结点的完全二叉树的深度必为log2n＋1性质5:对完全二叉树，

8、若从上至下