非递归前序遍历二叉树

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

1、LABDIHEKJCFGMN二叉树的非递归遍历LABDIHEKJCFGMN非递归前序遍历二叉树：先访问根节点，再访问左子树，最后访问右子树。设置一个栈，出栈即为访问节点。先将根节点进栈，在栈不空时一直如下循环：出栈，访问，将其右孩子进栈，再将左孩子进栈。voidPreOrderTraverse(BTNode*T,Status(*visit)(ElementTypee)){BTNode*stack[MAX_SIZE],*p;inttop=-1;if(T!=NULL){stack[++top]=T;while(top>-1){p=stack[top--];visit(p->

2、data);if(p->rchild!=NULL){stack[++top]=p->rchild;}if(p->lchild!=NULL){stack[++top]=p->lchild;}}}}LABDIHEKJCFGMN设置一个栈，出栈即为访问该结点。LABDIHEKJCFGMNA先将根节点进栈LABDIHEKJCFGMNA在栈不空时一直如下循环：出栈，访问，将其右孩子进栈，再将左孩子进栈。LABDIHEKJCFGMNA出栈，访问。LABDIHEKJCFGMN将A右孩子C进栈CLABDIHEKJCFGMN将A左孩子B进栈CBLABDIHEKJCFGMNB出栈，访问。CL

3、ABDIHEKJCFGMN将B右孩子E进栈CELABDIHEKJCFGMN将B左孩子D进栈CEDLABDIHEKJCFGMND出栈，访问。CELABDIHEKJCFGMN将D右孩子I进栈CEILABDIHEKJCFGMN将D左孩子H进栈CEIHLABDIHEKJCFGMNH出栈，访问。CEILABDIHEKJCFGMNH已是叶子结点，没有左右孩子进栈操作了。CEILABDIHEKJCFGMNI出栈，访问。CELABDIHEKJCFGMNI已是叶子结点，没有左右孩子进栈操作了。CELABDIHEKJCFGMNE出栈，访问。CLABDIHEKJCFGMN将E右孩子K进栈。CK

4、LABDIHEKJCFGMN将E左孩子J进栈。CKJLABDIHEKJCFGMNJ出栈，访问。CKLABDIHEKJCFGMN将J右孩子N进栈。CKNLABDIHEKJCFGMN将J左孩子M进栈。CKNMLABDIHEKJCFGMNM出栈，访问。CKNLABDIHEKJCFGMNM已是叶子结点，没有左右孩子进栈操作了。CKNLABDIHEKJCFGMNN出栈，访问。CKLABDIHEKJCFGMNN已是叶子结点，没有左右孩子进栈操作了。CKLABDIHEKJCFGMNK出栈，访问。CLABDIHEKJCFGMNK已是叶子结点，没有左右孩子进栈操作了。CLABDIHEKJC

5、FGMNC出栈，访问。LABDIHEKJCFGMN将C右孩子G进栈。GLABDIHEKJCFGMN将C左孩子F进栈。GFLABDIHEKJCFGMNF出栈，访问。GLABDIHEKJCFGMN将F右孩子L进栈。GLLABDIHEKJCFGMNF没有左孩子进栈操作了。GLLABDIHEKJCFGMNL出栈，访问。GLABDIHEKJCFGMNL已是叶子结点，没有左右孩子进栈操作了。GLABDIHEKJCFGMNG出栈，访问。LABDIHEKJCFGMNG已是叶子结点，没有左右孩子进栈操作了。LABDIHEKJCFGMN此时，栈为空。遍历结束。