二叉树遍历的非递归算法.doc

文档介绍：二叉树遍历的非递归算法1:先序遍历的非递归算法需要设计栈:保留结点的位置用于查找右孩子入栈:访问结点之后要做入栈操作出栈:某结点的左子树访问完毕之后思路:①栈初始化,p初始化②栈不空或p不为空a:若p不空:访问p所指结点,p入栈,修改p,p=p->lchild否则b:若栈不空:出栈→p,求p的右孩子p=p->rchild算法:VoidPreorder(BiTreet){//二叉树先序遍历非递归算法p=t;InitStack(s);while(p||!StackEmpty(s))if(p){printf(p->data);Push(s,p);p=p->lchild}else{Pop(s,p);p=p->rchild}}改进算法:入栈查找右孩子,可以直接让右孩子入栈2、中序遍历的非递归算法需要设计栈:保留结点的位置用于查找右孩子,访问该结点入栈:访问左子树之前要做入栈操作出栈:某结点的左子树访问完毕之后思路:①栈初始化,p初始化②栈不空或p不为空a:若p不空:p入栈,修改p,p=p->lchild否则b:若栈不空:出栈→p;访问p所指结点,求p的右孩子p=p->、后序遍历的非递归算法需要设计栈:保留结点的位置用于查找右孩子,访问该结点入栈:访问左子树之前要做入栈操作;访问右子树之前要做入栈操作出栈:某结点的左子树访问完毕之后;某结点的右子树访问完毕之后思路:①栈初始化s1,s2,p初始化②栈不空或p不为空若p不空:p入s1栈,0入s2栈,修改p,p=p->lchild否则栈不空:出栈s1→p;出栈s2→tagtag=0:p入s1栈,1入s2栈,修改p,p=p->rchildtag=1:访问p所指结点,修改p,p=NULLVoidPostorder(BiTreet){//二叉树后序遍历非递归算法p=t;InitStack(s1);InitStack(s2);while(p||!StackEmpty(s1)){if(p){Push(s1,p);Push(s2,0);p=p->lchild}else{Pop(s1,p);Pop(s2,tag);if(tag==0){Push(s1,p);Push(s2,1);p=p->rchild}else{printf(p->data);p=NULL;}}}}