数据结构(C语言)中ppt.ppt

数据结构（ C语言）中 第 5章 树 （时间： 3次课， 6学时） 第 5章 树 教学提示： 在前面 2 4章中介绍了线性表 、 栈 、 队列 、 数 组 、 串等 ， 它们的逻辑结构都是线性的 ， 即数据之间存在着 一对一的关系 ， 表示数据的结点间具有惟一前驱和惟一后继 。 然而 ， 在实际应用中常常遇到非线性关系 。 非线性结构的特 征是结点间的关系不具有惟一性 。 本章介绍的树型结构 ， 其 结点间关系具有惟一的前驱而后继不惟一 ， 即结点之间是一 对多的关系 。 教学目标： 通过本章的学习 ， 用户应掌握树的逻辑结构 、 存 储结构及其基本操作；学会利用树 、 二叉树的特性 、 遍历的 递归算法以及哈夫曼算法解决实际问题 。 第 5章 树 5.1 树 5.2 二叉树 5.3 树和森林 5.4 上机实习 5.5 习题 5.1 树 5.1.1 树的基本概念 5.1.2 树的表示 5.1.3 树的基本运算 5.1.1 树的基本概念 图 5.1 树的逻辑结构示例 5.1.1 树的基本概念 1. 树的定义 树是 n(n0)个结点的有限集合 。 当 n 0时 ， 为空树；当 n 0时 ， 该集合满足如下条件： 有且仅有一个称为根 (root)的特定结点 ， 它没有直接前驱 ， 但有零个或多个直接后继 。 其余 n-1个结点 可以划分成 m (m0) 个互不相交的有限集 T1， T2， ， Tm， 其 中每一个集合 Ti又是一棵树 ， 称其为根的子树 。 2. 关于树结构的基本术语 结点： 包含一个数据元素及若干指向其子树的分支信息 。 结点的度： 一个结点所拥有的子树个数称为该结点的度 。 树的度： 树中所有结点的度的最大值 。 叶子结点 (终端结点 )： 度为零的结点 ， 即没有后继的结点 。 分支结点 (非终端结点 )： 度不为零的结点 。 孩子结点： 若某个结点为树或子树的根 ， 这个结点的直接后继 ， 称为该结点的孩子结点 。 5.1.1 树的基本概念 双亲结点： 一个结点被称为其孩子结点 (或后继结点 )的双亲结点 。 兄弟结点： 同一个双亲的结点之间互为兄弟结点 。 祖先结点： 从树的根结点到达一个结点的路径上的所有结点都是 该结点的祖先结点 。 子孙结点： 结点为根的子树中的所有结点 (包括直接后继和间接 后继 )都称为该结点的子孙结点 。 结点的层次： 树具有一种层次结构 ， 从根结点开始定义 ， 根结点 为第一层 ， 根的孩子为第二层 ， 以此类推 。 树的高度 (深度 )： 树中所有结点的层次的最大值 。 有序树： 如果将树结点的各个子树看成从左到右是有次序的 (不 能互换 )， 即各子树之间是有先后次序的 ， 则称之为有序树 。 反 之 ， 被称为无序树 。 森林： m(m0)棵互不相交的树的集合 。 5.1.2 树的表示 除了树的逻辑定义以外 ， 树的表示法还有以下四种 。 对于以下逻辑 结构的树： T = (K， L) K = A， B， C， D， E， F， G， H L = ， ， ， ， ， ， T是表示树形结构的二元组 ， 其中 ， K是树中结点的有限集 ， L是树 中结点之间关系的有限集 。 正是由于树结构在日常生活和计算机程序设计中应用非常广泛 ， 使 得树的表示方法多种多样 。 一般来说 ， 分等级的分类方案都可以用 树结构表示 。 5.1.2 树的表示 图 5.2 树的四种表示 5.1.3 树的基本运算 数据对象 D： D是一个集合 ， 且该集合中的所有元素具有相同的特性 。 数据关系 R： 若 D为空集 ， 则为空树 。 若 D中仅含有一个数据元素 ， 则 R为空集 ， 否则 R = H ， 其中 H是如下的二元关系： 在 D中存在惟一的称为根的数据元素 root， 它在关系 H下没有前驱 。 除 root以外 ， D中每个结点在关系 H下都有且仅有一个前驱 。 基本操作： InitTree(Tree)：将 Tree初始化为一棵空树 。 DestoryTree(Tree)：销毁树 Tree。 CreateTree(Tree)：创建树 Tree。 TreeEmpty(Tree)：若 Tree为空 ， 则返回 TRUE， 否则返回 FALSE。 ROOT(Tree)：返回树 Tree的根 。 5.1.3 树的基本运算 (2) Parent(Tree， x)： 树 Tree存在 ， x是 Tree中的某个结点 。 若 x为非根结 点 ， 则返回它的双亲 。 否则返回 “ 空 ” 。 FirstChild(Tree， x)： 树 Tree存在 ， x是 Tree中的某个结点 。 若 x为非叶 子结点 ， 则返回它的第一个孩子结点 ， 否则返回 “ 空 ” 。 NextChild(Tree， x)： 树 Tree存在 ， x是 Tree中的某个结点 。 若 x不是其 双亲的最后一个孩子结点 ， 则返回 x后面的下一个兄弟结点 ， 否则返 回 “ 空 ” 。 InsertChild(Tree， p， Child)： 树 Tree存在 ， p指向 Tree中某一个结点 ， 非空树 Child与 Tree不相交 。 将 Child插入 Tree中 ， 作为 p所指向结点的 子树 。 DeleteChild(Tree， p， i)： 树 Tree存在 ， p指向 Tree中某个结点 ， 1id， d为 p所指向结点的度 。 删除 Tree中 p所指向结点的第 i棵子树 。 TraverseTree(Tree， Visit()： 树 Tree存在 ， Visit()是对结点进行访问的 函数 。 按某种次序对树 Tree的每个结点调用 Visit()函数访问一次且最 多访问一次 。 若 Visit()失败 ， 则操作失败 。 5.2 二 叉 树 5.2.1 二叉树的概念 5.2.2 二叉树的性质 5.2.2 二叉树的性质 5.2.1 二叉树的概念 1. 二叉树 二叉树 (Binary Tree)是一种特殊的树形结构 ， 它必须满足以下两个条件： 树中每个结点至多只有两棵子树 (即二叉树中不存在度大于 2的结点 )； 二叉树的每个结点的子树有左右之分 ， 其次序不能任意颠倒 。 二叉树的抽象数据类型的定义如下： ADT BinaryTree 5.2.1 二叉树的概念 图 5.3 二叉树的五种基本形态 5.2.1 二叉树的概念 5.2.1 二叉树的概念 基本操作： InitBiTree(BiTree)： DestoryBiTree(TBiree)： CreateTree(BiTree)： BiTreeEmpty(BiTree)： ROOT(BiTree)： BiTreeDepth(BiTree)： Parent(BiTree， x)： LeftChild(BiTree， x)： RightChild(BiTree， x)： InsertChild(BiTree， p， i， Child)： DeleteChild(BiTree， p， i)： Value(BiTree， x)： Assign(BiTree， x， value)： PreOrderTraverse(BiTree， visit()： InOrderTraverse(BiTree， visit()： PostOrderTraverse(BiTree， visit()： LevelOrderTraverse(BiTree， visit()： 5.2.1 二叉树的概念 2. 满二叉树 棵深度为 k且有 2k-1个结点的二叉树称为满二叉树 。 这种树的特点是 每一层上的结点数 ， 都是最大结点数 。 3. 完全二叉树 深度为 k， 结点数为 n的二叉树 ， 当且仅当其每个结点都与深度为 k的 满二叉树中编号从 1至 n的结点一一对应时 ， 称为完全二叉树 。 完全二叉树也是特殊形态的二叉树 。 完全二叉树的特点是： 5.2.1 二叉树的概念 图 5.4 满二叉树 图 5.5 完全二叉树 5.2.2 二叉树的性质 二叉树具有下列重要特性 : 1. 性质 1: 在二叉树的第 i层上至多有 2i 1个结点 (i1)。 2. 性质 2: 深度为 k的二叉树至多有 2k 1个结点 (k1)。 3. 性质 3: 对任意一棵二叉树 T，如果其终端结点数为 n0，度 为 2的结点数为 n2，则 n0=n2+1。 4. 性质 4: 具有 n个结点的完全二叉树的深度为 log2n +1。 5. 性质 5: 对于具有 n个结点的完全二叉树，如果按照从上到 下和从左到右的顺序对二叉树中的所有结点从 1开始顺 序编号，则对于任意的序号为 i的结点有： (1) 若 i=1，则序号为 i的结点是二叉树的根结点，无双亲， 如 i1，则序号为 i的结点的双亲结点序号为 i/2。 (2) 若 2in，则序号为 i的结点无左孩子；若 2in，则序号为 i 的结点的左孩子结点的序号为 2i； (3) 若 2i+1n，则序号为 i的结点无右孩子；若 2i+1n，则序 号为 i的结点的右孩子结点的序号为 2i+1。 5.2.3 二叉树的存储结构 二叉树的结构是非线性的结构 ， 即每一结点最多可有两个后继 。 二叉树存储结构有两种：顺序存储结构和链式存储结构 。 1. 顺序存储结构 顺序存储结构是用一组连续的存储单元来存放二叉树的数据元素 。 根据二叉树的性质 5， 可得根结点的编号为 1， 结点 i的左孩子的位置为 Lchild(i)=2i；右孩子的位置为 Rchild(i)=2i+1。 2. 链式存储结构 用链式结构存储二叉树 ， 关键是设计结点的结构 ， 不同的结点结构会 构造出不同的链表 。 根据二叉树的定义 ， 二叉树的每个结点由一个数据元素和分别指向左 、 右孩子的两分支组成 。 根据二叉链表的结构特点 ， 可以得出：若一棵二叉树含有 n个结点 ， 则 它的二叉链表中必含有 2n个指针字段 ， 其中 n+1个为空链字段 。 5.2.3 二叉树的存储结构 图 5.7 一般二叉树及其顺序存储结构 5.2.3 二叉树的存储结构 图 5.8 单支二叉树及其顺序存储结构 5.2.3 二叉树的存储结构 图 5.9 二叉树的结点及存储结构 5.2.3 二叉树的存储结构 用 C语言说明二叉树的二叉链表结点的结构： typedef struct BiTNode DataType data; Struct Node *Lchild; Struct Node *Rchild; BiTree; 5.2.3 二叉树的存储结构 图 5.10 链表存储结构 5.2.4 二叉树的遍历 二叉树的遍历 是指按一定规律或路径对二叉树中的每个结点进行访 问且仅访问一次 。 其中的 “ 访问 ” 指对二叉树中的结点进行各种处 理和操作 。 根据二叉树的递归定义 ， 二叉树是由根结点 、 左子树 、 右子树三部 分组成的 ， 因此只要依次遍历这三部分 ， 就遍历了整棵二叉树 。 假设约定 L、 D、 R分别表示遍历左子树 ， 访问根结点 ， 遍历右子树 ， 则 对二叉树的遍历顺序可以有六种方式： 先访问根 ， 再遍历左子树 ， 最后遍历右子树 (记做 DLR)。 先访问根 ， 再遍历右子树 ， 最后遍历左子树 (记做 DRL)。 先遍历左子树 ， 再访问根 ， 最后遍历右子树 (记做 LDR)。 先遍历右子树 ， 再访问根 ， 最后遍历左子树 (记做 RDL)。 先遍历左子树 ， 再遍历右子树 ， 最后访问根 (记做 LRD)。 先遍历右子树 ， 再遍历左子树 ， 最后访问根 (记做 RLD)。 5.2.4 二叉树的遍历 在以上六种遍历方式中 ， 规定按先左后右的顺序 ， 则只保留 DLR、 LDR、 LRD三种遍历方式 。 又根据对根访问的顺序的不同分别称 DLR为先序 (根 )遍历 ， LDR为中序 (根 )遍历 ， LRD为后序 (根 )遍历 。 先序遍历 (DLR)： 若二叉树为空 ， 则空操作 ， 否则依次执行如下三 个操作： (1) 访问根结点； (2)先序遍历左子树； (3) 先序遍历右子树 。 中序遍历 (LDR)： 若二叉树为空 ， 则空操作 ， 否则依次执行如下三 个操作： (1) 按中序遍历左子树； (2) 访问根结点； (3) 按中序遍历 右子树 。 后序遍历 (LRD)： 若二叉树为空 ， 则空操作 ， 否则依次执行如下三 个操作： (1) 后序遍历左子树； (2) 后序遍历右子树； (3) 访问根 结点 。 5.2.4 二叉树的遍历 _算法 先序遍历二叉树的递归算法 : void PreOrder(BiTree *p) if(p!=NULL) printf(%d,p-data); PreOrder(p-lchild); PreOrder(p-rchild); 5.2.4 二叉树的遍历 _算法 中序遍历二叉树的算法 : void InOrder(BiTree *p) if(p!=NULL) InOrder(p-lchild); printf(%d,p-data); InOrder(p-rchild); 5.2.4 二叉树的遍历 _算法 后序遍历二叉树的算法 : void PostOrder(BiTree *p) if(p!=NULL) PostOrder(p-lchild); PostOrder(p-rchild); printf(%d,p-data); 5.2.4 二叉树的遍历 _例 先序遍历序列： A B D F G C E H 中序遍历序列： B F D G A C E H 后序遍历序列： F G D B H E C A 5.2.5 哈夫曼树和哈夫曼编码 哈夫曼树又称最优二叉树 ， 是一种带权路径长度最短的树 ， 有着广泛 的应用 。 1. 哈夫曼树 路径和路径长度 路径是指从一个结点到另一个结点之间的分支序列；路径长度是指一 个结点到另一个结点的路径上所经过的分支数目 。 结点的权和带权路径长度 在实际应用中 ， 人们常常给树的每个结点赋予一个具有某种实际意义 的实数 ， 这些具有一定意义的实数被称为这个结点的权 。 在树形结构 中 ， 从树根到某一结点的路径长度与该结点的权的乘积 ， 叫做该结点 的带权路径长度 。 树的带权路径长度 树的带权路径长度为树中所有叶子结点的带权路径长度之和 。 哈夫曼树是由 n个带权叶子结点构成的所有二叉树中带权路径长度 WPL最短的二叉树 。 5.2.5 哈夫曼树和哈夫曼编码 图 5.12 具有不同带权路径长度的二叉树 5.2.5 哈夫曼树和哈夫曼编码 构造哈夫曼树的算法步骤如下： (1) 用给定的 n个权值 w1， w2， ， wn对应的 n个结点构成 n棵二叉 树的森林 F=T1， T2， ， Tn， 其中每一棵二叉树 Ti(1 i n)都只 有一个权值为 wi的根结点 ， 其左 、 右子树为空 。 (2) 在森林 F中选择两棵根结点权值最小的二叉树 ， 作为一棵新二叉 树的左 、 右子树 ， 标记新二叉树的根结点权值为其左右子树的根结 点权值之和 。 (3) 从 F中删除被选中的那两棵二叉树 ， 同时把新构成的二叉树加入 到森林 F中 。 (4) 重复 (2)、 (3)的操作 ， 直到森林中只含有一棵二叉树为止 ， 此时 得到的这棵二叉树就是哈夫曼树 。 提示： 在哈夫曼树中 ， 权值越大的叶子结点离根越近 ， 权 值越小的叶子结点离根越远 。 5.2.5 哈夫曼树和哈夫曼编码 2. 哈夫曼编码 构造表示字符串的最优的二进制编码 ， 必须满足以下两个条件： 表示字符串的二进制编码一定是二进制前缀编码 。 在字符串中出现次数较多的字符采用尽可能短的编码 。 利用二叉树可以设计出二进制编码的前缀编码 ， 将需要编码的字符做为叶 子结点构造一棵二叉树 ， 并且约定二叉树的左分支表示的字符为 0， 右分 支表示的字符为 1， 则可以从根结点到叶子结点的路径分支上的 0、 1组成 的序列作为该叶子结点字符的编码 。 由于哈夫曼树中没有度为 l的结点 ， 则一棵有 n个叶子的哈夫曼树共有 2n 1个结点 ， 可以用一个大小为 2n 1的一维数组存放哈夫曼树的各个结点 。 构造算法 5.4， 参见教材 p85. 5.2.5 哈夫曼树和哈夫曼编码 _例 例 5-4 已知某系统在通讯联络中只可能出现 8种字符 ， 其出现的频率分别为 5 , 29 ， 7 ， 8 ， 14 ， 3 ， 23 和 11 ， 根据算法 5.4设计哈夫 曼编码 。 设表示字符的叶子结点权值为 w=5,29,7,8,14,3,23,11， n=8， 则 m=2n-1=15， 按照算法 5.4构造一棵哈夫曼树如图 5.14所示 。 其存储结构 HT的初始状态如图 5.15(a)所示 ， 终结状态如图 5.15(b)所示 ， 所得哈夫 曼编码如图 5.15(c)所示 。 图 5.14 例 5-4构造的哈夫曼树 5.2.5 哈夫曼树和哈夫曼编码 _例 图 5.15 例 5-4构造的哈夫曼树存储结构 5.3 树 和 森 林 5.3.1 树的存储结构 5.3.2 树、森林与二叉树的转换 5.3.3 树和森林的遍历 5.3.1 树的存储结构 1. 双亲表示法 树中每个结点的孩子可能有任意多个，但其双亲只有一个。双亲表示法 是通过结点与双亲之间的关系将树中结点组织在一起。该存储结构以一 组连续空间存储树的结点，同时在每个结点上附设一个指示器，指示其 双亲结点的位置。 2. 孩子表示法 孩子表示法是树的一种链式存储结构，其设计思想有两种，其一是建立 一个多重链表，存放树中每个结点及其多棵子树，即每个结点由一个数 据字段和多个指针字段组成，数据字段中存放该结点的数据元素，每个 指针字段中的指针指向一棵子树的根结点。 3. 孩子兄弟表示法 孩子兄弟表示法又称二叉树表示法，或二叉链表表示法。即以二叉链表 作为树的存储结构，链表中结点的两个字段分别指向该结点的第一个孩 子结点和下一个兄弟结点，分别命名为 firstchild字段和 nextsibling字段。 利用孩子兄弟表示法存储树，能方便地实现树的各种操作。特别是易于 实现查找某结点的孩子结点的运算。 5.3.1 树的存储结构 1. 双亲表示的存储结构类型定义如下： #define MAX 100 typedef struct PTNode TelemType data; int parent; /* 双亲位置字段 */ PTNode; typedef struct PTNode nodesMAX; int n; /* 结点数 */ PTree; 5.3.1 树的存储结构 2. 孩子链表存储结构类型定义如下： typedef struct CTNode /* 孩子结点 */ int child; struct CTNode *next; *ChildPtr; typedef struct TelemType data; ChildPtr firstchild; /* 孩子链表头指针 */ CTBox; typedef struct CTBox nodesMAX; int n, *r; /* 结点数和根的位置 */ CTree; 5.3.1 树的存储结构 图 5.17 孩子表示法 5.3.1 树的存储结构 3. 孩子兄弟表示法的结构 定义如下 ： typedef struct CSNode ElemType data; struct CSNode *firstchild; *nextsibling; CSNode,*CSTree; 5.3.2 树、森林与二叉树的转换 1.树与二叉树的转换 具体步骤如下： (1) 将树的根结点作为二叉树的根结点； (2) 对于树中的每个结点 ， 都将其第一个孩子结点作为该二叉 树结点的左子树 ， 将其第一个兄弟结点作为该二叉树结点 的右子树 。 若把森林中各树按从左到右的顺序依次变为二叉树 ， 再把 各棵二叉树从左到右依次合并 ， 将第二棵树的根结点看成 是第一棵树的根结点的兄弟 ， 即右边的二叉树作为左边二 叉树根的右子树 ， 则同样可以导出森林和二叉树的对应关 系 。 5.3.2 树、森林与二叉树的转换 2.森林与二叉树之间转换 森林转换成二叉树 如果 F=T1， T2， Tm 是森林，则可以按照如下规则转换 成一棵二叉树， B=root， LB， RB。 若 F为空，即 m=0，则 B为空二叉树； 若 F非空，即 m0，则 B的根 root即为森林中第一棵树的根 ROOT(T1)； B的左子树 LB是从 T1中根结点的子树森林 F1=T11， T12， ， T1m转换而成的二叉树； B的右子树 RB是从森林 F=T2， T3， ， Tm转换而成的二叉树。 5.3.2 树、森林与二叉树的转换 二叉树转换成森林 如果 B=root， LB， RB是一棵二叉树 ， 则可以按照如下 规则转换成森林 F=T1， T2， ， Tm。 若 B为空 ， 即 m=0， 则 F为空； 若 B非空 ， 即 m0， 则 F中第一棵树的根 ROOT(T1)即为的 二叉树的根 root； T1中根结点的子树森林 F1是由 B的左子 树 LB转换而成的森林； F中除 T1之外其余树组成的森林 F=T2， T3， ， Tm是由 B的右子树 RB转换而成的森林 。 5.3.3 树和森林的遍历 1.树的遍历 由树的结构定义可以得出树的遍历方法主要有两种：先根 (次序 )遍历和后根 (次序 )遍历 。 先根 (次序 )遍历 若树非空 ， 则遍历方法为首先访问根结点；然后从左到右 ， 依次先根遍历根结点的每一棵子树 。 例如：图 5.19中树的先 根遍历序列为 ABCDE。 后根 (次序 )遍历 若树非空 ， 则遍历方法为首先从左到右 ， 依次后根遍历根 结点的每一棵子树；然后访问根结点 。 例如：图 5.19中树的 后根遍历序列为 BDCEA。 5.3.3 树和森林的遍历 2.森林的遍历 森林的遍历方法主要有两种，即先序遍历和后序遍历。 先序遍历 若森林非空，则先序遍历方法为： 访问森林中第一棵树的根结点。 先序遍历第一棵中的根结点的子树森林。 先序遍历除去第一棵树之后剩余的树构成的森林。 后序遍历 若森林非空，则后序遍历方法为： 后序遍历森林中第一棵树的根结点的子树森林。 访问第一棵树的根结点。 后序遍历除去第一棵树之后剩余的树构成的森林。 5.4 上 机 实 习 5.4.1 实习 1 5.4.2 实习 2 5.4.1 实习 1 掌握二叉树的建立算法 ， 并利用递归实现中序遍历二叉树 。 题目：二叉树按照二叉链表方式存储 ， 编写算法 ， 将二叉树左右子树 进行交换 。 #define Null 0 typedef struct node int data; struct node *lchild,*rchild; bitree; bitree* creat() /*建立二叉树 */ bitree *t; 5.4.1 实习 1(2) int x; scanf(%d, if(x=0) t=Null; else t=(bitree*)malloc(sizeof(bitree); t-data=x; t-lchild=creat(); t-rchild=creat(); return t; /*creat*/ 5.4.1 实习 1(3) void inorder(bitree *t) /*中序遍历二叉树 */ if(t!=null) inorder(t-lchild); printf(%4d,t-data); inorder(t-rchild); /*inorder*/ void exchange(bitree *t) /*对二叉树 t中所有结点的左右子树进行交换 */ bitree *p; 5.4.1 实习 1(4) if(t!=null) p=t-lchild; t-lchild=t-rchild; t-rchild=p; exchang(t-lchild); exchang(t-rchild); /*exchange*/ main() bitree *root; 5.4.1 实习 1(5) printf(n); root=creat(); inorder(root); exchange(root); printf(n); inorder(root); /*main*/ 5.4.2 实习 2 利用非递归的方法 ， 层序遍历二叉树 。 题目：编写算法对以二叉链表存储的二叉树 ， 按层序遍历输出 。 #define M 100 #define Null 0 typedef struct node int data; struct node *lchild,*rchild; bitree; bitree *queM; int front=0,rear=0; bitree *creat() /*建立二叉树 */ 5.4.2 实习 2(2) bitree *t; int x; scanf(%d, if(x=0) t=Null; else t=(bitree*)malloc(sizeof(bitree); t-data=x; t-lchild=creat(); t-rchild=creat(); return t; /*creat*/ 5.4.2 实习 2(3) void inorder(bitree *t) /*中序遍历二叉树 */ if(t!=null) inorder(t-lchild); printf(%4d,t-data); inorder(t-rchild); /*inorder*/ void levorder(bitree *t) /*按层序遍历输出二叉树中各结点 */ 5.4.2 实习 2(4) bitree *quemax; int rear,front; if(t!=null) front=0; rear=1; que1=t; while(rear!=front); front=front%max+1; t=quefront; printf(%4d,t-data); if(t-lchild!=Null) 5.4.2 实习 2(5) rear=rear%max+1; querear=t-lchild; if(t-rchild!=Null) rear=rear%max+1; querear=t-rchild; /*levorder*/ 5.4.2 实习 2(6) main() bitree *root; printf(n); root=creat(); inorder(root); printf(n); levorder(root); /*main*/ 5.5 习 题 1 填空题 2 选择题 3 判断题 4 解答题 5 算法题 5.5 习 题 _填空题 1. 填空题： (1) 假定一棵树的嵌套括号表示法为 A(B(E)， C(F(H， I， J)， G)， D)， 则该树 的度为 _， 树的深度为 _， 终端结点的个数为 _， 单分支结点的个数为 _， 双分支结点的个数为 _， 三分支 结点的个数为 _， C结点的双亲结点为 _， 其孩子结点为 _和为 _结点 。 (2) 设 F是一个森林 ， B是由 F转换得到的二叉树 ， F中有 n个非终端结点 ， 则 B 中右指针字段为空的结点有 _。 (3) 对于一个具有 n个结点的二叉树 ， 当它为一棵 _二叉树时 ， 具有最 小高度 ， 即为 _， 当它为一棵单支树时具有为 _高度 ， 即 为 _。 (4) 对于一个具有 n个结点的二叉树 ， 当它存储在二叉链表中时 ， 其指针字段 的总数为 _个 ， 其中 _个用于链接孩子结点 ， _ 个空闲 。 5.5 习 题 _填空题 (5) 一棵深度为 k的满二叉树的结点总数为 _， 一棵深度为 k的完 全二叉树的结点总数的最小值为 _， 最大值为 _。 (6) 如果 T2是由有序树 T转换而来的二叉树 ， 那么 T中结点的前序就是 T2中 结点的 _序 。 (7) 如果 T2是由有序树 T转换而来的二叉树 ， 那么 T中结点的后序就是 T2中 结点的 _序 。 (8) 具有 n个结点的完全二叉树 ， 若按层次从上到下 、 从左到右对其编号 (根结点为 1号 )， 则编号最大的分支结点序号为 _， 编号最 小的分支结点序号为 _， 编号最大的叶子结点序号为 _， 编号最小的叶子结点序号为 _。 (9) 有 m个叶子结点的哈夫曼树 ， 其结点总数为 _。 (10) 由三个结点构成的二叉树 ， 共有 _种不同的结构 。 5.5 习 题 _选择题 2. 选择题 (1) 数组的基本操作主要包括 _。 A. 建立与删除 B. 索引与修改 C.访问与修改 D. 访问与索引 (2) 稀疏矩阵一般的压缩存储方法有两种 ， 即 _。 A. 二维数组和三维数组 B. 三元组和散列 C. 三元组和十字链表 D. 散列和十字链表 (3) 设二叉树有 n个结点 ， 则其深度为 _。 A. n-1 B. n C. +1 D.无法确定 (4) 设森林 T中有三棵树 ， 第一 、 二 、 三棵数的结点个数分别为 n1、 n2、 n3， 那么将森林转换成二叉树后 ， 其根结点的右子树上有 _个结点 。 A.n1-1 B.n2+n3 C.n1+n2+n3 D.n1 (5) 设森林 T中有三棵树 ， 第一 、 二 、 三棵数的结点个数分别为 n1、 n2、 n3， 那么将森林转换成二叉树后 ， 其根结点的左子树上有 _个结点 。 A.n1-1 B.n2+n3 C.n1+n2+n3 D.n1 (6) 设深度为 k的二叉树上只有度为 0或度为 2的结点 ， 则这类二叉树上所含结 点总数至少 _。 A.k+1 B. 2k C. 2k-1 D.2k+1 5.5 习 题 _选择题 (7) 树转换成二叉树后 ， 以下结论正确的是 _。 A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B.树的先根遍历序列与其对应的二叉树的中序遍历序列相同 C.树的后根遍历序列与其对应的二叉树的后序遍历序列相同 D.以上都不对 (8) 某二叉树的前序遍历结点访问顺序为 ABDGCEFH， 中序遍历结点访问顺序 为 DGBAECHF， 则其后序遍历结点访问顺序为 _。 A. BDGCEFHA B.GDBECFHA C. BDGAECHF D. GDBEHFCA (9) 在一棵非空二叉树的中序遍历序列中 ， 根结点的右边 _。 A. 只有右子树上的所有结点 B. 只有右子树上的部分结点 C. 只有左子树上的所有结点 D. 只有左子树上的部分结点 (10)任何一棵二叉树的叶结点在先序 、 中序和后序遍历序列中的相对次序 _。 A. 不发生变化 B. 发生变化 C. 不能确定 D. 以上都不对 5.5 习 题 _判断题 3. 判断题 (1) 一棵度为 2的树就是一棵二叉树。 ( ) (2) 无序树的子树没有顺序之分，而二叉树的子树分为左子树 和右子树。 ( ) (3) 给定二叉树的先序遍历序列和后序遍历序列，就能惟一地 确定一棵二叉树。 ( ) (4) 先根序列和中根序列相同的二叉树中任意一个结点都无左 孩子。 ( ) 5.5 习 题 _解答题 4. 解答题 (参见教材题目及图例 ) (1) 已知一棵树边的集合为 (I， M)， (I， N)， (E， I)， (B， E)， (B， D)， (A， B)， (G， J)， (G， K)， (C， G)， (C， F)， (H， L)， (C， H)， (A， C)，画出 这棵树，并回答下列问题： 哪个结点是根结点？ 哪些结点是叶子结点 ? 哪个结点是结点 G的双亲结点 ? 哪些结点是结点 G的祖先结点？ 哪些结点是结点 G的孩子结点 ? 哪些结点是结点 E的子孙结点 ? 哪些结点是结点 E的兄弟结点？哪些是结点 F的兄弟结点？ 结点 B和 N的层次分别是多少 ? 树的深度是多少 ? 以结点 C为根的子树的深度是多少 ? (2) 说明一棵度为 2的树与一棵二叉树之间的区别。 (3) 试分别画出具有 3个结点的树和具有 3个结点的二叉树的所有结构图。 (4) 对图 5.21所示的二叉树，写出此树的先序遍历、中序遍历和后序遍历的结 点序列。 5.5 习 题 _解答题 (5)按照下列给定二叉树的先序遍历序列、中序遍历序列和后序遍历序列， 分别构造出二叉树。 先序遍历序列： EBADCFHGIKJ 中序遍历序列： ABCDEFGHIJK 中序遍历序列： ACBGEDF 后序遍历序列： ABCDEFG (6) 分别画出图 5.22所示树的对应的二叉树。 (7) 对图 5.23所示的二叉树，分别画出它的顺序存储结构和二叉链表。 (8)对给定的权值 2,3,4,7,8,9，构造出相应的赫夫曼树和赫夫曼编码， 并求出带权路径的长度 WPL。 (9) 将图 5.24所示的二叉树转换成树。 5.5 习 题 _算法题 5. 算法题 (1) 假设二叉树中至多有一个结点的数据字段的值为 x， 编写算法 ， 摘除 以该结点为根的子树 ， 使原二叉树分为两棵二叉树 。 (2) 编写算法 ， 计算一棵以二叉链表表示的树的所有结点中度为 1的结点 个数 。 (3) 对以二叉链表表示的树编写计算树的深度的算法 。 (4) 设计算法 ， 将给定二叉树的叶子结点连成一个带头结点的单链表 ， 并 要求叶子结点按照从左到右的顺序插入 ， 而排列顺序为从右到左 (逆 置 )的单链表 。 (5) 设计一个算法 ， 求给定值 x的结点在二叉树中的所有祖先 ， 设树中值 为 x的结点不多于一个 。 Q E = (V 1 ， V 2 ) ， (V 1 ， V 4 ) ， (V 2 ， V 3 ) ， (V 2 ， V 5 ) ， (V 3 ， V 4 ) ， (V 3 ， V 5 ) 。 在有向图中，用尖括号表示两个顶点间的首尾关系，有向边也称为弧。有向边 中 V i 称为弧尾， V j 称为弧头。在有向图 G 2 中： G 2 =(V ， E) V = V l ， V 2 ， V 3 ， V 4 E= ， ， ， (a ) 无向图 G 1 (b) 有向图 G 2 图 6 . 1 图的类型 6.1.2 图的相关术语 图有以下术语： 1. 无向图 : 每条边都没有方向 (如图 6.1(a)的图称为无向图 。 2. 有向图 : 每条边都有方向 (如图 6.1(b)的图称为有向图 。 3. 无向完全图 : 任意两顶点间都有边的图称为无向完全图 。 在一 个含有 n个顶点的无向完全图中 ， 有 n(n-l)/2条边 。 4. 有向完全图 : 任意两顶点之间都有方向互为相反的两条弧相连 接的有向图称为有向完全图 。 在一个含有 n个顶点的有向完全图 中 ， 有 n(n-l)条弧 。 5. 稠密图 /稀疏图 : 若边数为 e， 顶点数为 n， 边数稀少到 en), printf(请输入顶点信息 (顶点号 )每个顶点以回车作为结束： n); for(i=0;in;i+) getchar();scanf(%C， for(i=0;in;i+) for(j=0;jn;j+) 6.3.1 图的邻接矩阵 (4) G-edgesij=0; printf(请输入每条边对应的两个顶点的序号 (输入格式为： i,j)： n); fork=0； ke； k+ getchar(); printf(请输入 %d条边的顶点序号： ,k+1); scanf(%c,%c, for(i=0;Ch2!=G-vexsi;i+); forj=0;Ch2!=G-vexsj;j+; G-edgesij=1; 6.3.2 邻接表 邻接表是一种顺序存储与链式存储结合的存储方法 。 1. 邻接表的实例 该实例中图的结构如图 6.7(a)所示 ， 图的邻接表如图 6.7(b)所示 。 2. 邻接表的数据类型 (算法 6.2) #define MAXLEN 10 / 最大顶点数为 10 typedef struct node / 边表结点 int adjvex; / 邻接点字段 struct node * next; /指向下一个邻接点的指针字段 / 若要表示边上信息 ， 则应增加一个数据字段 info EdgeNode; typedef struct vnode / 顶点表结点 6.3.2 邻接表 (2) VertexType vertex; / 顶点字段 EdgeNode firstedge; / 边表头指针 VertexNode; typedef VertexNode AdjListMAXLEN;/ AdjList是邻接表类型 typedef struct AdjList adjlist; / 邻接表 int n,e; / 顶点数和边数 ALGraph; / ALGraph是以邻接表方式存储的图类型 6.3.2 邻接表 (3) 3. 建立邻接表的算法 (算法 6.3) void CreateGraphAL(ALGraph *G) int I,j,k; EdgeNode * s; printf(请输入顶点数和边数 输入格式为：顶点数 ， 边数 ： n); scanf(%d,%d, /读入顶点数和边数 printf(请输入顶点信息 (输入格式为：顶点号 )每个顶点以回车 作为结束 :n); for(i=0;in； i+) /有 n个顶点的顶点表 scanf(n%c, /读入顶点信息 6.3.2 邻接表 (4) G-adjlisti.firstedge=NULL; /点的边表头指针设为空 printf(请输入边的信息 (输入格式为： I,j)： n); for(k=0； ke;k+) /建立边表 scanf(n%d,%d, /读入边 的顶点对应序号 s=new edgeNode; /生成新边表结点 s(也可为 s=(EdgeNode*)malloc (sizeof(EdgeNode) s-adjvex=j; /邻接点序号为 j s-next=G-adjlisti.firstedge; /新边表结点 s插入到顶点 Vi的边表头部 G-adjlisti.firstedge=s; 6.4 图 的 遍 历 图的遍历 是指从图中的某一顶点出发，对图 中的所有顶点访问一次，且仅访问一次。图 的遍历是图的一种基本操作。 6.4 图的遍历 (2) 6.4.1 深度优先搜索 6.4.2 广度优先搜索 6.4.1 深度优先搜索 深度优先搜索 (Depth First Search)遍历类似于树的先根遍历 ， 是树的 先根遍历的推广 。 深度优先搜索的方法： 首先访问出发点 V结点 ， 将其标记为已访问过； 依次从 V出发搜索 V的每个邻接点 W， 若 W未曾访问过 ， 则以 W为新 的出发点继续进行深度优先遍历； 直至图中所有与 V连通的顶点均已被访问过为止； 若此时图中仍有未访问过的结点 ， 则选一个未访问过的结点作为源 点重复上述操 作 ， 直至所有结点均已被访问 。 深度优先搜索的时间复杂度为 O(n+e)。 6.4.1 深度优先搜索 在邻接表的存储结构下进行深度优先搜索的算法 (算法 6.4)如下 : void DFSTraverseM(MGraph *G)； int visitedmax; /该值为 1时 ， 相应结点已被访问 ， 否则未被访问 int i; for(i=0;in;i+) visitedi=FALSE; /FALSE在 C语言中定义为 0， 以下同 for(i=0;in;i+) if(!visitedi) DFSM(G,i); void DFSM(MGraph *G， int i) int j; printf(tt深度优先遍历结点：结点 %cn， G-vexsi)； visitedi=TRUE; /TRUE在 C语言中定义为 0， 以下同 for(j=0;jn;j+) if(G-edgesij=1 6.4.2 广度优先搜索 广度优先搜索 (Breadth First Search)遍历类似于树的按层遍历 。 广度优先搜索的方法如下 : 首先访问出发点 V， 接着依次访问 V的所有邻接点 W1,W2,W3 ； 然后再依次访问与 W1,W2,W3 邻接的所有未访问过的顶点 ， 依次 类推； 直到所有连通的结点都已访问到为止； 若此时图中仍有未访问过的结点 ， 则选一个未访问过的结点作为源 点重复上述操 作 ， 直至所有结点均已被访问 。 广度优先搜索的时间复杂度为 O(n+e)。 6.4.2 广度优先搜索 在邻接表的存储结构下进行广度优 先搜索的算法 (算法 6.5)如下 : void BFSTraverseM(MGraph *G) int visitedmax; int I; for(i=0;in;i+) visitedi=FALSE; for(i=0;in;i+) if(!visitedi) BFSM(G,i); void BFSM(MGraph *G,int k) int i,i; CirQueue Q; InitQueue( /初始化 printf(广度优先遍历 ：结点 %cn,G-vexsk); visitedk=TRUE; EnQueue( while(!QueueEmpty( /出队 for(j=0;jn;j+) if(G-edgesij=1 visitedi=TRUE; EnQueue( /进队 6.5 生成树和最小生成树 6.5.1 生成树 6.5.2 最小生成树 6.5.1 生成树 构造生成树的方法有以下两种 : 1.深度优先生成树 使用深度优先搜索方法遍历一个连通图 ， 所经过的边和顶点成为一 棵树 ， 称为深度优先生成树 。 如图 6.8(a)所示 。 2.广度优先生成树 使用广度优先搜索方法遍历一个连通图 ， 所经过的边和顶点成为一 棵树 ， 称为广度优先生成树 。 如图 6.8(b)所示 。 (a) 图 G4的深度优先生成树 (b) 图 G4广度优先生成树 图 6.8 生成树 6.5.2 最小生成树 对加权的连通图 ， 去掉多余的边 ， 使图成为树 ， 树的枝上的权值的和 最小 ， 该树称为 最小生成树 。 1.构造最小生成树的 Prim方法 图 6.9是用 Prim方法构造最小生成树的过程 。 Prim方法： 从加权图中选取权值最小的边 ， 与该边相关联的顶点被选择； 从与被选择的顶点相关联的未被选择的边中选取权值最小的边 ， 若该 边使已经选 择的顶点和边构成圈 ， 则去掉该边； 重复步骤 ， 直到没有未被选择也未被去掉的边 ， 剩下的边和图的全 部顶点构成最小生成树 。 2. 构造最小生成树的 Kruskal方法 图 6.10是用 Kruskal方法构造最小生成树的过程。 图 6.9 用 Prim方法构造最小生成树的过程 (a) (b) (c) (d) (e) (f) 图 6.10 用 Kruskal方法构造最小生成树的过程 6.6 习 题 1 填空题 2 选择题 3 问答题 6.6 习 题 _填空题 1. 填空题 (1) 一个具有 n个顶点的完全图的边数为 _。 (2) 无向图中的连通分量定义为无向图的 _。 (3) 设无向图 G的顶点数为 n，则 G最少有 _条边。 (4) 一个具有 n个顶点的有向完全图的弧数为 _。 (5) 有向图中的强连通分量定义为有向图的 _。 6.6 习 题 _选择题 (1) 连通分量是 _的极大连通子图 。 A.无向图 B.有向图 C. 树 D.图 (2) 强连通分量是 _的极大连通子图 。 A.无向图 B.有向图 C. 树 D.图 (3) 有 n个顶点的无向图的邻接矩阵是用 _数组存储 。 A.n行 n列 B.一维 C.任意行 n列 D.n行任意列 (4) 有 n条边的无向图的邻接表存储法中 ， 链表中结点的个数是 _个 。 A. n B. 2n C. n/2 D. n*n (5) 某图的邻接表如图 6.11所示 。 从 V1顶点进行深度优先搜索 ， 搜索中要经过的顺序是 _。 A.V1.V2.V3 B.V1.V3.V4 C.V1.V2.V4 D.V1.V3.V5 从 V1顶点进行广度优先搜索 ， 搜索中要经过的顺序是 _。 A.V1.V2.V3 B.V1.V3.V4 C.V1.V2.V4 D.V1.V3.V5 6.6 习 题 _选择题 (6) 个加权的无向连通图的最小生成树 _。 A.有一棵或多棵 B. 只有一棵 C.一定有多棵 D. 可能不存在 (7) 下列有关图遍历的说法中不正确的是 _。 A.连通图深度优先搜索是个递归过程 B.图的广度优先搜索中邻接点的寻找具有 “ 先进先出 ” 的特征 C.非连通图不能用深度优先搜索法 D.图的遍历要求每一顶点仅被防问一次 (8) 无向图的邻接矩阵是一个 _。 A. 对称矩阵 B. 零矩阵 C.上三角矩阵 D.对角距阵 (9) 下列说法中正确的是 _。 A.一个具有 n个顶点的无向完全图的边数为 n(n-1) B.连通图的生成树是该图的一个极大连通子图 C.图的广度优先搜索是一个递归过程 D.在非连通图的遍历过程中 ， 每调用一次深度优先搜索算法都得到该图 的一个连通分量 (10) 如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点 ， 则该图一定是 _。 A.完全图 B.连通图 C.有回路 D.一棵树 6.6 习 题 _问答题 3. 问答题 (1) 假设图的顶点是 A， B， ， 请根据如图 6.12所示的邻接矩阵分别画 出相应的无向图或有向图 。 (2) 假设一棵完全图包含 A， B， ， G七个结点 ， 写出其邻接矩阵 。 (3) 假设一棵完全图包含 A， B， C， D四个结点 ， 画出其邻接表 。 (4) 按图 6.11的邻接表写出从 V6点出发进行广度优先搜索序列和深度优 先搜索序列 图 6.11 某图的邻接表 6.6 习 题 _问答题 (5) 按图 6.11的邻接表写出从 V1点出发进行广度优先搜索序列和深度优 先搜索序列 。 (6) 画出如图 6.13所示加权图的最小生成树 。 (7) 根据如图 6.14所示的有向图 ， 回答问题 。 该图是强连通图吗 ？ 若不是 ， 则给出其强连通分量 。 请给出两个有向环 。 请给出每个顶点的度 、 入度和出度 。 请给出其邻接表 、 邻接矩阵及逆邻接表 。 (8)已知一个无向图 G的邻接矩阵如图 6.15所示 ， 假设对其每行元素访问 时必须从右到左 ， 请写出从 V0开始的深度优先搜索的序列 。 (9) 已知某无向图 G的邻接矩阵如图 6.16所示 。 假设对其访问时每行元 素必须从右到左 ， 请画出其所有连通分量 。 (10)已知无向图 G的邻接表如图 6.17所示 ， 请画出其所有的连通分量 。 01010 00001 10001 01000 00110 0111 1011 1101 1110 (a) (b) 图 6.12 邻接矩阵 图 6.13 加权图 图 6.14 有向图 0 1 2 3 4 0 1 2 3