数据结构与算法5资料.ppt

;;;5.1 树的基本概念;树是由n（n≥0）个结点组成的有限集T。当n=0时，称为空树；当n0时，集合T须满足如下条件： 有且仅有一个没有前驱的结点，该结点称为树的根结点； 将根节点去除后，其余结点可分为m（m≥0）个互不相交的子集T1、T2、…、Tm，其中每个子集Ti（i=1, 2, …, m）又是一棵树，并称其为根的子树。 可以看到，树的定义采用的是递归定义方式，即一棵非空的树由根节点和去除根节点后得到的若干棵规模更小的子树构成，而每一棵子树又是由该子树的根节点和去除该子树根节点后得到的若干棵更小的子树构成。例如，图5-1所示的树可以看作是由根节点A和3棵子树T1、T2、T3（结点集合分别为D1={B, E, F, I}、D2={C, G}和D3={D, H, J, K, L}）构成；子树T1又可以看作是由根节点B和两棵子树T11、T12（结点集合分别为D11={E}、D12={F, I}）构成。 ;树形图表示法因其直观性强而成为树的最常用的表示形式，图5-1即是采用树形图表示法表示的树。除树形图表示法之外，还有三种常用的表示形式： 1.嵌套集合表示法 嵌套集合表示法是通过集合包含的形式体现结点之间的关系，后继结点集合包含在前驱结点集合中。例如，采用嵌套集合表示法可将图5-1所示的树表示为图5-3所示的形式。 ;2.凹入表表示法 凹入表表示法是利用书的目录形式表示结点之间的关系，后继结点位于前驱结点的下一层目录中。例如，采用凹入表表示法可将图5-1所示的树表示为图5-4所示的形式。 3.广义表表示法 广义表表示法是利用广义表的多层次结构来表示树，后继结点位于前驱结点的下一层次。例如，采用广义表表示法可将图5-1所示的树表示为图5-5所示的形式。 ;5.1 树的基本概念;5.1 树的基本概念;5.1 树的基本概念;5.1 树的基本概念;;;5.2二叉树及其基本性质 ;;;;;5.3 二叉树的抽象数据类型和表示方式 ;5.3 二叉树的抽象数据类型和表示方式 ;2.二叉树顺序表示的实现 由于顺序表示非完全二叉树时空间利用率较低，因此，二叉树的顺序表示在实际中应用不多。下面主要围绕二叉树的创建和删除这两个最基本的操作介绍二叉树顺序表示的实现。 二叉树顺序表示的类模板描述如下： 【描述5-1】二叉树顺序表示的类模板描述。 分析：在类模板中，需设置以下成员变量：一维数组m_pElement用于存储二叉树中各结点的值，数组类型由二叉树结点的值的类型决定；整型变量m_nMaxSize用于存储二叉树中的最大结点数；一个bool型一维数组m_pbUsed，用于表示结点状态，若某个结点不存在（如图5-9（b）中的结点4和结点5），则m_pbUsed中相应元素的值为false，否则相应元素的值为true。 ;3.二叉树顺序表示代码复用示例 【例5-1】基于二叉树顺序表示的C++实现代码，完成如下操作： 创建图5-9（b）所示的二叉树，其中每一个结点保存一个字符信息，并通过逐层遍历输出各结点的值。 将以结点C为根结点的子树删除，并通过逐层遍历输出各结点的值。 清空二叉树中的元素。 分析：对于由简单数据元素构成的二叉树，一般可以直接使用C++语言提供的基本数据类型来描述数据元素，本例中可直接使用char类型。;5.3 二叉树的抽象数据类型和表示方式 ;5.3 二叉树的抽象数据类型和表示方式 ;5.3 二叉树的抽象数据类型和表示方式 ;5.3 二叉树的抽象数据类型和表示方式 ;5.3 二叉树的抽象数据类型和表示方式 ;5.4 二叉树的遍历及常用操作;;;5.4 二叉树的遍历及常用操作;;;1.获取指定结点的双亲结点 在二叉树的二叉链表表示中，结点中没有指向其双亲结点的指针，要获取双亲结点则需要从根结点开始遍历二叉树直至找到指定结点的双亲结点。因此，可以参照上一小节中给出的二叉树遍历算法，编写获取双亲结点的程序。 2.删除以指定结点为根的子树 删除以指定结点为根的子树，一方面要将子树从二叉树中删除，另一方面要将子树中的结点释放。将子树从二叉树中删除是通过将指定结点的双亲结点的指针值置空来实现（若删除的是整棵二叉树，则应将根结点指针值置空）。将子树中的结点释放，就是采用类似于遍历子树中所有结点的方式将各结点占据的内存释放。;3.根据关键字查找结点 根据关键字查找结点，实质上就是按照某种规则依次访问二叉树中的每一结点，直至找到与关键字匹配的结点。因此，同遍历算法一样，根据关键字查找结点也可以采用递归方式和非递归方式。;5.5 哈夫曼树和哈夫曼码 ;;5.5 哈夫曼树和哈夫曼码 ;5.5 哈夫曼树和哈夫曼码 ;在由n个叶