资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,L,A,B,D,I,H,E,K,J,C,F,G,M,N,二叉树的非递归遍历,LABDIHEKJCFGMN二叉树的非递归遍历,1,L,A,B,D,I,H,E,K,J,C,F,G,M,N,非递归中序遍历二叉树：,先访问左子树，再访问根节点，最后访问右子树。,设置一个栈，出栈即为访问节点。先将根节点的左节点全部进栈，然后出栈一个节点，访问。将该节点的右孩子节点进栈，再将右孩子节点的所有左节点全部进栈,.,如此这般直到栈空为止。,LABDIHEKJCFGMN 非递归中序遍历二叉树：,2,void InOrderTraverse(BiTree T,Status(*visit)(ElemType e),BiTree pStack100,p;,int top=-1;,if(T!=NULL),p=T;,while(top -1|p!=NULL),while(p!=NULL),pStack+top=p;,p=p-lchild;,if(top -1),p=pStacktop-;,visit(p-data);,p=p-rchild;,非递归中序遍历二叉树课件,3,L,A,B,D,I,H,E,K,J,C,F,G,M,N,设置一个栈，出栈即为访问该结点。,LABDIHEKJCFGMN设置一个栈，出栈即为访问该结点。,4,L,A,B,D,I,H,E,K,J,C,F,G,M,N,先将根节点及其左孩子全部进栈。,p-,LABDIHEKJCFGMN先将根节点及其左孩子全部进栈。p,5,L,A,B,D,I,H,E,K,J,C,F,G,M,N,将根结点,A,进栈。,此时，,p,指向,A,的左孩子,B,。,A,p-,LABDIHEKJCFGMN将根结点A进栈。Ap-,6,L,A,B,D,I,H,E,K,J,C,F,G,M,N,将根结点,A,的左孩子,B,进栈。,此时，,p,指向,B,的左孩子,D,。,A,B,p-,LABDIHEKJCFGMN将根结点A的左孩子B进栈。ABp,7,L,A,B,D,I,H,E,K,J,C,F,G,M,N,将,B,的左孩子,D,进栈。,此时，,p,指向,D,的左孩子,H,。,A,B,D,p-,LABDIHEKJCFGMN将B的左孩子D进栈。ABDp-,8,L,A,B,D,I,H,E,K,J,C,F,G,M,N,将,D,的左孩子,H,进栈。,此时，,p,指向,H,的左孩子，为,NULL,。,A,B,D,H,LABDIHEKJCFGMN将D的左孩子H进栈。ABDH,9,L,A,B,D,I,H,E,K,J,C,F,G,M,N,H,出栈，访问。,此时，,p,指向,H,的右孩子，为,NULL,。,A,B,D,遍历结果：,H,LABDIHEKJCFGMNH出栈，访问。ABD遍历结果：H,10,L,A,B,D,I,H,E,K,J,C,F,G,M,N,D,出栈，访问。,此时，,p,指向,D,的右孩子,I,。,A,B,遍历结果：,H,D,LABDIHEKJCFGMND出栈，访问。AB遍历结果：HD,11,L,A,B,D,I,H,E,K,J,C,F,G,M,N,将,I,进栈。,此时，,p,指向,I,的左孩子，为,NULL,。,A,B,遍历结果：,H,D,I,LABDIHEKJCFGMN将I进栈。AB遍历结果：HDI,12,L,A,B,D,I,H,E,K,J,C,F,G,M,N,I,出栈，访问。此时，,p,指向,I,的右孩子，为,NULL,。,A,B,遍历结果：,H,D,I,LABDIHEKJCFGMNI出栈，访问。此时，p指向I的右,13,L,A,B,D,I,H,E,K,J,C,F,G,M,N,B,出栈，访问。此时，,p,指向,B,的右孩子,E,。,A,遍历结果：,H,D,I,B,p-,LABDIHEKJCFGMNB出栈，访问。此时，p指向B的右,14,L,A,B,D,I,H,E,K,J,C,F,G,M,N,将,E,进栈。,此时，,p,指向,E,的左孩子,J,。,A,遍历结果：,H,D,I,B,E,LABDIHEKJCFGMN将E进栈。A遍历结果：HDIBE,15,L,A,B,D,I,H,E,K,J,C,F,G,M,N,将,E,的左孩子,J,进栈。此时，,p,指向,J,的左孩子,M,。,A,遍历结果：,H,D,I,B,E,J,LABDIHEKJCFGMN将E的左孩子J进栈。此时，p指向,16,L,A,B,D,I,H,E,K,J,C,F,G,M,N,将,J,的左孩子,M,进栈。此时，,p,指向,M,左孩子，为,NULL,。,A,遍历结果：,H,D,I,B,E,J,M,LABDIHEKJCFGMN将J的左孩子M进栈。此时，p指向,17,L,A,B,D,I,H,E,K,J,C,F,G,M,N,M,出栈，访问。此时，,p,指向,M,的右孩子，为,NULL,。,A,遍历结果：,H,D,I,B,E,J,M,LABDIHEKJCFGMNM出栈，访问。此时，p指向M的右,18,L,A,B,D,I,H,E,K,J,C,F,G,M,N,J,出栈，访问。,此时，,p,指向,J,的右孩子,N,。,A,遍历结果：,H,D,I,B,E,M,J,LABDIHEKJCFGMNJ出栈，访问。A遍历结果：HDI,19,L,A,B,D,I,H,E,K,J,C,F,G,M,N,将,N,进栈。,此时，,p,指向,N,的左孩子，为,NULL,。,A,遍历结果：,H,D,I,B,E,M,J,N,LABDIHEKJCFGMN将N进栈。A遍历结果：HDIBE,20,L,A,B,D,I,H,E,K,J,C,F,G,M,N,将,N,出栈，访问。此时，,p,指向,N,的右孩子，为,NULL,。,A,遍历结果：,H,D,I,B,E,M,J,N,LABDIHEKJCFGMN将N出栈，访问。此时，p指向N的,21,L,A,B,D,I,H,E,K,J,C,F,G,M,N,将,E,出栈，访问。此时，,p,指向,E,的右孩子,K,。,A,遍历结果：,H,D,I,B,M,J,N,E,LABDIHEKJCFGMN将E出栈，访问。此时，p指向E的,22,L,A,B,D,I,H,E,K,J,C,F,G,M,N,将,K,进栈。,此时，,p,指向,K,的左孩子，为,NULL,。,A,遍历结果：,H,D,I,B,M,J,N,E,K,LABDIHEKJCFGMN将K进栈。A遍历结果：HDIBM,23,L,A,B,D,I,H,E,K,J,C,F,G,M,N,将,K,出栈，访问。此时，,p,指向,K,的右孩子，为,NULL,。,A,遍历结果：,H,D,I,B,M,J,N,E,K,LABDIHEKJCFGMN将K出栈，访问。此时，p指向K的,24,L,A,B,D,I,H,E,K,J,C,F,G,M,N,将,A,出栈，访问。此时，,p,指向,A,的右孩子,C,。,遍历结果：,H,D,I,B,M,J,N,E,K,A,LABDIHEKJCFGMN将A出栈，访问。此时，p指向A的,25,L,A,B,D,I,H,E,K,J,C,F,G,M,N,将,C,进栈。,此时，,p,指向,C,的左孩子,F,。,遍历结果：,H,D,I,B,M,J,N,E,K,C,A,LABDIHEKJCFGMN将C进栈。遍历结果：HDIBMJ,26,L,A,B,D,I,H,E,K,J,C,F,G,M,N,将,F,进栈。,此时，,p,指向,F,的左孩子，为,NULL,。,遍历结果：,H,D,I,B,M,J,N,C,F,E,K,A,LABDIHEKJCFGMN将F进栈。遍历结果：HDIBMJ,27,L,A,B,D,I,H,E,K,J,C,F,G,M,N,F,出栈，访问。,此时，,p,指向,F,的右孩子,L,。,遍历结果：,H,D,I,B,M,J,N,C,E,K,A,F,LABDIHEKJCFGMNF出栈，访问。遍历结果：HDIB,28,L,A,B,D,I,H,E,K,J,C,F,G,M,N,将,L,进栈。,此时，,p,指向,L,的左孩子，为,NULL,。,遍历结果：,H,D,I,B,M,J,N,C,L,E,K,A,F,LABDIHEKJCFGMN将L进栈。遍历结果：HDIBMJ,29,L,A,B,D,I,H,E,K,J,C,F,G,M,N,L,出栈，访问。,此时，,p,指向,L,的右孩子，为,NULL,。,遍历结果：,H,D,I,B,M,J,N,C,E,K,A,F,L,LABDIHEKJCFGMNL出栈，访问。遍历结果：HDIB,30,L,A,B,D,I,H,E,K,J,C,F,G,M,N,C,出栈，访问。,此时，,p,指向,C,的右孩子,G,。,遍历结果：,H,D,I,B,M,J,N,E,K,A,F,L,C,LABDIHEKJCFGMNC出栈，访问。遍历结果：HDIB,31,L,A,B,D,I,H,E,K,J,C,F,G,M,N,将,G,进栈。,此时，,p,指向,G,的左孩子，为,NULL,。,遍历结果：,H,D,I,B,M,J,N,G,E,K,A,F,L,C,LABDIHEKJCFGMN将G进栈。遍历结果：HDIBMJ,32,L,A,B,D,I,H,E,K,J,C,F,G,M,N,将,G,进栈。,此时，,p,指向,G,的右孩子，为,NULL,。,遍历结果：,H,D,I,B,M,J,N,G,E,K,A,F,L,C,LABDIHEKJCFGMN将G进栈。遍历结果：HDIBMJ,33,L,A,B,D,I,H,E,K,J,C,F,G,M,N,此时，栈为空，且,p,为,NULL,。,遍历结束。,遍历结果：,H,D,I,B,M,J,N,G,E,K,A,F,L,C,LABDIHEKJCFGMN此时，栈为空，且p为NULL。遍,34,非递归中序遍历二叉树课件,35,
展开阅读全文