武汉理工大学-信息工程学院-数据结构-ppt-课件ch06-2-树和二叉树2-遍历二叉树

第6章树和二叉树数据结构讲义—遍历二叉树信息工程学院魏洪涛Email:[e-mail]6.3遍历二叉树二叉树的遍历–方法先序遍历：先访问根结点,然后分别先序遍历左子树、右子树。中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树。后序遍历：先后序遍历左、右子树，然后访问根结点。按层次遍历：从上到下、从左到右访问各结点。DLRLDR、LRD、DLRRDL、RLD、DRLADBCDLRADLRDLRBDCDLR先序遍历序列：ABDC先序遍历:ADBCLDRBLDRLDRADCLDR中序遍历序列：BDAC中序遍历:ADBCLRDLRDLRDADCLRD后序遍历序列：DBCA后序遍历:B-+/a*b-efcd先序遍历：中序遍历：后序遍历：层次遍历：-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/efvoidpreorder(JD*bt){if(bt!=NULL){printf(%d\t,bt-data);preorder(bt-lchild);preorder(bt-rchild);}}主程序Pre(T)返回返回pre(TR);返回返回pre(TR);ACBDTBprintf(B);pre(TL);BTAprintf(A);pre(TL);ATDprintf(D);pre(TL);DTCprintf(C);pre(TL);C返回T左是空返回pre(TR);T左是空返回T右是空返回T左是空返回T右是空返回pre(TR);先序序列：ABDC–非递归算法实现中序遍历ABCDEFGpiP-A(1)ABCDEFGpiP-AP-B(2)ABCDEFGpiP-AP-BP-C(3)p=NULLABCDEFGiP-AP-B访问：C(4)pABCDEFGiP-A访问：CB(5)ABCDEFGiP-AP-D访问：CBp(6)ABCDEFGiP-AP-DP-E访问：CBp(7)ABCDEFGiP-AP-D访问：CBEp(8)ABCDEFGiP-AP-DP-G访问：CBEP=NULL(9)ABCDEFGiP-A访问：CBEGDp(11)ABCDEFGiP-AP-F访问：CBEGDp(12)ABCDEFGiP-AP-D访问：CBEGp(10)ABCDEFGiP-A访问：CBEGDFp=NULL(13)ABCDEFGi访问：CBEGDFAp(14)ABCDEFGi访问：CBEGDFAp=NULL(15)后序遍历非递归算法遍历算法应用–按先序遍历序列建立二叉树的二叉链表，已知先序序列为：ABCDEGFABCDEFGA^B^C^D^E^F^^G^二叉树的建立演示用队列实现层次遍历可使用一个顺序存储的队列q[100],存放还没有处理的子树的根结点的地址。注意,队首和队尾指针分别指向队首结点和下次进队结点的存放位置。1)首先把根节点入队。2)然后访问队头的一个结点，再把该结点非空的左右子树入队。3)如果队列不空，重复2)。示例代码作业当用栈非递归实现树的先序遍历时，写出遍历右边所表示的树的全过程。像讲义中那样，写出遍历每一步栈中的数据。不是写具体的实现代码。ABCDEFG实验报告按先序遍历序列建立二叉树的二叉链表，已知先序序列为(表示空格)：ABCDEGF。并写一个函数treenodes()统计该二叉树的节点个数。如果有可能，写一个输出函数treeprint()用树形结构打印出该二叉树。注意实验报告中不必写完整代码。写树结构定义，已有函数声明，treenodes()和treeprint()的代码，实现过程，心得体会。