《计算机基础课件 第5章 树和二叉树》由会员分享，可在线阅读，更多相关《计算机基础课件 第5章 树和二叉树（206页珍藏版）》请在金锄头文库上搜索。
1、数据结构（C版） 树的逻辑结构 树的存储结构 二叉树的逻辑结构 二叉树的存储结构及实现 树、森林与二叉树的转换 哈夫曼树第 5 章 树和二叉树本章的主要内容是数据结构（C版）树的定义树：n（n0）个结点的有限集合。当n0时，称为空树；任意一棵非空树满足以下条件： 有且仅有一个特定的称为根的结点； 当n1时，除根结点之外的其余结点被分成m（ m0）个互不相交的有限集合T1,T2, ,Tm，其中每个集合又是一棵树，并称为这个根结点的子树。5.1 树的逻辑结构树的定义是采用递归方法数据结构（C版）(a) 一棵树结构 (b)一个非树结构 (c)一个非树结构 5.1 树的逻辑结构树的定义ACBGFEDH
2、IACBGFDACBGFDE数据结构（C版）树的应用举例文件结构5.1 树的逻辑结构My ComputerC:D:E:etcWINDOWSProgram FilesPictureMusic数据结构（C版）树的基本术语结点的度：结点所拥有的子树的个数。 树的度：树中各结点度的最大值。5.1 树的逻辑结构CGBDEFKLHMIJA数据结构（C版） 5.1 树的逻辑结构叶子结点：度为0的结点，也称为终端结点。 分支结点：度不为0的结点，也称为非终端结点。CGBDEFKLHMIJA树的基本术语数据结构（C版）孩子、双亲：树中某结点子树的根结点称为这个结点 的孩子结点，这个结点称为它孩子结点的双亲结点；
3、 兄弟：具有同一个双亲的孩子结点互称为兄弟。 5.1 树的逻辑结构CGBDEFKLHMIJA树的基本术语数据结构（C版）路径：如果树的结点序列n1, n2, , nk有如下关系：结 点ni是ni+1的双亲（1 struct PNode T data; /数据域int parent; /指针域，双亲在数组中的下标 ; PNode TreeMaxSize;data parent5.2 树的存储结构树的双亲表示法实质上是一个静态链表。双亲表示法数据结构（C版）下标 data parent0 1 2 3 4 5 6 7 8A -1B 0C 0D 1E 1F 1 G 2 H 2 I 4 5.2 树的存储
4、结构如何查找双亲结点？时间性能？双亲表示法ACBHFEDGI数据结构（C版） 5.2 树的存储结构双亲表示法ACBHFEDGI如何查找孩子结点？下标 data parentfirstchild136-18 -1 -1 -1 -10 1 2 3 4 5 6 7 8A -1B 0C 0D 1E 1F 1 G 2 H 2 I 4 数据结构（C版）下标 data parent rightsib-12 -145 -1 7 -1 -15.2 树的存储结构双亲表示法0 1 2 3 4 5 6 7 8A -1B 0C 0D 1E 1F 1 G 2 H 2 I 4 ACBHFEDGI如何查找兄弟结点？时间性能？
5、数据结构（C版）链表中的每个结点包括一个数据域和多个指针域， 每个指针域指向该结点的一个孩子结点。 如何确定链表中的结点结构？5.2 树的存储结构5.2.2孩子链表表示法方案一：指针域的个数等于树的度data child1 child2 childd其中：data：数据域，存放该结点的数据信息；child1childd：指针域，指向该结点的孩子。 （1）多重链表表示法数据结构（C版） 5.2 树的存储结构缺点：浪费空间ACBHFEDGIABCDEFGHI 适用于树中各结点的度相差不大的情况数据结构（C版） 5.2 树的存储结构方案二： 指针域的个数等于该结点的度data degree chil
6、d1 child2 childd其中：data：数据域，存放该结点的数据信息；degree：度域，存放该结点的度；child1childd：指针域，指向该结点的孩子。 数据结构（C版） 5.2 树的存储结构缺点：结点结构不一致ACBHFEDGIA 2B 3C 2E 1I 0G 0H 0F 0D 0没有空指针，空间利用率高数据结构（C版）孩子链表表示法基本思想：把每个结点的孩子排列起来，看成是一个 线性表，且以单链表存储，则n个结点共有 n 个孩子 链表。这 n 个单链表共有 n 个头指针，这 n 个头指 针又组成了一个线性表，为了便于进行查找采用顺序 存储。最后，将存放 n 个头指针的数组和存
7、放n个结 点的数组结合起来，构成孩子链表的表头数组。 5.2 树的存储结构将结点的所有孩子放在一起，构成线性表。（2）孩子链表表示法-指向第一个孩子数据结构（C版）ACBHFEDGI0 1 2 3 4 5 6 7 8下标 data firstchildA B C DE FG H I 5.2 树的存储结构如何查找孩子结点？时间性能？12 345 7 68 数据结构（C版）child next孩子结点struct CTNode int child;CTNode *next; ;5.2 树的存储结构template struct CBNode T data;CTNode *firstchild; ;
8、孩子链表表示法data firstchild表头结点数据结构（C版）ACBHFEDGI0 1 2 3 4 5 6 7 8下标 data firstchildA B C DE FG H I 5.2 树的存储结构12 345 7 68 如何查找双亲结点？时间性能？数据结构（C版）5.2.3 双亲孩子表示法（前两种方法的结合）5.2 树的存储结构0 1 2 3 4 5 6 7 8A -1B 0C 0D 1 E 1F 1 G 2 H 2 I 4 data parent firstchild 12 345 7 68 ACBHFEDGI数据结构（C版）5.2.4 孩子兄弟表示法5.2 树的存储结构ACBH
9、FEDGI某结点的第一个孩子是惟一的 某结点的右兄弟是惟一的设置两个分别指向该结点的 第一个孩子和右兄弟的指针 数据结构（C版）template struct TNode T data;TNode *firstchild, *rightsib; ;5.2 树的存储结构结点结构firstchild data rightsibdata：数据域，存储该结点的数据信息； firstchild：指针域，指向该结点第一个孩子； rightsib：指针域，指向该结点的右兄弟结点。 孩子兄弟表示法数据结构（C版） 5.2 树的存储结构孩子兄弟表示法ACBHFEDGIAB CD E F G HI如何查找兄弟结点
10、？时间性能？数据结构（C版） 5.2 树的存储结构孩子兄弟表示法ACBHFEDGIAB CD E F G HI如何查找孩子结点？时间性能？数据结构（C版） 5.2 树的存储结构孩子兄弟表示法ACBHFEDGIAB CD E F G HI如何查找双亲结点？时间性能？数据结构（C版）二叉树的定义 二叉树是n（n0）个结点的有限集合，该集合或 者为空集（称为空二叉树），或者由一个根结点 和两棵互不相交的、分别称为根结点的左子树和 右子树的二叉树组成。5.3 二叉树的逻辑结构问题转化：将树转换为二叉树，从而利用二叉树解 决树的有关问题。研究二叉树的意义？注意！ 二叉树不是树的 特例！数据结构（C版）二
11、叉树的特点： 每个结点最多有两棵子树； 二叉树是有序的，其次序不 能任意颠倒。 5.3 二叉树的逻辑结构注意：二叉树和树是两种树结构。ABCDEFGABAB数据结构（C版）二叉树的基本形态空二叉树只有一个根结点左子树根结点只有左子树右子树根结点只有右子树左子树右子树根结点同时有左右子树5.3 二叉树的逻辑结构数据结构（C版） 5.3 二叉树的逻辑结构具有3个结点的树和具有3个结点的二叉树的形态v二叉树和树是两种树结构。数据结构（C版）特殊的二叉树斜树 1 .所有结点都只有左子 树的二叉树称为左斜树； 2 .所有结点都只有右子 树的二叉树称为右斜树； 3.左斜树和右斜树统称为 斜树。1. 在斜树
12、中，每一层只有一个结点；2.斜树的结点个数与其深度相同。 5.3 二叉树的逻辑结构斜树的特点：ABCABC数据结构（C版）满二叉树在一棵二叉树中，如果所 有分支结点都存在左子树 和右子树，并且所有叶子 都在同一层上。满二叉树的特点：1. 叶子只能出现在最下一层；2. 只有度为0和度为2的结点。5.3 二叉树的逻辑结构特殊的二叉树A15234678910BCDEFGHIJKLM NO 1112 13 14 15数据结构（C版）满二叉树5.3 二叉树的逻辑结构不是满二叉树，虽然 所有分支结点都有左 右子树，但叶子不在 同一层上。满二叉树在同样深度的二叉树中结点个数最多 满二叉树在同样深度的二叉树中
13、叶子结点个数最多A1523467BCDEFGLM 89特殊的二叉树数据结构（C版）完全二叉树对一棵具有n个结点的二叉树按层序编号，如果编 号为i（1in）的结点与同样深度的满二叉树中编 号为i的结点在二叉树中的位置完全相同。5.3 二叉树的逻辑结构特殊的二叉树A15234678910BCDEFGHIJKLM NO 1112 13 14 15 A15234678910BCDEFGHIJ数据结构（C版）在满二叉树中，从最后 一个结点开始，连续去 掉任意个结点，即是一 棵完全二叉树。5.3 二叉树的逻辑结构A1523467910BCDEFGHIJK 11L 12M 13N 14O 158 A15234678910BCDEFGHIJ不是完全二叉树，结点 10与满二叉树中的结点 10不是同一个结点特殊的二叉树数据结构（C版）1. 叶子结点只能出现在最下 两层，且最下层的叶子结点 都集中在二叉树的左部； 2. 完全二叉树中如果有度为 1的结点，只可能有一个， 且该结点只有左孩子。3. 深度为k的完全二叉树在 k-
