遍历二叉树

遍历二叉树授课：陈嘉庆二叉树的运算1、二叉树的遍历2、二叉树的输出3、求二叉树的深度3遍历二叉树TraversingBinaryTree遍历定义——遍历用途——遍历方法——指按某条搜索路线遍访每个结点且不重复（又称周游）。它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。对每个结点的查看通常都是“先左后右”。4遍历规则———二叉树由根、左子树、右子树构成，定义为D、L、R以根结点为参照系注：“先、中、后”的意思是指访问的结点D是先于子树出现还是后于子树出现。D、L、R的组合定义了六种可能的遍历方案：LDR,LRD,DLR,DRL,RDL,RLD若限定先左后右，则有三种实现方案：DLRLDRLRD先序/根遍历中序/根遍历后序/根遍历5例1：先序遍历的结果是：中序遍历的结果是：后序遍历的结果是：ABCDEDBEACDEBCA口诀：DLR—先序遍历，即先根再左再右LDR—中序遍历，即先左再根再右LRD—后序遍历，即先左再右再根ABDEC6对遍历的分析：1.从前面的三种遍历算法可以知道：如果将print语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。从虚线的出发点到终点的路径上，每个结点经过3次。AFEDCBG第1次经过时访问，是先序遍历第2次经过时访问，是中序遍历第3次经过时访问，是后序遍历2.二叉树遍历的时间效率和空间效率时间效率：O(n)//每个结点只访问一次空间效率：O(n)//栈占用的最大辅助空间精确值：树深为k的递归遍历需要k+1个辅助单元7特别讨论：若已知先序（或后序）遍历结果和中序遍历结果，能否“恢复”出二叉树？例：已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG和DECBHGFA，请画出这棵二叉树。分析：①由后序遍历特征，根结点必在后序序列尾部（即A）；②由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树的子孙（即BDCE），其右部必全部是右子树的子孙（即FHG）；③继而，根据后序中的DECB子树可确定B为A的左孩子，根据HGF子串可确定F为A的右孩子；以此类推。8已知中序遍历：BDCEAFHG已知后序遍历：DECBHGFA（BDCE）（FHG）A（DCE）BFGHCDEABBACCDCE二叉树的遍历●遍历——按一定规律走遍树的各个顶点，且使每一顶点被且仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列●常用方法●NLR：前序遍历，访问结点的操作发生在遍历其左右子树之前●LNR：中序遍历，访问结点的操作发生在遍历其左右子树之中（间）●LRN：后序遍历，访问结点的操作发生在遍历其左右子树之后ADBCNLRANLRNLRBDCNLR先序遍历序列：ABDC先序遍历:ADBCLNRBLNRLNRADCLNR中序遍历序列：BDAC中序遍历:ADBCLRNLRNLRNADCLRN后序遍历序列：DBCA后序遍历:B-+/a*b-efcd先序遍历：中序遍历：后序遍历：-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef遍历——练习遍历——练习●有二叉树的中序遍历为ABCEFGHD，后序遍历序列为：ABFHGEDC。请画出此二叉树，并求前序序列。例：用顺序存储方式建立一棵如图所示的二叉树，并对其进行先序遍历。123465abcdfe先序遍历算法proceduresearch(m:integer);beginwithtr[m]dobeginwrite(data);ifl0thensearch(l);ifr0thensearch(r);end;end;beginjtr;search(1);writeln;end.programtree1;constn=15;typenode=recorddata:char;l,r:0..n;end;vartr:array[1..n]ofnode;i,j:integer;procedurejtr;vari:integer;beginfori:=1tondowithtr[i]doreadln(data,l,r);end；例：由先序序列建立二叉树（链表），并且先序、中序、后序遍历该二叉树abcd先序序列为：ab##cd###二叉树的遍历●二叉树常用的存储结构typebitree=^nodenode=recorddata:datatype;lchild,rchild:bitree;end;1、先序遍历：根左右Procedurepreorder(bt:bitree);Beginifbtnilthenbeginvisit(bt^);preorder(bt^.lchild);preorder(bt^.rchild);end;End;二叉树的遍历2、中序遍历：左根右Procedurepreorder(bt:bitree);Beginifbtnilthenbeginpreorder(bt^.lchild);visit(bt^);preorder(bt^.rchild);end;End;3、后续遍历：左右根Procedurepreorder(bt:bitree);Beginifbtnilthenbeginpreorder(bt^.lchild);preorder(bt^.rchild);visit(bt^);end;End;输出二叉树如何将一棵二叉树输出为广义表的形式。Procedureprint(bt:bitree);Beginifbtnilthenwrite(bt^.data);if(bt^.lchildnil)or(bt^.rchildnil)thenbeginwrite(‘(’);print(bt^.lchild);ifbt^.rchildnilthenbeginwrite(‘,’);print(bt^rchild);end;write(‘)’);end;End;结论：1、已知先序和中序可以确定二叉树2、已知后序和中序可以确定二叉树例：先序:abdecf中序:dbeafc画出二叉树，写出后序遍历的结果。2、(NOIP7)已知一棵二叉树的结点名为大写英文字母。中序遍历：CBGEAFHDIJ后序遍历：CGEBHFJIDA则该二叉树的先序遍历的顺序为：3、中序遍历：DBGEACHFI后序遍历：DGEBHIFCA求先序遍历结果4、(NOIP6)已知，按中序遍历二叉树的结果为：abc问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。1、给出一棵二叉树的先序遍历：ABCDEFGH中序遍历：CBEDAGHF画出此二叉树并写出后序遍历结果。【例题1】根据两种遍历顺序确定树结构输入：二叉树的前序遍历顺序与中序遍历顺序输出：二叉树的后序遍历顺序样例：输入：ABCDEFGHCBEDAGHF输出：CEDBHGFA//算法1varsx,sz:string;procedurework(sx,sz:string);varl,k:integer;beginifsx''thenbeginl:=length(sx);k:=pos(sx[1],sz);work(copy(sx,2,k-1),copy(sz,1,k-1));work(copy(sx,k+1,l-k),copy(sz,k+1,l-k));write(sx[1]);end;end;beginreadln(sx);readln(sz);work(sx,sz);end.//算法2functionwork(sx,sz:string):string;varl,k:integer;left,right:string;beginifsx=''thenexit('')elsebeginl:=length(sx);k:=pos(sx[1],sz);left:=work(copy(sx,2,k-1),copy(sz,1,k-1));right:=work(copy(sx,k+1,l-k),copy(sz,k+1,l-k));work:=left+right+sx[1];end;end;Writeln(work(sx,sz);ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI树转换成的二叉树其右子树一定为空将树转换成二叉树●加线：在兄弟之间加一连线●抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系求二叉树的深度若二叉树空，则深度为0，否则其深度=子树的最大深度+1。Functiondepth(bt:bitree):integer;Beginifbt=nilthendepth:=0;depth1:=depth(bt^.lchild);depth2:=depth(bt^.rchild);ifdepth1depth2thendepth:=depth1+1elsedepth:=depth2+1;End;ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ森林转换成二叉树●将各棵树分别转换成二叉树●将每棵树的根结点用线相连29小结1、定义和性质2、存储结构3、遍历顺序结构链式结构二叉链表三叉链表树二叉树1:2，性质有3+2条中序遍历后序遍历先序遍历1:n相关术语