非递归中序遍历二叉树精品课件学习教案.pptxVIP

会计学1非递归中序遍历二叉树

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

voidInOrderTraverse(BiTreeT,Status(*visit)(ElemTypee)){ BiTreepStack[100],p; inttop=-1; if(T!=NULL) { p=T; while(top-1||p!=NULL) { while(p!=NULL) { pStack[++top]=p; p=p-lchild; } if(top-1) { p=pStack[top--]; visit(p-data); p=p-rchild; } } }}第2页/共34页

LABDIHEKJCFGMN设置一个栈，出栈即为访问该结点。第3页/共34页

LABDIHEKJCFGMN先将根节点及其左孩子全部进栈。p-第4页/共34页

LABDIHEKJCFGMN将根结点A进栈。此时，p指向A的左孩子B。Ap-第5页/共34页

LABDIHEKJCFGMN将根结点A的左孩子B进栈。此时，p指向B的左孩子D。ABp-第6页/共34页

LABDIHEKJCFGMN将B的左孩子D进栈。此时，p指向D的左孩子H。ABDp-第7页/共34页

LABDIHEKJCFGMN将D的左孩子H进栈。此时，p指向H的左孩子，为NULL。ABDH第8页/共34页

LABDIHEKJCFGMNH出栈，访问。此时，p指向H的右孩子，为NULL。ABD遍历结果：H第9页/共34页

LABDIHEKJCFGMND出栈，访问。此时，p指向D的右孩子I。AB遍历结果：HD第10页/共34页

LABDIHEKJCFGMN将I进栈。此时，p指向I的左孩子，为NULL。AB遍历结果：HDI第11页/共34页

LABDIHEKJCFGMNI出栈，访问。此时，p指向I的右孩子，为NULL。AB遍历结果：HDI第12页/共34页

LABDIHEKJCFGMNB出栈，访问。此时，p指向B的右孩子E。A遍历结果：HDIBp-第13页/共34页

LABDIHEKJCFGMN将E进栈。此时，p指向E的左孩子J。A遍历结果：HDIBE第14页/共34页

LABDIHEKJCFGMN将E的左孩子J进栈。此时，p指向J的左孩子M。A遍历结果：HDIBEJ第15页/共34页

LABDIHEKJCFGMN将J的左孩子M进栈。此时，p指向M左孩子，为NULL。A遍历结果：HDIBEJM第16页/共34页

LABDIHEKJCFGMNM出栈，访问。此时，p指向M的右孩子，为NULL。A遍历结果：HDIBEJM第17页/共34页

LABDIHEKJCFGMNJ出栈，访问。此时，p指向J的右孩子N。A遍历结果：HDIBEMJ第18页/共34页

LABDIHEKJCFGMN将N进栈。此时，p指向N的左孩子，为NULL。A遍历结果：HDIBEMJN第19页/共34页

LABDIHEKJCFGMN将N出栈，访问。此时，p指向N的右孩子，为NULL。A遍历结果：HDIBEMJN第20页/共34页

LABDIHEKJCFGMN将E出栈，访问。此时，p指向E的右孩子K。A遍历结果：HDIBMJNE第21页/共34页

LABDIHEKJCFGMN将K进栈。此时，p指向K的左孩子，为NULL。A遍历结果：HDIBMJNEK第22页/共34页

LABDIHEKJCFGMN将K出栈，访问。此时，p指向K的右孩子，为NULL。A遍历结果：HDIBMJNEK第23页/共34页

LABDIHEKJCFGMN将A出栈，访问。此时，p指向A的右孩子C。遍历结果：HDIBMJNEKA第24页/共34页

LABDIHEKJCFGMN将C进栈。此时，p指向C的左孩子F。遍历结果：HDIBMJNEKCA第25页/共34页

LABDIHEKJCFGMN将F进栈。此时，p指向F的左孩子，为NULL。遍历结果：HDIBMJNCFEKA第26页/共34页

LABDIHEKJCFGMNF出栈，访问。此时，p指向F的右孩子L。遍历结果：HDIBMJNCEKAF第27页/共34页

LABDIHEKJCFGMN将L进栈。此时，p指向L的左孩子，为NULL。遍历结果：HDIBMJNCLEKAF第28页/共34页

LABDIHEKJCFGMNL出栈，访问。此时，p指向L的右孩子，为NULL。遍历结果：HDIB