先序遍历二叉树的非递归算法
1个回答
展开全部
InitStack(S);//初始化栈
p=T;//取栈顶
while(P||!StackEmpty(S)){
//P存在或者栈非空
if(p)
{
//p非空，即左子树或者右子树存在
Push(S,p);
//将左子树入栈
p=p->lchild;
//取下一个左子树
}
else{
Pop(S,p);
//出栈，相当于先序遍历了，因为左子树都TMD入栈了，现在反向输出
p=p->rchild;
//弹出一个左子树，就同时取其右子树右子树，然后又跳到这个if的最开头那里，p存在的那个分支。接下来再取右子树的左子树
}
}
//其实，用递归也许你更能理解一些。但是，递归本质上也是压栈，只不过是程序压栈，还不如这个效率高
p=T;//取栈顶
while(P||!StackEmpty(S)){
//P存在或者栈非空
if(p)
{
//p非空，即左子树或者右子树存在
Push(S,p);
//将左子树入栈
p=p->lchild;
//取下一个左子树
}
else{
Pop(S,p);
//出栈，相当于先序遍历了，因为左子树都TMD入栈了，现在反向输出
p=p->rchild;
//弹出一个左子树，就同时取其右子树右子树，然后又跳到这个if的最开头那里，p存在的那个分支。接下来再取右子树的左子树
}
}
//其实，用递归也许你更能理解一些。但是，递归本质上也是压栈，只不过是程序压栈，还不如这个效率高
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
