非递归中序遍历二叉树-课件（PPT讲稿）.ppt

文档介绍：L ABDIH EKJ CFG MN 二叉树的非递归遍历 2L ABDIH EKJ CFG MN 非递归中序遍历二叉树: 先访问左子树,再访问根节点,最后访问右子树。设置一个栈,出栈即为访问节点。先将根节点的左节点全部进栈,然后出栈一个节点,访问。将该节点的右孩子节点进栈,再将右孩子节点的所有左节点全部进栈...如此这般直到栈空为止。 void InOrderTraverse ( BiTree T, Status ( * visit)( ElemType e)) { BiTree pStack [100], 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 = pStack [top--]; visit(p->data); p = p-> rchild ; }}}}L ABDIH EKJ CFG MN 设置一个栈,出栈即为访问该结点。L ABDIH EKJ CFG MN 先将根节点及其左孩子全部进栈。 p->L ABDIH EKJ CFG MN 将根结点 A进栈。此时, p指向 A的左孩子 B。 A p->L ABDIH EKJ CFG MN 将根结点 A的左孩子 B进栈。此时, p指向 B的左孩子 D。 A B p->L ABDIH EKJ CFG MN 将B的左孩子 D进栈。此时, p指向 D的左孩子 H。 A B D p->L ABDIH EKJ CFG MN 将D的左孩子 H进栈。此时, p指向 H的左孩子,为 NULL 。 A B D HL ABDIH EKJ CFG MN H出栈,访问。此时, p指向 H的右孩子,为 NULL 。 A B D遍历结果: H