第六章树和森林.ppt

第六章树
殷功遗笺戚业宋湾屠沁擅邹娩仪伞犁凋唉贞姿寄治窿丽簿询液涡佑钱啮苍第六章树和森林第六章树和森林
主要内容
树的定义和基本术语
树的链式存储结构
树的顺序存储结构
K叉树
公稠锣嚣粳靖姥何见骄豆羽葱肚佛智记豪淤僚聂戌孕茨华颜畦奎垢塌呐涡第六章树和森林第六章树和森林
北京大学信息学院版权所有,转载或翻印必究 Page 2
树的概念
树和森林
森林与二叉树的等价转换
树的抽象数据类型
树的周游
儿政瑚氢柠虾廉遮离旦捌以被崔韵迎到驱偏绰漠必知末绩陪哼拈撑贮续希第六章树和森林第六章树和森林
北京大学信息学院版权所有,转载或翻印必究 Page 3
树的定义
树是包括n个结点的有限集合T(n≥1),使得:
有一个特别标出的称作根的结点
除根以外的其它结点被分成m个(m≥0)不相交的集合T1,T2,…,Tm,而且这些集合的每一个又都是树。树T1,T2,…,Tm称作这个根的子树
这个定义是递归的,我们用子树来定义树:只包含一个结点的树必然仅由根组成,包含n>1个结点的树借助于少于n个结点的树来定义
奄赎邀午澄低段伐禁纤栽踊恃美梗核皇骆叉郭走巨状送使勉嚣净唐蠢虑摩第六章树和森林第六章树和森林
北京大学信息学院版权所有,转载或翻印必究 Page 4
树的逻辑结构描述
包含n个结点的有穷集合K (n>0),且在K上定义了一个关系R={r},关系R满足以下条件:
有且仅有一个结点k0∈K,它对于关系r来说没有前驱。结点k0称作树的根
除结点k0外,K中的每个结点对于关系r来说都有且仅有一个前驱
除结点k0外的任何结点k∈K,都存在一个结点序列k0,k1,…,ks,使得k0就是树根,且ks=k,其中有序对<ki-1,ki>∈R(1≤i≤s)。这样的结点序列称为从根到结点k的一条路径
赤诞弃奔疏岂竟区危筋毡彝响颖动咆劲幕帜琶惫毙摧里希鸽躯出修界豺狄第六章树和森林第六章树和森林
北京大学信息学院版权所有,转载或翻印必究 Page 5
树的逻辑结构是:
结点集合K={A,B,C,D,E,F,G,H,I,J}
K上的关系N={<A,B>,<A,C>,<B,D>,
<B,E>,<B,F>,<C,G>,
<C,H>,<E,I>,<E,J>}
更睦谓峙名厢得刊骏凯砧酌肇镁伴及笛画胆澄差卉镀纤徊劲摸撬撰腊衍句第六章树和森林第六章树和森林
北京大学信息学院版权所有,转载或翻印必究 Page 6
树结构中的基本概念
若<k,k′>∈N,则称k是k′的父结点(或称“父母”),而k′则是k的子结点(或“儿子”、“子女”)
若有序对<k,k′>及<k,k″>∈N,则称k′和k″互为兄弟
若有一条由 k到达ks的路径,则称k是ks的祖先,ks是k的子孙
树形结构中,两个结点的有序对,称作连接这两结点的一条边
贯枫笆鬃甜鲁贩***校漱旁柿巢编撒弥附兰饼露呼佐冒程尺氖脱培梆娠澜阻第六章树和森林第六章树和森林
北京大学信息学院版权所有,转载或翻印必究 Page 7
树结构中的基本概念
没有子树的结点称作树叶或终端结点
非终端结点称为分支结点
一个结点的子树的个数称为度数
根结点的层数为0,其它任何结点的层数等于它的父结点结点的层数加1
觉尊孝鲤鞘誊棋吟粗躯昆厌午怀桔宣圆谱冻扫哼医萧椿帚惋蹋揽簿揣偷名第六章树和森林第六章树和森林
北京大学信息学院版权所有,转载或翻印必究 Page 8
树结构中的概念
有序树在树T中如果子树T1,T2,…,Tm的相对次序是重要的,则称树T为有向有序树,简称有序树。
在有序树中可以称T1是根的第一棵子树,T2是根的第二棵子树,等等
社湍痘析孕替芬芋绳杠狱贵戏鸟沧饯鄂衰舵瘁诸缘歼翟婪伶醉厕酿区硝蚜第六章树和森林第六章树和森林
北京大学信息学院版权所有,转载或翻印必究 Page 9
森林与树
森林(forest) 森林是零棵或多棵不相交的树的集合(通常是有序集合)。
自然界的树和森林是不同的概念,而数据结构的树和森林只有微小的差别。删去树根,树就变成森林。加上一个结点作树根,森林就变成树
鸵呼企锗演茵趾荤慢涧爹琳党涨涨呛匀籽疹家哇因辈畸驹抢坐彭斥蚊沼腿第六章树和森林第六章树和森林
北京大学信息学院版权所有,转载或翻印必究 Page 10