搜题
  1. 问题易首页
  2. 大学
导航：题目详情 | 答案解析 | 相关问题 | 最新问题

试编写出先序 中序和后序遍历的非递归算法。

大学 递归,遍历,算法 已帮助 人

试编写出先序、中序和后序遍历的非递归算法。

请帮忙给出正确答案和分析，谢谢！

热搜：二叉树的中序遍历的递归形式和非递归形式

答案解析

难度★★☆ 搜索

  • 正确答案：(1)先序遍历。 void PreOrderTraverse(BiTree bt) { ／*二叉树bt采用二叉链表存储对其进行先序遍历*／ if(bt) ／*二叉树非空*／ {InitStack(S)；Push(Sbt)； while(!EmptyStack(S)) {while(GetTop(Sp)&&p) ／*当栈顶元素非空*／ {visit(p一>data)； push(SP一>ichild)； Pop(SP)； if(!EmptyStack(S)) ／*若栈非空使栈顶元素的右孩子人栈*／ {Pop(Sp)；Push(SP一>rchild)；) } } } (2)中序遍历。 void InOrderTraverse(BiTree bt) { ／*二叉树bt采用二叉链表存储对其进行中序遍历*／ if(bt) {InitStack(s)；Push(sbt)； while(!EmptyStack(S)) {while(GetTop(Sp)&&p) push(SP一>ichild)； Pop(SP)； if(!EmptyStack(S)) {Pop(SP)； visit(p一>data)； Push(SP一>rchild)； } } } } (3)后序遍历。 voidFeorder(BiTreebt) { ／*后序遍历bt所指的二又树s为存储二叉树结点指针的栈*／ InitStack(S)；Push(Sbt)； while(!EmptyStack(S)) {while(GetTop(SP)) Push(SP一>ichild)； Pop(SP)； if(!EmptyStack(S)) {Push(SGetTop(Sp)一>rchild)； if(GetTop(sP)==NULL) {Pop(sP);Pop(sP); visit(P一>data); while(GetTop(sq)一>rchild==p&&!EmptyStack(s)) {Pop(sP); visit(P一>data); } if(!EmptyStack(s)) Push(sGetTop(sP)一>rchild); } } } }
    将一个递归算法转换成一个非递归算法，利用栈就可消除递归，根据对二叉树进行先序、中序和后序遍历的思想，其非递归算法描述如下。