![数据结构课件:树和二叉树-1_第1页](http://file4.renrendoc.com/view/4597b15f5067bf46779c526ce17611e6/4597b15f5067bf46779c526ce17611e61.gif)
![数据结构课件:树和二叉树-1_第2页](http://file4.renrendoc.com/view/4597b15f5067bf46779c526ce17611e6/4597b15f5067bf46779c526ce17611e62.gif)
![数据结构课件:树和二叉树-1_第3页](http://file4.renrendoc.com/view/4597b15f5067bf46779c526ce17611e6/4597b15f5067bf46779c526ce17611e63.gif)
![数据结构课件:树和二叉树-1_第4页](http://file4.renrendoc.com/view/4597b15f5067bf46779c526ce17611e6/4597b15f5067bf46779c526ce17611e64.gif)
![数据结构课件:树和二叉树-1_第5页](http://file4.renrendoc.com/view/4597b15f5067bf46779c526ce17611e6/4597b15f5067bf46779c526ce17611e65.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
对于线性数据结构,每个元素都有唯一的前驱(第一个除外)和后继(最后一个除外),但是在现实应用中,一些问题的数据元素之间的关系就不这样简单。
本章学习一种非线性数据结构-----树,数据元素之间是一种层次关系,元素有且只有一个前驱,但可以有多个后继树和二叉树树的概念和基本术语二叉树二叉树遍历线索二叉树树与森林霍夫曼树
树和二叉树1树的概念和基本术语树的定义
树是由n(n0)个结点的有限集合。如果n=0,称为空树;如果n>0,则
有且仅有一个特定的称之为根(Root)的结点,它只有直接后继,但没有直接前驱;
当n>1,除根以外的其它结点划分为m(m>0)个互不相交的有限集
T1,T2,…,Tm,其中每个集合本身又是一棵树,并且称为根的子树(SubTree)ACGBDEFKLHMIJ例如A只有根结点的树有13个结点的树其中:A是根,其余结点分成三个互不相交的子集,T1={B,E,F,K,L};T2={C,G};T3={D,H,I,J,M},T1,T2,T3都是根A的子树,且本身也是一棵树树的基本术语树的结点:包含一个数据元素及若干指向子树的分支;孩子结点:结点的子树的根称为该结点的孩子双亲结点:B结点是A结点的孩子,则A结点是B结点的双亲ACGBDEFKLHMIJ兄弟结点:同一双亲的孩子结点
堂兄结点:双亲在同一层的结点互为堂兄弟结点层次
:根结点的层定义为1根的孩子为第二层结点依此类推ACGBDEFKLHMIJ树的基本术语树的高度(或深度):树中结点的最大层次结点的度:结点子树的个数树的度:树内各结点的度的最大值叶子结点:也叫终端结点,是度为0的结点分枝结点:也叫非终端结点,度不为0的结点有序树:子树有序的树,(子树不能互换)如:家族树无序树:不考虑子树的顺序ACGBDEFKLHMIJ树的基本术语路径:树中的k个结点n1,n2,…,nk,满足ni
是ni+1的双亲,n1到nk有一条路径路径长度:分支数=路径上结点个数一1根没有双亲,叶子没有孩子;vi是vj
的双亲,则L(vi)=L(vj)-1;
堂兄弟的双亲是兄弟关系吗?有序树和无序树的区别注意ACGBDEFKLHMIJ任何一棵非空树是一个二元组
Tree=(root,F)其中:root被称为根结点,
F被称为子树森林是m(m≥0)棵互不相交的树的集合ArootBEFKLCGDHIJMF森林对比树型结构和线性结构的结构特点~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~线性结构树型结构第一个数据元素
(无前驱)
根结点
(无前驱)最后一个数据元素
(无后继)多个叶子结点
(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)树的常见表示方法1.直观表示法:用圆圈表示结点,元素写在圆圈中,连线表示元素之间的关系.根在上,叶子在下(即树向下生长)2、集合表示法:根据树的集合定义,写出集合划分
3、文氏图表示法:
集合表示的一种直观表示,用图表示集合树的常见表示法4、目录表示法:
将一棵树描述为一本书,书--章--节--小节树的常见表示法5、广义表表示法:将一棵树描述为一个广义表,子树就对应子表人们最常用的是第一种,但是不适合计算机!树的常见表示法树的基本操作
InitTree(&T)操作结果:构造空树T。
DestroyTree(&T)初始条件:树T存在。操作结果:销毁树T。
CreateTree(&T,definition)初始条件:definition给出树T的定义。操作结果:按definition构造树T。
ClearTree(&T)初始条件:树T存在。操作结果:将树T清为空树树的基本操作
TreeEmpty(T)初始条件:树T存在。操作结果:若T为空树,则返回ture,否则false。
TreeDepth(T)初始条件:树T存在。操作结果:返回T的深度。
Root(T)初始条件:树T存在。操作结果:返回T的根。
Value(T,Cur_e)初始条件:树T存在,cur_e是T中某个结点。操作结果:返回cur_e的值Assign(T,cur_e,value)初始条件:树T存在,cur_e是T中某个结点。操作结果:结点cur_e赋值为value。
Parent(T,cur_e)初始条件:树T存在,cur_e是T中某个结点。操作结果:若cur_e是T的非根结点,则返回它的双亲,否则函数值为“空”。
Rightsibling(T,cur_e)初始条件:树T存在,cur_e是T中某个结点操作结果:若cur_e有右兄弟,则返回它的右兄弟,否则函数值为“空”。
InsertChild(&T,&p,i,c)初始条件:树T存在,p指向T中某个结点,1≤i≤p所指结点的度+1,非空树c与T不相交。操作结果:插入c为T中p指结点的第i棵子树。DeleteChild(&T,&p,i)初始条件:树T存在,p指向T中某个结点,1≤i≤p指结点的度。操作结果:删除T中p所指结点的第i棵子树。
TraverseTree(T,visit())初始条件:树T存在,visit是对结点操作的应用函数。操作结果:按某种次序对T的每个结点调用函数visit()一次且至多一次.一旦visit()失败,则操作失败LeftChild(T,cur_e)
初始条件:树T存在,cur_e是T中某个结点。操作结果:若cur_e是T的非叶子结点,则返回它的最左孩子,否则返回“空”
6.2二叉树一二叉树的概念二二叉树的性质三二叉树的存储结构定义:二叉树或为空树;或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成ABCDEFGHK根结点左子树右子树2二叉树(BinaryTree)特点:每个结点至多只有两棵子树(二叉树中不存在度大于2的结点)二叉树的五种基本形态N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树应用举例
e
d
c
b
f
a
+
*
/
-
-
a+b*(c-d)-e/f例可以用二叉树表示表达式性质1 在二叉树的第i层上至多有2i-1个结点(i
1)
[证明用归纳法]证明:当i=1时,只有根结点,2i-1=20=1。假设对所有j,i>j1,命题成立,即第j层上至多有2j-1
个结点。由归纳假设第i-1
层上至多有2i-2个结点。由于二叉树的每个结点的度至多为2,故在第i层上的最大结点数为第i-1层上的最大结点数的2倍,即2*2i-2=2i-1。性质性质2 深度为k的二叉树至多有2k-1个结点(k1)证明:由性质1可见,深度为k的二叉树的最大结点数为
=20+21+…+2k-1=2k-1=性质3 对任何一棵二叉树T,如果其叶结点数为n0,度为2的结点数为n2,则n0=n2+1.证明:若度为1的结点有n1
个,总结点个数为n,总边数为e,则根据二叉树的定义,
n=n0+n1+n2e=2n2+n1=n-1因此,有2n2+n1=n0+n1+n2
-1n2=n0
-1n0=n2+1定义1满二叉树(FullBinaryTree)
一棵深度为k且有2k-1个结点的二叉树称为满二叉树两种特殊形态的二叉树6217543891011131412满二叉树152154367216543非完全二叉树定义2完全二叉树(CompleteBinaryTree)
若设二叉树的高度为h,则共有h层。除第h层外,其它各层(0h-1)的结点数都达到最大个数,第h层从右向左连续缺若干结点,这就是完全二叉树。621754389101112完全二叉树性质4
具有n(n0)个结点的完全二叉树的深度为log2(n)+1
证明: 设完全二叉树的深度为h,则根据性质2和完全二叉树的定义有
2h-1
-1<n2h-1或2h-1
n<2h取对数h-1<log2nh,又h是整数,因此有h=log2(n)
+1性质5:在完全二叉树中编号(1开始)为i的结点,1)若有左孩子,则左孩编号为2i;2)若有右孩子,则有孩子结点编号为2i+1;3)若有双亲,则双亲结点编号为
i/2;2i+2
2i2i+1
2i+22i+3i+1
2i2i+1iii+1二叉树也可以采用两种存储方式:顺序存储结构和链式存储结构。顺序存储结构这种存储结构适用于完全二叉树其存储形式为:用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点二叉树的存储结构一般二叉树的顺序表示ABCDEFGHIJABDHIJEFGC顺序表示IABCFEDGH9J完全二叉树的顺序表示ABCD0EFGH0000IJ--------二叉树的顺序存储表示------------#defineMAX_TREE_SIZE100//二叉树的最大结点数
typedef
TElemType
SqBiTree[MAX_TREE_SIZE];//0号单元存放根结点
SqBiTree
bt;最坏情况:深度为k的且只有k个结点的单支树需要长度为2k-1的一维数组。链式存储结构
在顺序存储结构中,利用编号表示元素的位置及元素之间孩子或双亲的关系,因此对于非完全二叉树,需要将空缺的位置用特定的符号填补,若空缺结点较多,势必造成空间利用率的下降。在这种情况下,就应该考虑使用链式存储结构常见的二叉树结点结构如下所示:lChild
data
rChild其中,Lchild和Rchild是分别指向该结点左孩子和右孩子的指针,data是数据元素的内容。类型定义为:
typedef
struct
BiTNode{
TElemTypedata;
struct
BiTNode
*Lchild,*Rchlid;}BTNode,*BTree;GHDEFBCA^G^^H^^D^E^F^B^CABT这种存储结构的特点是寻找孩子结点容易,双亲比较困难。因此,若需要频繁地寻找双亲,可以给每个结点添加一个指向双亲结点的指针域,其结点结构如下所示lChilddataparentrChild
typedef
struct
TriTNode
{//结点结构
TElemType
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- Zinc-acetate-生命科学试剂-MCE
- R-5-Oxopyrrolidine-2-carboxylic-acid-Standard-生命科学试剂-MCE
- Perfluorononanoic-acid-PFNA-生命科学试剂-MCE
- 2025年卫星支架、分配器合作协议书
- Dexamethasone-metasulfobenzoate-sodium-Standard-生命科学试剂-MCE
- 消防管件购销合同
- 公路机电系统工程施工方案
- 离婚后财产归属协议书
- 2025年地铁建设项目发展计划
- 2025年医用磁共振成像设备项目发展计划
- 二零二五年度博物馆场地租赁与文物保护合作协议3篇
- 2025年春新人教版历史七年级下册全册课件
- 岛津气相色谱培训
- 2024年03月四川农村商业联合银行信息科技部2024年校园招考300名工作人员笔试历年参考题库附带答案详解
- 睡眠专业知识培训课件
- 骆驼祥子-(一)-剧本
- 临床思维能力培养
- 人教版高中物理必修第三册第十章静电场中的能量10-1电势能和电势练习含答案
- 魏晋南北朝时期中外文化的交流
- 渔业行业智能化海洋牧场养殖方案
- 中国宗教文化 中国古代宗教文化的特点及现代意义
评论
0/150
提交评论