资源描述：
《数据结构课程之树和二叉树.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
1、第5章数组和广义表（Arrays&Lists）5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.4广义表的定义5.5广义表的存储结构12、广义表特点：有次序性有长度有深度可递归可共享一个直接前驱和一个直接后继＝表中元素个数＝表中括号的重数自己可以作为自己的子表可以为其他广义表所共享特别提示：任何一个非空表，表头可能是原子，也可能是列表；但表尾一定是列表。2介绍两种特殊的基本操作：GetHead(L)——取表头(可能是原子或列表);GetTail(L)——取表尾(一定是列表)。广义表的抽象数
2、据类型定义见教材P107-10831.GetTail【(b,k,p,h)】＝;2.GetHead【((a,b),(c,d))】＝;3.GetTail【((a,b),(c,d))】＝;4.GetTail【GetHead【((a,b),(c,d))】】＝;例：求下列广义表操作的结果（严题集5.10②）(k,p,h)（b）5.GetTail【（e）】＝;6.GetHead【(())】＝.7.GetTail【(())】＝.()(a,b)()()((c,d))45.5广义表的存储结构由于广义表的元素可以是不同结构（
3、原子或列表），难以用顺序存储结构表示，通常用链式结构，每个元素用一个结点表示。1.原子结点：通常设2个域valuetag=0标志域数值域注意：列表的“元素”还可以是列表，故结点有两种形式：2.表结点：通常设3个域tphptag=1标志域表头指针表尾指针指向子表指向下一结点5②C=(a,(b,c,d))1^110a0b0d0c1^1例：①E=(a,E)0a1^1第4-5章自测卷习题解答6数据结构课程的内容7第6章树和二叉树（Tree&BinaryTree）6.1树的基本概念6.2二叉树6.3遍历二叉树和线索
4、二叉树6.4树和森林6.5赫夫曼树及其应用特点：非线性结构，一个直接前驱，但可能有多个直接后继（1：n）86.1树的基本概念1.树的定义2.若干术语3.逻辑结构4.存储结构5.树的运算91.树的定义注1：过去许多书籍中都定义树为n≥1，曾经有“空树不是树”的说法，但现在树的定义已修改。注2：树的定义具有递归性，即树中还有树。由一个或多个(n≥0)结点组成的有限集合T，有且仅有一个结点称为根（root），当n>1时，其余的结点分为m(m≥0)个互不相交的有限集合T1,T2，…，Tm。每个集合本身又是棵树，被
5、称作这个根的子树。10树的表示法有几种：图形表示法嵌套集合表示法广义表表示法目录表示法左孩子－右兄弟表示法这些表示法的示意图参见教材P120树的抽象数据类型定义参见教材P118-11911图形表示法：教师学生其他人员99级2000级2001级2002级……华中科技大学计算机系电信系自控系……叶子根子树12广义表表示法(A(B(E(K,L),F),C(G),D(H(M),I,J))根作为由子树森林组成的表的名字写在表的左边datalink1link2...linkn麻烦问题：应当开设多少个链域?13左孩子－
6、右兄弟表示法ABCDEFGHIJKLM数据左孩子右兄弟(A(B(E(K,L),F),C(G),D(H(M),I,J)))14树的抽象数据类型定义（见教材P118-119）ADTTree{数据对象D:数据关系R:基本操作P：}ADTTree若D为空集，则称为空树；//允许n=0若D中仅含一个数据元素，则R为空集；其他情况下的R存在二元关系：①root唯一//关于根的说明②Dj∩Dk=Φ//关于子树不相交的说明③……//关于数据元素的说明D是具有相同特性的数据元素的集合。//至少有15个152.若干术语——即
7、上层的那个结点(直接前驱)——即下层结点的子树的根(直接后继)——同一双亲下的同层结点（孩子之间互称兄弟）——即双亲位于同一层的结点（但并非同一双亲）——即从根到该结点所经分支的所有结点——即该结点下层子树中的任一结点ABCGEIDHFJMLK根叶子森林有序树无序树——即根结点(没有前驱)——即终端结点(没有后继)——指m棵不相交的树的集合(例如删除A后的子树个数)双亲孩子兄弟堂兄弟祖先子孙——结点各子树从左至右有序，不能互换（左为第一）——结点各子树可互换位置。162.若干术语（续）——即树的数据元素—
8、—结点挂接的子树数（有几个直接后继就是几度，亦称“次数”）结点结点的度结点的层次终端结点分支结点树的度树的深度(或高度)ABCGEIDHFJMLK——从根到该结点的层数（根结点算第一层）——即度为0的结点，即叶子——即度不为0的结点（也称为内部结点）——所有结点度中的最大值（Max{各结点的度}）——指所有结点中最大的层数（Max{各结点的层次}）问：右上图中的结点数＝；树的度＝；树的深度＝1334173.树的逻辑结构(特点)
