非递归后序遍历二叉树.pptx

《非递归后序遍历二叉树.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、LABDIHEKJCFGMN二叉树的非递归遍历LABDIHEKJCFGMN非递归后序遍历二叉树：先访问左子树，再访问右子树，最后访问根节点。设置一个栈。先将根节点的左节点全部进栈。出栈一个节点，将该节点的右孩子进栈，再将右孩子的左节点全部进栈...当一个节点的左、右孩子都被访问过后再访问该节点，如此这般直到栈空为止。(判断某节点的右孩子是否被访问，需要单独设置一个指针跟踪刚刚访问的节点。在后序遍历中，某节点的右孩子节点一定刚好在该节点之前被访问)voidPostOrderTraverse(BiTreeT,Status(*visit)(ElemTypee)){BiTr

2、eepStack[100],p;inttop=-1,sign;BiTreeroot=T;if(root!=NULL){do{while(root!=NULL){pStack[++top]=root;root=root->lchild;}/**/p=NULL;sign=1;while(top!=-1&&sign){root=pStack[top];if(root->rchild==p){visit(root->data);top--;p=root;}else{root=root->rchild;sign=0;}}/**/}while(top!=-1);}}LABDIH

3、EKJCFGMN设置一个栈，在可访问访问结点的情况后出栈。LABDIHEKJCFGMN将A根结点进栈。此时p指向A的左孩子B。ALABDIHEKJCFGMN将B进栈。此时p指向B的左孩子D。ABLABDIHEKJCFGMN将D进栈。此时p指向D的左孩子H。ABDLABDIHEKJCFGMN将H进栈。此时p指向H的左孩子，为NULL。pTmp也为NULL。ABDHLABDIHEKJCFGMNwhile(top!=-1&&sign):获取栈顶H，p指向H，由于H右孩子不存在，访问H，H出栈。此时，pTmp指向已被访问的H结点。sign置为已访问。ABD遍历结果：HLAB

4、DIHEKJCFGMNwhile(top!=-1&&sign):获取栈顶D，p指向D，由于D右孩子存在，不访问D。此时，把p指向D的右孩子I，pTmp仍指向已被访问的H结点。sign置为0。AB遍历结果：HDLABDIHEKJCFGMNwhile(p!=NULL):将I进栈，p指向I的左孩子，为NULL。此时，pTmp置为NULL。sign置为0。AB遍历结果：HDILABDIHEKJCFGMNwhile(top!=-1&&sign):获取栈顶I，p指向I，由于I右孩子不存在，访问I，I出栈。此时，pTmp指向已被访问的I结点。sign置为已访问。AB遍历结果：HD

5、ILABDIHEKJCFGMNwhile(top!=-1&&sign):获取栈顶D，p指向D，由于D右孩子I已被访问，访问D，D出栈。此时，pTmp指向已被访问的D结点。sign置为已访问。AB遍历结果：HIDLABDIHEKJCFGMNwhile(top!=-1&&sign):获取栈顶B，p指向B，由于B右孩子存在，不访问B。此时，把p指向B的右孩子E，pTmp仍指向已被访问的D结点。sign置为0。AB遍历结果：HIDLABDIHEKJCFGMNwhile(p!=NULL):将E进栈。此时p指向E的左孩子J。AB遍历结果：HIDELABDIHEKJCFGMNwh

6、ile(p!=NULL):将J进栈。此时p指向J的左孩子M。AB遍历结果：HIDEJLABDIHEKJCFGMNwhile(p!=NULL):将M进栈。此时p指向M的左孩子，为NULL。pTmp也为NULL。sign置为1。AB遍历结果：HIDEJMLABDIHEKJCFGMNwhile(top!=-1&&sign):获取栈顶M，p指向M，由于M右孩子不存在，访问M，M出栈。此时，pTmp指向已被访问的M结点。sign置为已访问。AB遍历结果：HIDEJMLABDIHEKJCFGMNwhile(top!=-1&&sign):获取栈顶J，p指向J，由于J右孩子存在，不

7、访问J。此时，把p指向J的右孩子K，pTmp仍指向已被访问的M结点。sign置为0。AB遍历结果：HIDEJMLABDIHEKJCFGMNwhile(p!=NULL):将N进栈，p指向N的左孩子，为NULL。此时，pTmp置为NULL。sign置为0。AB遍历结果：HIDEJMNLABDIHEKJCFGMNwhile(top!=-1&&sign):获取栈顶N，p指向N，由于N右孩子不存在，访问N，N出栈。此时，pTmp指向已被访问的N结点。sign置为已访问。AB遍历结果：HIDEJMNLABDIHEKJCFGMNwhile(top!=-1&&sign):获取栈