《数据结构——用C语言描述(第二版)》-宁正元-电子教案 第6章 树
90页1、6.1 树的基本概念 6.2 二叉树 6.3 遍历二叉树 6.4 线索二叉树 6.5 树和森林 6.6 哈夫曼树,第6章 树,树形结构是一种应用十分广泛和重要的非线性数据结构,是一种以分支关系定义的层次结构。在这种结构中,每个数据元素至多只有一个前趋,但可以有多个后继;数据元素之间的关系是一对多的层次关系。树形结构主要用于描述客观世界中具有层次结构的数据关系。 本章重点讨论树与二叉树的概念、性质、存贮结构及其各种运算,并研究一般树、森林和二叉树的转换关系;此外,作为树形结构的应用,介绍了哈夫曼树及其哈夫曼编码。,第6章 树,6.1.1 树的定义及表示 1、树形结构示例,6.1 树的基本概念,2、树的定义 树(Tree)是n(n0)个结点的有限集合T,当n=0时称为空树,否则,称为非空树。在任一棵非空树中: (1)有且仅有一个称为树根的结点。 (2)除根结点之外的其余结点可分为m(m0)个互不相交的集合T1,T2,Tm,其中每一个集合本身又都是一棵树,一般称为根的子树。 树的定义是一个递归的定义,它反映了树的固有特性,即一棵树由若干棵子树构成,且各子树间互不相交,而每棵子树又由若干棵更小
2、的子树构成。例如,在图6.2中,(a)是只有一个根结点的树;(b)是有8个结点的一般树,其中A是根,其余结点分成三个互不相交的子集:T1=B、E、F,T2 =C,T3=D、G、H,而且它们都是A的子树,且其本身也是一棵树。,3、树的表示 树的表示方法有树形表示、集合表示、凹入表示和广义表等4种。图6.3给出了树的其它表示形式,如(a)为集合表示法或范氏图法,(b)为凹入表示法或缩格法,(c)为广义表表示法或嵌套括弧法等。,6.1.2 树的常用术语 树的结点:是指一个数据元素及若干指向其子树的分支,通常用一个结构体或记录来描述,在树形表示中用一个圆圈及短线表示。 结点的度:是指结点的子树数目。 叶子或终端结点:是指度为零的结点。 分支结点或非终端结点:是指度不为零的结点。 树的度:是指树中各结点度的最大值。 有时,在实际应用中也引用家族树中的一些习惯用语来描述树,如孩子、双亲、祖先、子孙和兄弟等。如将某结点的子树的根称为该结点的孩子,相应地,将该结点称为孩子的双亲;同一个双亲的孩子之间互称为兄弟等等。祖先则是从根结点到该结点所经过分支上的所有结点,而以某结点作为根的子树中任一个结点都称为
3、该结点的子孙。,结点的层次:从根开始定义,根为第一层,根的孩子为第二层,以此类推,即设根结点的层数为1,其余结点的层数等于其双亲结点的层数加1。若某结点在第i层,则其孩子结点就在第i+1层。 树的深度或高度:是指树中结点的最大层次数。 路径:若树中存在一个结点序列k1,k2,kj,使得ki是k i1的双亲(1ij),则称该结点序列是从k1到kj的一条路径,且路径的长度为j-1,即等于路径上分支的数目。在树形表示中,路径表示从k1出发自上而下地通过k2,k3,kj各结点。 有序树和无序树:若将树中每个结点的各子树看成是从左至右有序且不能交换,则称该树为有序树,否则称为无序树。图6.4给出了两棵不同的有序树。,图6.4 两棵不同的有序树,森林:是指m(m0)棵互不相交的树的集合。 显然,树形结构不同于线性结构。在树中,一个结点至多只有一个直接前趋(双亲),却可以有多个直接后继(孩子),即结点之间的关系不象线性结构中的结点关系是一一对应关系,而是呈现出一对多的层次关系。,6.1.3 树的基本运算 (1)setnull(T) :置T为空树,即初始化一棵树T。 (2)root(T)或root(x
4、):求根函数。 (3)parent(T,x):求双亲函数。 (4)child(T,x,i):求孩子结点函数。 (5)rsibling(T,x):求右兄弟函数。 (6)create(x,F):建树函数。 (7)delchild(x,i):子树删除操作。 (8)addchild(y,i,x):插入子树操作。 (9)traverse(T):树的遍历操作。,二叉树(Binary Tree)是另一种重要的树形结构,在实际应用中具有重要的意义。本节将详细地讨论二叉树的定义、重要性质、存储方式、运算及其应用。,6.2 二叉树,6.2.1 二叉树的概念及运算 1、二叉树定义 二叉树是n(0)个结点的有限集合,这个集合可以是空集合,或者由一个根结点和两棵互不相交的分别称为根的左子树和右子树的二叉树组成。显然,由定义可知,二叉树具有递归性质,它的特点是每个结点至多只有二棵子树即二叉树中任何结点的度数不大于2,而且,二叉树的子树有左右之分,其次序不能任意颠倒。应该指出的是,二叉树与树是两个不同的概念,它不是树的特殊情形,例如,在图6.5中,(a)和(b)所示的两棵二叉树虽然与(c)所示的一般树相似,但却不等
《《数据结构——用C语言描述(第二版)》-宁正元-电子教案 第6章 树》由会员E****分享,可在线阅读,更多相关《《数据结构——用C语言描述(第二版)》-宁正元-电子教案 第6章 树》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课3稿
当代大学生人生信仰及追求的调查研究
长相思 纳兰性德-ppt课件
课件:危机意识 一
英语ppt演讲关于阿甘正传
发达国家基础教育改革的动向与趋势 修改版
中国民间美术 课件.ppt
生物质发电技术与系统 课程ppt 第1章 生物质发电技术现状及发展趋势 2学时 -----2016
现代信号处理思考题 含答案
执业药师继续教育 抑郁症的药物治疗 100分
小学生的成长档案模板不用修改 万能型
增订六版 现代汉语 上册 第二章文字 思考与练习答案
国家财政ppt课件
加拿大英语介绍
六年级统计图的选择课件
中学生成长档案ppt
中国现代文学史期末复习整理
lohi和hihilo训练对女子赛艇运动员运动能力影响的比较研究
风雨贾平凹阅读答案
2024-03-21 39页
2024-03-21 41页
2024-03-21 40页
2024-03-21 34页
2024-03-21 33页
2024-03-21 35页
2024-03-21 21页
2024-03-21 45页
2024-03-21 33页
2024-02-20 85页