数据结构第5章树与二叉树

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

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树的表示法主要有5种：

2、图形表示法嵌套集合表示法广义表表示法凹入表示法左孩子－右兄弟表示法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：树是非线性结构，该怎样存储？特点：——仍然有顺序存储、链式存储等方式。115.2二叉树为何要重点研究每结点

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

5、可轻松求出）性质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度结点数)又∵二叉树中全部结点数n＝B+1(总分支数＋根结点)（除根结点外，每个结点必有一个直接前趋，即一个分

6、支）而总分支数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个结点的二叉树。（特点：每层都“充满”了结点）完全二叉树：深度为k的、有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二

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