《《数据结构（C语言版）》电子教案－赵坚 数据结构06》由会员分享，可在线阅读，更多相关《《数据结构（C语言版）》电子教案－赵坚 数据结构06（89页珍藏版）》请在金锄头文库上搜索。
1、2019/5/25,1,第6章 树和二叉树,本章主题：树、二叉树 教学目的：掌握树和二叉树的类型定义、运算及存储结构 教学重点：树的各种表示、各种存储方式和运算， 二叉树的概念及其运算和应用 教学难点：二叉树的非递归运算及应用 主要内容：树 二叉树 树、森林与二叉树的转换 树的应用,2019/5/25,2,本章学习导读,本章主要介绍树的基本概念，树的存储结构，树和二叉树的遍历等一些常用算法。通过本章学习，读者应该： 1) 熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作。 2) 理解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。 3) 熟练掌握二叉树
2、和树的各种存储结构及建立的算法。 4) 学会编写实现树的各种操作的算法。 5)了解最优二叉树的特性，掌握建立最优二叉树和哈夫曼编码的方法。,2019/5/25,3,数据结构:线性结构和非线性结构 线性结构(线性表, 栈,队列等) 非线性结构: 至少存在一个数据元素有不止一个直接前驱或后继(树,图等) 树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界国是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在
3、分析算法的行为时，可用树来描述其执行过程。等等。,2019/5/25,4,6.1 .1 树型结构实例 1家族树,6.1 树的逻辑结构和存储结构,图6-1 家族树,2019/5/25,5,2书的目录结构,图6-2 书的目录,2019/5/25,6,6.1 .2 树的定义 1树的定义 树(Tree)是n (n0)个结点的有限集(记为T)，T为空时称为空树，否则它满足以下两个条件： (1) 有且仅有一个结点没有前驱，称该结点为根结点(Root)； (2) 除根结点以外，其余结点可分为m(m0)个互不相交的有限集合T0，Tl，Tm-1。其中每个集合又构成一棵树，树T0，Tl ，Tm-1被称为根结点的子
4、树(Subree)。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个后继。 树的逻辑结构表示数据之间的关系是一对多，或者多对一的关系。它的结构特点具有明显的层次关系，是一种十分重要的非线性的数据结构。,6.1 树的逻辑结构和存储结构,2019/5/25,7,图6-3 树的示例,图6-3 (a)是一棵只有一个根结点的树； 图6-3 (b)是一棵有12个结点的树，即T=A，B，C，K，L 。A是棵根，除根结点A之外，其余的11个结点分为三个互不相交的集合。T1，T2和T3是根A的三棵子树，且本身又都是一棵树。所以树的定义是递归的 。,返回,2019/5/25,8,2树的基本术语 树的结点包
5、含一个数据元素及若干指向其子树的分支。 1. 树的结点:包含一个DE和指向其子树的所有分支; 2. 结点的度:一个结点拥有的子树个数,度为零的结点称为叶结点; 3. 树的度:树中所有结点的度的最大值 Max(D(I) 含义:树中最大分支数为树的度; 4. 结点的层次及树的深度:根为第一层,根的孩子为第二层,若某结点为第k层,则其孩子为k+1层. 树中结点的最大层次称为树的深度或高度 5.森林:是m(m=0)棵互不相的树的集合 森林与树概念相近,相互很容易转换. 6 .有序树、无序树 如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。,2019/5/25,9,
6、7.森林: 是m（m0）棵互不相交的树的集合。 在树结构中，结点之间的关系又可以用家族关系描述，定义如下： 8.孩子、双亲: 结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。 9.子孙: 以某结点为根的子树中的所有结点都被称为是该结点的子孙。 10.祖先: 从根结点到该结点路径上的所有结点。 11.兄弟: 同一个双亲的孩子之间互为兄弟。 12.堂兄弟: 双亲在同一层的结点互为堂兄弟。,2019/5/25,10,3. 树的基本运算 树的基本运算主要有： 初始化操作INITIATE(T)：创建一棵空树。 求根函数ROOT(T)：求树T的根；ROOT(X)：求结点x所在树的根。 求双亲
7、函数PARENT(T,x)：在树T中求x的双亲。 求第i个孩子函数CHILD(T,x,i)：在树T中求结点x的第i个孩子。 建树函数CRT-TREE(x,F)：建立以结点x为根，森林F为子树的树。 6.遍历树操作TRAVERSE(T)：按顺序访问树T中各个结点。,2019/5/25,11,6.1.3 树的表示 树的逻辑表示方法有多种，常见的有 ： 1 树形图表示法 2 嵌套集合表示法（文氏图表示法） 3 凹入表示法 4 广义表表示法,2019/5/25,12,6.1.3 树的存储结构 和线性表一样，树可以用顺序和链式两种存储结构。 树的顺序存储结构适合树中结点比较“满”的情况。根据树的非线性结
8、构特点，常用链式存储方式来表示树。树常用的存储方法有：双亲存储表示法、孩子链表表示法和孩子兄弟链表表示法。 1双亲存储表示法 一般采用顺序存储结构实现。用一组地址连续的存储单元来存放树的结点，每个结点有两个域： data域-存放结点的信息； parent域-存放该结点双亲结点的位置,特点：求结点的双亲很容易，但求结点的孩子需要遍历整个向量。,2019/5/25,13,存储结构描述为： #define MaxTreeSize 100 /定义数组空间的大小 typedef char DataType； /定义数据类型 typedef struct DataType data； /结点数据 int
9、parent； /双亲指针，指示结点的双亲在数组中的位置 PTreeNode； typedef struct PTreeNode nodesMaxTreeSize; int n； /结点总数 PTree； PTree T； /T是双亲链表,2019/5/25,14,2孩子链表表示法 这是树的链式存储结构。每个结点的孩子用单链表存储，称为孩子链表。 n个结点可以有n个孩子链表（叶结点的孩子链表为空表）。 n个孩子链表的头指针用一个向量表示。,图6-6 树的孩子链表结构,头指针向量 孩子链表,特点：与双亲相反，求孩子易，求双亲难。,2019/5/25,15,存储结构描述为： typedef str
10、uct CTNode int child; /孩子链表结点 struct CTNode *next; *ChildPtr; typedef struct /孩子链表头结点 ElemType data; /结点的数据元素 ChildPtr firstchild; /孩子链表头指针 CTBox; typedef struct CTBox nodesMaxTreeSize; int n, r, /数的结点数和根结点的位置 CTree;,2019/5/25,16,孩子链表表示法的类型说明 typedef struct Cnode /DataType和MaxTreeSize由用户定义 /孩子链表结点 i
11、nt child; /孩子结点在数组中对应的下标 struct CNode *next; Cnode; typedef struct /孩子链表头结点 DataType data; /存放树中结点数据 CNode *firstchild; /孩子链表的头指针 PTNode; typedef struct PTNode nodesMaxTreeSize; Int n,root; /树的结点数和根结点的位置 Ctree; Ctree T; /T的孩子链表表示,2019/5/25,17,3孩子兄弟链表表示法 孩子兄弟链表表示法也是树的一种链式存储结构。用二叉链表作为树的存储结构，每个结点的左链域指向
12、该结点的第一个孩子，右链域指向下一个兄弟结点。 由于结点中的两个指针指示的分别为“孩子”和“兄弟”，故称为“孩子-兄弟链表”。这种结构也称为二叉链表。,图6-7 树的孩子-兄弟存储结构,特点：双亲只管长子 长子连接兄弟,2019/5/25,18,树的孩子兄弟链表的存储结构描述为： typedef struct CSNode ElemType data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree; 孩子兄弟存储结构的最大优点是可以方便地实现树和二叉树的相互转换和树的各种操作。但是，孩子兄弟存储结构的缺点也是查找当前结点的双亲
13、结点比较麻烦，需要从树根结点开始逐个结点比较查找。,2019/5/25,19,6.1.5 树和森林的遍历 1树的遍历 所谓树的遍历，就是按照某种顺序依次访问树中各个结点，并使得每个结点只被访问一次。也就是把非线性结构的树结点变成线性序列的一种方式 。 树的遍历可以按深度优先遍历，也可以按照广度优先（按层次）遍历。深度优先遍历通常有两种方式：前序遍历和后序遍历。 (1) 前序遍历的递归定义： 若树T非空，则： 访问根结点R； 按照从左到右的顺序依次前序遍历根结点R的各子树T1，T2，Tk。,2019/5/25,20,(2) 后序遍历的递归定义： 若树T非空，则： 按照从左到右的顺序依次后序遍历根
14、T的各子树Tl，T2，Tk； 访问根结点R。 (3) 广度优先（按层）遍历 广度优先（按层次）遍历定义为：先访问第一层结点（即树根结点），再从左至右访问第二层结点，依次按层访问，直到树中结点全部被访问为止。对图6-6 (a)中的树进行按层次遍历得到树的广度优先遍历序列为：ABCDEFG。 说明： 前序遍历一棵树恰好等价于前序遍历该树所对应的二叉树。（6.2节将介绍二叉树） 后序遍历树恰好等价于中序遍历该树所对应的二叉树。,2019/5/25,21,树的先序遍历算法描述如下： void Preorder(Btree *root) /先根遍历k叉树 if (root!=NULL) printf(“
15、%cn”,root-data); /访问根结点 for(i=0;iti); /递归前序遍历每一个子结点 ,2019/5/25,22,2森林的遍历 森林的深度优先遍历通常也有两种方式：前序遍历和后序遍历。 (1) 前序遍历森林 若森林非空，则： 访问森林中第一棵树的根结点； 前序遍历第一棵树中根结点的各子树所构成的森林 前序遍历去掉第一棵树外其它树构成的森林。 (2) 后序遍历森林 若森林非空，则: 后序遍历森林中第一棵树中根结点的各子树所构成的森林； 访问第一棵树的根结点； 后序遍历去掉第一棵树外其它树构成的森林。 当用二叉链表作为树和森林的存储结构时，树和森林的前序遍历和后序遍历可用二叉树的前序遍历和中序遍历算法来实现。,2019/5/25,23,2森林的遍历 森林的深度优先遍历通常也有两种方式：前序遍历和后序遍历。 (1) 前序遍历森林 若森林非空，则： 访问森林中第一棵树的根结点； 前序遍历第一棵树中根结点的各子树所构成的森林 前序遍历去掉第一棵树外其它树构成的森林。 (2) 后序遍历森林 若森林非空，则: 后序遍历森林中第一棵树中根结点的各子树所构成的森林； 访问第一棵树的根结点； 后序遍历去掉第一棵树外其它树构成的森林。,2019/5/25,24,图6-8 森林和对应的二叉树,2019/5
