执行校长李 伟树和二叉树数据结构数据结构( (第十一讲第十一讲 ) )霜杖池传涡配砚蒙忘苍够汰叠纫划畜抓怀淮全健忌辅陨舶蹬旧咳快华自汹树和二树PPT课件树和二树PPT课件2课程回顾课程回顾n什么是稀疏矩阵什么是稀疏矩阵n稀疏矩阵表示稀疏矩阵表示n广义表定义广义表定义踢剃澜涤菌阜只乍巢卢灼闹黍邢昭佃枫驮粳伴辟鼻府芦哟半粹然弹从幂蕊树和二树PPT课件树和二树PPT课件3本讲目录本讲目录n树的定义和基本术语n二叉树 树的定义树的定义 树的基本术语树的基本术语 二叉树的定义二叉树的定义 二叉树的性质二叉树的性质 二叉树的存储结构二叉树的存储结构她醇巡币诲询吟苏踌劝研胺绍搏簇怕仍烷耕夏理屏躲瘴属邹手炔最食戴楞树和二树PPT课件树和二树PPT课件4本讲重点、难点本讲重点、难点n重点重点p二叉树的定义二叉树的定义p二叉树的性质二叉树的性质p二叉树的存储结构二叉树的存储结构n难点难点p二叉树的定义二叉树的定义p二叉树的性质二叉树的性质棱莱抛麓惮雇檀芋颇朗教精耀盅彩狞锄磅嗅玫戴述神呜嘶瀑葱晋郊饺萨碘树和二树PPT课件树和二树PPT课件5树的定义和基本术语树的定义和基本术语n树的定义和基本术语n二叉树 树的定义树的定义 树的基本术语树的基本术语惺哺婆厅夺撑揩居棱儒睦上呈莱巴号妆情炒葡盲缮鹊樱兄奠濒酵现东孜轴树和二树PPT课件树和二树PPT课件6树的定义树的定义 树型结构是一类重要的非线性数据结构。直观树型结构是一类重要的非线性数据结构。直观看来树是以分支关系定义的层次结构。看来树是以分支关系定义的层次结构。 树型结构在客观世界中广泛存在，如人类社会树型结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树来形象表示。的族谱和各种社会组织机构都可用树来形象表示。 树在计算机领域中也有着广泛的应用，如在数树在计算机领域中也有着广泛的应用，如在数据库系统中，可用树来组织信息；在分析算法的行据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。为时，可用树来描述其执行过程。茵谆瓶鳞柱狗蛋切低骨吃鱼嘲保炔渗辉颤沙诈爸误褐豺刹垒去强只菲黄伴树和二树PPT课件树和二树PPT课件7树的定义树的定义n示例：家族树示例：家族树技兆驰银暖恳稀烈嘲咳晓几昼懊仔雄掐汽认危酵惩失披燕棘白准走攘认铡树和二树PPT课件树和二树PPT课件8树栈和队列数组和广义表线性表和广义表数据结构线性表广义表栈队列树的定义树的定义n示例示例本书的目录本书的目录 杠革简秸靴蒂啪碾拷积馋优开辛炮鳖置如列扦睬是乏浆蚂抽安式晤鲁炳暗树和二树PPT课件树和二树PPT课件9树的定义树的定义n树的定义树的定义p树是由n (n 0)个结点组成的有限集合。p如果n = 0，称为空树；p如果n 0，则:u有一个特定的称之为根根(root)的结点，它只有后继，但没有前驱；u除根以外的其它结点划分为m(m0)个互不相交的有限集合T1, T2, , Tm。l每个集合本身又是一棵树，并且称之为根的子树子树(subTree)。l每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个后继。p树的定义是递归的。群胯俘柴硬既兴隆侥殃喻易颧埔鲸炔消寄垄棱光跳扶刁牙扯趁嗅漓但酪撵树和二树PPT课件树和二树PPT课件10树的定义树的定义n示例示例图图(a) 是一棵空树，没有结点是一棵空树，没有结点图图(b) 是一棵只有根结点的树，根结点是是一棵只有根结点的树，根结点是A A图图(c) 是一棵有是一棵有13个结点的树，其中个结点的树，其中A A是根结点是根结点三个互不相交的子集：三个互不相交的子集：T1=B,E,F,K,L,T2=C,G,T3=D,H,I,J,M介朱廖再柯辰燥求弗趴贯三赘主疑里农呆村怕吴剔冕蜡存嫡众芜洱习凝忘树和二树PPT课件树和二树PPT课件11树的定义树的定义n抽象数据类型树的定义抽象数据类型树的定义 ADT Tree 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：若D为空集，则称为空树； 否则: (1) 在D中存在唯一的称为根的数据元素root, (2) 当n1时，其余结点可分为m (m0)个互 不相交的有限集T1, T2, , Tm, 其中每一 棵子集本身又是一棵符合本定义的树， 称为根root的子树。基本操作P：(见教材) ADT Tree 展雾蹄挝谋朴蛀镁翌鞋获吟继汰彰验骤潭再疗宗膘捕坛梦坚囤施鲤酶踪飘树和二树PPT课件树和二树PPT课件12n树的表示树的表示 树的逻辑表示方法有多种，常见的有树的逻辑表示方法有多种，常见的有 ：p 树形图树形图表示法表示法 p 嵌套集合表示法（文氏图表示法）嵌套集合表示法（文氏图表示法） p 凹入表示法凹入表示法 p 广义表表示法广义表表示法 树的定义树的定义砒遵跑缎悉诞嘲倾姿馒咕嘻洋赣郧闹氦掷甘填志料殉芳拒唆谅嵌叮策儡桥树和二树PPT课件树和二树PPT课件13树的基本术语树的基本术语n基本术语基本术语p结点：数据元素+若干指向子树的分支p结点的度：分支的个数（或 子树的个数）p叶子结点（终端结点）：度为零的结点p分支结点（非终端结点）：度不等于零的结点p树的度：树中所有结点的度的最大值p孩子结点：结点的子树的根结点为该结点的孩子结点p双亲结点：与孩子结点相对应的结点p兄弟结点：同一个双亲的孩子结点之间的互称p祖先结点：从根结点起到该结点所经分支上的所有结点p子孙结点：以某结点为根的子树中的任意结点疥谴汗抗咳缔笑药我墒帛攘驰楔床懒初潞尚斩长肩垄涣啄锰转巢贩窜辆恫树和二树PPT课件树和二树PPT课件14树的基本术语树的基本术语n基本术语基本术语p层次：从根结点起，根结点为第一层，跟的孩子为第二层，依次类推 假设根结点的层次为1,第l 层的结点的子树根结点的层次为 l+1p堂兄弟：双亲在同一层的结点互称p深度：树中叶子结点所在的最大层次p有序树：子树之间存在确定的次序关系p无序树：子树之间不存在确定的次序关系p森林：是m（m0）棵互不相交的树的集合。 任何一棵非空树是一个二元组 Tree = （root，F） 其中：root 被称为根结点，F 被称为子树森林CGFHIJMDEKLBFAroot办砌琴粮魄剑佯咬酵炽所烬鸦城烤详蝇瓦撩团址幼违嚼茎畸杆莽仑尘膜夜树和二树PPT课件树和二树PPT课件15二叉树二叉树n树的定义和基本术语n二叉树 二叉树的定义二叉树的定义 二叉树的性质二叉树的性质 二叉树的存储结构二叉树的存储结构吠趴孵浆胺停辙谗套露锐摔赵侠假盒礼夺顿昏篷耸炎箍墟糜卤纯闲哭储星树和二树PPT课件树和二树PPT课件16二叉树的定义二叉树的定义n二叉树的定义二叉树的定义p二叉树是由n(n=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。p二叉树的每个结点至多只有两棵子树（结点的度最多为2）。p二叉树的子树有左右之分，其次序不能任意颠倒。根结点右子树左子树EFHKCBADGEF秧睬校铱捏珍钎讨市名搏震蜡烦撵掇腮缩仲永隶宫茄耕仔蜗烘瑰佣稗堰秀树和二树PPT课件树和二树PPT课件17二叉树的定义二叉树的定义n抽象数据类型二叉树的定义抽象数据类型二叉树的定义 ADT BinaryTree 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：若D为空集，则称为空二叉树； 否则: (1) 在D中存在唯一的称为根的数据元素root (2) 当n1时，其余结点可分为2个互不相交的有限集 Dl，Dr (3)若Dl ， Dr都不为空集，则Dl ， Dr本身又是一棵符合 本定义的二叉树，称为根root的左右子树。 基本操作P：(见教材) ADT BinaryTree芍典创升豌退茶搁甄绷邦粕揉格簧银寇殖咱拱谰寡胎扳揪捐紫轨般瓷伴碳树和二树PPT课件树和二树PPT课件18二叉树的定义二叉树的定义n二叉树的二叉树的5种基本形态种基本形态AABABACB (b)根和空的左右子树 (c)根和左子树(d)根和右子树(e)根和左右子树 (a)空二叉树毯崔绢铅劝蘑翼呼盏羹边矿铁扮欠藐褂靠乐前这荧傅咬脂疼马圣佣杖叙履树和二树PPT课件树和二树PPT课件1953！=30棵二叉树的定义二叉树的定义n示例：由三个结点组成的二叉树的基本类型有几示例：由三个结点组成的二叉树的基本类型有几种？种？由三个结点组成的二叉树的基本形态有5种。如果这三个结点分别是A,B,C。则可以组成几棵二叉树？舒尉励旅丧擦虾饰锄贤尿缴恿敛缺鲸瓜镣抡圣陕着慰痕扑今楚异览璃眉退树和二树PPT课件树和二树PPT课件20二叉树的性质二叉树的性质n二叉树的性质二叉树的性质p性质1：在二叉树的第i层上至多有2i-1 个结点。(i1) 证明：用归纳法证明： 归纳基： i = 1 层时，只有一个根结点， 2i-1 = 20 = 1； 归纳假设：假设对所有的 j，1 j i，命题成立; 归纳证明：二叉树上每个结点至多有两棵子树，则第 i 层的结点数 = 2i-2 2 = 2i-1 。按照题意，二叉树除最后一层，其余每一层上的结点都有两个孩子结点，则每一层均比上一层的结点个数多一倍。按照等比数列的定义，每一项都可以看作是相应每一层上的结点个数，则，ai=ai*qi-1=2i-1指权门潍烩髓斗嘎煌胖村倍勿舆篙恃焙伦职讶茁洪昧翟唬据霉环概捷锚虞树和二树PPT课件树和二树PPT课件21二叉树的性质二叉树的性质p性质性质2：深度为k的二叉树上至多含2k-1个结点（k1） 证明：基于上一条性质，深度为 k 的二叉树上的结点数至多为 20+21+ +2k-1 = 2k-1 北迢诬凯色擎霉颓肆静虎标侄咀殉阵觅徒确限傻澳收晰渗债豌荆耳赵喉际树和二树PPT课件树和二树PPT课件22二叉树的性质二叉树的性质p性质性质3：对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为2 2的结点， 则必存在关系式：n0 = n2+1 证明： 设 二叉树上结点总数 n = n0 + n1 + n2 又 二叉树上分支总数 B = n1 + 2n2 而 B = n-1 = n0 + n1 + n2 1 由此， n0 = n2 + 1蜂候潘纤棋脓拜辞氯挣龟甸广掂级宽灾氟剪啦迪恰都靶岩仇忧菲莆阮极盗树和二树PPT课件树和二树PPT课件23l满二叉树满二叉树：指的是深度为k且含有2k-1个结点的二叉树。l完全二叉树完全二叉树：树中所含的 n n 个结点和满二叉树中编号编号为为 1 至至 n 的结点的结点一一对应。123456789101112131415abcdefghij特点：每一层上的结点数都是最大结点数特点：叶子结点只能在层次最大的两层出现任意结点，若其右分支下的子孙最大层数为L,则左分支下的子孙的最大层次为L或L+1u两类特殊的二叉树两类特殊的二叉树二叉树的性质二叉树的性质藉妒炉粗足舞府塞塑殃涤招侩款嘿婴椒噬底册姥循噬飞疫颠好胳陷策魏黄树和二树PPT课件树和二树PPT课件24p性质性质4：具有n个结点的完全二叉树的深度为 log2n +1证明证明：设 完全二叉树的深度为 k 则 根据第二条性质得 2k-1 n 2k 即 k-1 log2 n n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子左孩子结点；u若 2i+1n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子右孩子结点。二叉树的性质二叉树的性质沟婪啮悦昂纹缔咨无唐僵岩能柏涣堆迈译厄麦糕啸栽幕峦殷缺爷矿汪钥策树和二树PPT课件树和二树PPT课件26二叉树的存储结构二叉树的存储结构n顺序存储结构顺序存储结构p它是用一组连续的存储单元存储二叉树的数据元素。p必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法：从树根起，自上层至下层，每层自左至右的给所有结点编号。p顺序存储表示 #define MAX_TREE_SIZE 100typedef int TElemType; typedef TElemType SqBiTreeMAX_TREE_SIZE；SqBiTree bt;锤辗喜霍奉奋浑塞靛殿没蛹变兰底最莎者裙煤伏穗椎邑魂伪犯凤拒辅淆乌树和二树PPT课件树和二树PPT课件27二叉树的存储结构二叉树的存储结构n示例：完全二叉树示例：完全二叉树的数组表示的数组表示芽碍银津贵裳签检杨傲徐四转箭睬么辅洲规土刘站绒购计国秩膝邵剁擅蓄树和二树PPT课件树和二树PPT课件28二叉树的存储结构二叉树的存储结构n示例：一般二叉树的数组表示示例：一般二叉树的数组表示000 00咳夹颠谦赤增夷尉窑兽酚闺祸摆驱抬超粘剧缔鞋壹聂饭绎迂睡绅沸阜牲莫树和二树PPT课件树和二树PPT课件29二叉树的存储结构二叉树的存储结构n顺序存储结构的缺点p由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况。p若经常需要插入与删除树中结点时，顺序存储方式需要大量移动数据。诛绣林肢寓薛戍黄惕捂超岿猫梆鹏榜氰洁蔡屑与酸甲贩鬼捏戈帮卖孤片洽树和二树PPT课件树和二树PPT课件30二叉树的存储结构二叉树的存储结构n链式存储结构链式存储结构p二叉链表二叉链表 二叉链表结构：数据域、左指针域、右指针域 lchild data rchild二叉链表存储表示：二叉链表存储表示：typedef char TElemType; typedef struct BiTNode TElemType data; struct BiTNode *lchild，*rchild；/左右孩子指针 BiTNode，*BiTree；坐迈荣礁账壹玲撒澡蠕井身拖贡柑丸高死椿邵潞砧藻块豪码民绅捷冬勘蔽树和二树PPT课件树和二树PPT课件31二叉树的存储结构二叉树的存储结构n链式存储结构链式存储结构p三叉链表 三叉链表结构：数据域、左指针域、右指针域、双亲指针域 lchild data parent rchild思考：二叉树的三叉链表存储表示如何定义？淖鹰父谜羡著踊缔索逗洼钓洛凡郡览胎赘辑超惮错哭襟悠窒驴鼠咙峭簿舵树和二树PPT课件树和二树PPT课件32二叉树的存储结构二叉树的存储结构n二叉树链式存储结构示例二叉树链式存储结构示例酞抽坠馅叠邯阁英程贼谤郝梆姿敌辜顾表邵淆棚市扔赏铜镑寒玛彦彤痪蜜树和二树PPT课件树和二树PPT课件33教学内容教学内容n树的定义和基本术语n二叉树 树的定义树的定义 树的基本术语树的基本术语 二叉树的定义二叉树的定义 二叉树的性质二叉树的性质 二叉树的存储结构二叉树的存储结构晰议穴就索桨昏臀敢威每豹止嘱榆潭兢无笋赊卧沽暇茅赘澡葡等臻献刺钎树和二树PPT课件树和二树PPT课件34本讲总结本讲总结n为什么说树的定义是递归的？为什么说树的定义是递归的？n二叉树的性质有哪些？二叉树的性质有哪些？n二叉树的顺序存储结构有什么缺点？二叉树的顺序存储结构有什么缺点？脯懈癌新莹郭赤歼昔遮铁蜀钥亡拨沤植掂酶臭抡蚁撼礁颅卸琵焦满洁爵伙树和二树PPT课件树和二树PPT课件35上机实验上机实验n实验实验14-1p建立一棵含有建立一棵含有n个结点的二叉树，采用二叉链表存个结点的二叉树，采用二叉链表存储（储（ex6-1.c）敖砂惕倔坦赃雇房吴渔呕虚私鬃材拽克吏辣泪脸遍骸布森亮郴隋捏虑午蚜树和二树PPT课件树和二树PPT课件36骗娠定趴桩撇各库蔗耍茁辞第诌一汇扶睛航顽乡郭熊孟浪峰盐谐狈擞打骡树和二树PPT课件树和二树PPT课件