非递归中序遍历二叉树共35张课件.ppt

1、LABDIHEKJCFGMN二叉树的非递归遍历二叉树的非递归遍历LABDIHEKJCFGMN 非递归中序遍历二叉树：非递归中序遍历二叉树：先访问左子树，再访问根节点，最后先访问左子树，再访问根节点，最后访问右子树。访问右子树。设置一个栈，出栈即为访问节点。先设置一个栈，出栈即为访问节点。先将根节点的左节点全部进栈，然后出将根节点的左节点全部进栈，然后出栈一个节点，访问。将该节点的右孩栈一个节点，访问。将该节点的右孩子节点进栈，再将右孩子节点的所有子节点进栈，再将右孩子节点的所有左节点全部进栈左节点全部进栈.如此这般直到栈空如此这般直到栈空为止。为止。void InOrderTraverse(B

2、iTree 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;LABDIHEKJCFGMN设置一个栈，出栈即为访问该结点。LABDIHEKJCFGMN先将根节点及其左孩子全部进栈。p-LABDIHEKJCFGMN将根结点A进栈。此时，p指向A的左孩子B。Ap-LABDIHEKJCFGMN将

3、根结点A的左孩子B进栈。此时，p指向B的左孩子D。ABp-LABDIHEKJCFGMN将B的左孩子D进栈。此时，p指向D的左孩子H。ABDp-LABDIHEKJCFGMN将D的左孩子H进栈。此时，p指向H的左孩子，为NULL。ABDHLABDIHEKJCFGMNH出栈，访问。此时，p指向H的右孩子，为NULL。ABD遍历结果：HLABDIHEKJCFGMND出栈，访问。此时，p指向D的右孩子I。AB遍历结果：HDLABDIHEKJCFGMN将I进栈。此时，p指向I的左孩子，为NULL。AB遍历结果：HDILABDIHEKJCFGMNI出栈，访问。此时，p指向I的右孩子，为NULL。AB遍历结果

4、：H DILABDIHEKJCFGMNB出栈，访问。此时，p指向B的右孩子E。A遍历结果：H DIBp-LABDIHEKJCFGMN将E进栈。此时，p指向E的左孩子J。A遍历结果：H DIBELABDIHEKJCFGMN将E的左孩子J进栈。此时，p指向J的左孩子M。A遍历结果：H DIBEJLABDIHEKJCFGMN将J的左孩子M进栈。此时，p指向M左孩子，为NULL。A遍历结果：H DIBEJMLABDIHEKJCFGMNM出栈，访问。此时，p指向M的右孩子，为NULL。A遍历结果：H DIBEJMLABDIHEKJCFGMNJ出栈，访问。此时，p指向J的右孩子N。A遍历结果：H DIBE

5、MJLABDIHEKJCFGMN将N进栈。此时，p指向N的左孩子，为NULL。A遍历结果：H DIBEMJNLABDIHEKJCFGMN将N出栈，访问。此时，p指向N的右孩子，为NULL。A遍历结果：H DIBEMJNLABDIHEKJCFGMN将E出栈，访问。此时，p指向E的右孩子K。A遍历结果：H DIB MJNELABDIHEKJCFGMN将K进栈。此时，p指向K的左孩子，为NULL。A遍历结果：H DIB MJNEKLABDIHEKJCFGMN将K出栈，访问。此时，p指向K的右孩子，为NULL。A遍历结果：H DIB MJNEKLABDIHEKJCFGMN将A出栈，访问。此时，p指向A

6、的右孩子C。遍历结果：H DIB MJNEKALABDIHEKJCFGMN将C进栈。此时，p指向C的左孩子F。遍历结果：H DIB MJNEKCALABDIHEKJCFGMN将F进栈。此时，p指向F的左孩子，为NULL。遍历结果：H DIB MJNCFEKALABDIHEKJCFGMNF出栈，访问。此时，p指向F的右孩子L。遍历结果：H DIB MJNCEKAFLABDIHEKJCFGMN将L进栈。此时，p指向L的左孩子，为NULL。遍历结果：H DIB MJNCLEKAFLABDIHEKJCFGMNL出栈，访问。此时，p指向L的右孩子，为NULL。遍历结果：H DIB MJNCEKAFLLABDIHEKJCFGMNC出栈，访问。此时，p指向C的右孩子G。遍历结果：H DIB MJNEKAFLCLABDIHEKJCFGMN将G进栈。此时，p指向G的左孩子，为NULL。遍历结果：H DIB MJNGEKAFLCLABDIHEKJCFGMN将G进栈。此时，p指向G的右孩子，为NULL。遍历结果：H DIB MJNGEKAFLCLABDIHEKJCFGMN此时，栈为空，且p为NULL。遍历结束。遍历结果：H DIB MJNGEKAFLC