2. 自考
  3. 试编写出先序、中序和后序遍历的非递归算法。

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

admin2014-12-25  31
问题 试编写出先序、中序和后序遍历的非递归算法。
选项
答案 (1)先序遍历。 void PreOrderTraverse(BiTree bt) { ／*二叉树bt采用二叉链表存储，对其进行先序遍历*／ if(bt) ／*二叉树非空*／ {InitStack(S)；Push(S，bt)； while(!EmptyStack(S)) {while(GetTop(S，p)&&p) ／*当栈顶元素非空*／ {visit(p一>data)； push(S，P一>ichild)； Pop(S，P)； if(!EmptyStack(S)) ／*若栈非空，使栈顶元素的右孩子人栈*／ {Pop(S，p)；Push(S，P一>rchild)；) } } } (2)中序遍历。 void InOrderTraverse(BiTree bt) { ／*二叉树bt采用二叉链表存储，对其进行中序遍历*／ if(bt) {InitStack(s)；Push(s，bt)； while(!EmptyStack(S)) {while(GetTop(S，p)&&p) push(S，P一>ichild)； Pop(S，P)； if(!EmptyStack(S)) {Pop(S，P)； visit(p一>data)； Push(S，P一>rchild)； } } } } (3)后序遍历。 voidFeorder(BiTreebt) { ／*后序遍历bt所指的二又树，s为存储二叉树结点指针的栈*／ InitStack(S)；Push(S，bt)； while(!EmptyStack(S)) {while(GetTop(S，P)) Push(S，P一>ichild)； Pop(S，P)； if(!EmptyStack(S)) {Push(S，GetTop(S，p)一>rchild)； if(GetTop(s，P)==NULL) {Pop(s，P);Pop(s，P); visit(P一>data); while(GetTop(s，q)一>rchild==p&&!EmptyStack(s)) {Pop(s，P); visit(P一>data); } if(!EmptyStack(s)) Push(s，GetTop(s，P)一>rchild); } } } }
解析 将一个递归算法转换成一个非递归算法，利用栈就可消除递归，根据对二叉树进行先序、中序和后序遍历的思想，其非递归算法描述如下。
转载请注明原文地址:https://kaotiyun.com/show/YeVx777K
本试题收录于： 数据结构导论题库理工类分类
0

数据结构导论

理工类

相关试题推荐
随机试题
最新回复(0)