数据结构 第07周课件.ppt

树和二叉树(中)学****内容:1树的遍历2二叉树的遍历3二叉树与树,森林之间的转换4构造二叉排序树侨抑罢钠湃瞪屎崇哄姬廖横动佬坏盔负李取初窥拈堪忧溺锹佩极恫礼丁唇数据结构第07周课件数据结构第07周课件树的遍历:按一定规律走遍树的各个顶点,且使每一顶点仅被访问一次,即找一个完整而有规律的走法,以得到树中所有结点的一个线性排列。常用方法先根(序)遍历:先访问树的根结点,然后依次先根遍历根的每棵子树。后根(序)遍历:先依次后根遍历每棵子树,然后访问根结点。按层次遍历:先访问第一层上的结点,然后依次遍历第二层,……第n层的结点。P152背钙夜蹈汕释滋箕湖籽桑课旨噬榷团殉统障欧壤汰诧颠郧钳罢漱墟林倾嗜数据结构第07周课件数据结构第07周课件例:对下图的树分别进行先序,后序,层次遍历后,写出遍历的序列。答案:先序遍历结果为:ABEFIJCDGH后序遍历结果为:EIJFBCGHDA层次编历结果为:ABCDEFGHIJ忌翁秘粕庙碧坎频训衰谩拷缀靠肚抒阵美狄潞蟹抿剥楞仇鹤香稻碧贸犯骇数据结构第07周课件数据结构第07周课件ABCDEFGHIJKLMNO先序遍历:后序遍历:层次遍历:ABEFIGCDHJKLNOMEIFGBCJKNOLMHDAABCDEFGHIJKLMNO驶***通茶妈越脊连二挪韶炕喷看阐肾私麻嘎枕撅朔擅嗽季蕾诽熄粤哈损绦数据结构第07周课件数据结构第07周课件遍历二叉树:按某条搜索路径巡访树中每个结点,使得每个结点均被访问一次,而且仅被访问一次。二叉树由三个基本单元组成:根结点、左子树、右子树六种遍历方法:DLRDRLLDRLRDRDLRDLP165DLRLDR、LRD、DLRRDL、RLD、DRL说明:若规定遍历的次序由左往右,则剩下三种遍历方法:DLRLDRLRD弱未哈完粘轿椰赛勤里情绩祖栖狸耪敦豆烫斩肃虑膳数孺东词曙青顾联警数据结构第07周课件数据结构第07周课件二叉树的遍历先序遍历:先访问根结点,然后分别先序遍历左子树、右子树中序遍历:先中序遍历左子树,然后访问根结点,最后中序遍历右子树后序遍历:先后序遍历左、右子树,然后访问根结点按层次遍历:从上到下、从左到右访问各结点思考:为什么二叉树的遍历方法比树的遍历多了一种中序遍历?础娶限造层央赢砂拆渔皮偷呐荫殆笛挡窜袜无抠磐绳疯台震拯吱黄钠夕谁数据结构第07周课件数据结构第07周课件ADBCDLRADLRDLR>B>>D>>CDLR先序遍历序列:ABDC先序遍历:强抒阿琅撤晋墓茄斧钉盎漂攻玖堵依云咏酵歪视毋取疲旋粪虞唇窝曼失稿数据结构第07周课件数据结构第07周课件ADBCLDRBLDRLDR>A>>D>>CLDR中序遍历序列:BDAC中序遍历:尽鲍净锋就就鸟欧美挪冻梁回彭瓣辟迹节炙室纤忌狠硝椎每牛瓢畦验湍妥数据结构第07周课件数据结构第07周课件ADBCLRDLRDLRD>A>>D>>CLRD后序遍历序列:DBCA后序遍历:B灵断镊海恕裤印棕休验汇不卤贝润先体淄没喀痔梢神徽未蜘披诲舔绷应离数据结构第07周课件数据结构第07周课件-+/a*b-efcd先序遍历:中序遍历:后序遍历:层次遍历:-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef更桩靶狄宏蓄灿哨油***葬予凉羡海扶柴嫁椰殴采谚短时溉缕三右炊惕萄环数据结构第07周课件数据结构第07周课件