没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
如何用栈实现递归与非递归的转换
递归与非递归转换的基础知识是能够正确理解三种树的遍历方法:前序、中序和后序,
第一篇就是关于这三种遍历方法的递归和非递归算法。
(一)三种遍历树的算法
一、为什么要学习递归与非递归的转换的实现方法?
1)并不是每一门语言都支持递归的。B
2)有助于理解递归的本质。B
3)有助于理解栈,树等数据结构。
二、三种遍历树的递归和非递归算法
递归与非递归的转换基于以下的原理:所有的递归程序都可以用树结构表示出来。需
要说明的是,这个“原理”并没有经过严格的数学证明,只是我的一个猜想,不过在至少在
我遇到的例子中是适用的。学习过树结构的人都知道,有三种方法可以遍历树:前序,中
序,后序。理解这三种遍历方式的递归和非递归的表达方式是能够正确实现转换的关键之
处,所以我们先来谈谈这个。需要说明的是,这里以特殊的二叉树来说明,不过大多数情
况下二叉树已经够用,而且理解了二叉树的遍历,其它的树遍历方式就不难了。
1)前序遍历
A)递归方式:
void preorder_recursive(Bitree T) /* 先序遍历二叉树的递归算法B*/
{
if (T) {
visit(T); /* 访问当前结点B*/
preorder_recursive(T->lchild); /* 访问左子树B*/
preorder_recursive(T->rchild); /* 访问右子树B*/
}
}
B)非递归方式B
void preorder_nonrecursive(Bitree T) /* 先序遍历二叉树的非递归算法B*/
{
initstack(S);
push(S,T); /* 根指针进栈B*/
while(!stackempty(S)) {
while(gettop(S,p)&&p) { /* 向左走到尽头B*/
visit(p); /* 每向前走一步都访问当前结点B*/
push(S,p->lchild);
}
pop(S,p);
if(!stackempty(S)) { /* 向右走一步B*/
pop(S,p);
push(S,p->rchild);
}
}
}
2)中序遍历
A)递归方式B
void inorder_recursive(Bitree T) /* 中序遍历二叉树的递归算法B*/
{
if (T) {
inorder_recursive(T->lchild); /* 访问左子树B*/
visit(T); /* 访问当前结点B*/
inorder_recursive(T->rchild); /* 访问右子树B*/
}
}
B)非递归方式B
void inorder_nonrecursive(Bitree T)
{
initstack(S); /* 初始化栈B*/
push(S, T); /* 根指针入栈B*/
while (!stackempty(S)) {
while (gettop(S, p) && p) /* 向左走到尽头B*/
push(S, p->lchild);
pop(S, p); /* 空指针退栈B*/
if (!stackempty(S)) {
pop(S, p);
visit(p); /* 访问当前结点B*/
push(S, p->rchild); /* 向右走一步B*/
}
}
}
3)后序遍历
A)递归方式B
void postorder_recursive(Bitree T) /* 中序遍历二叉树的递归算法B*/
{
if (T) {
postorder_recursive(T->lchild); /* 访问左子树B*/
postorder_recursive(T->rchild); /* 访问右子树B*/
visit(T); /* 访问当前结点B*/
}
}
B)非递归方式B
typedef struct {
BTNode* ptr;
enum {0,1,2} mark;
} PMType; /* 有 mark 域的结点指针类型B*/
void postorder_nonrecursive(BiTree T) /*后续遍历二叉树的非递归算法B*/
{
PMType a;
initstack(S); /* S 的元素为 PMType 类型B*/
push (S,{T,0}); /* 根结点入栈B*/
while(!stackempty(S)) {
pop(S,a);
switch(a.mark)
{
case 0:B
push(S,{a.ptr,1}); /* 修改 mark 域B*/
if(a.ptr->lchild)
push(S,{a.ptr->lchild,0}); /* 访问左子树B*/
break;
case 1:B
push(S,{a.ptr,2}); /* 修改 mark 域B*/
if(a.ptr->rchild)
push(S,{a.ptr->rchild,0}); /* 访问右子树B*/
break;
case 2:B
visit(a.ptr); /* 访问结点B*/
}
}
}
(二)原理分析以及例子
第二篇在第一篇的基础之上分析递归与非递归转换的原理同时给出一些相关的例子进
行分析。
三、实现递归与非递归的换转原理和例子
一)原理分析
通常,一个函数在调用另一个函数之前,要作如下的事情:
A)将实在参数,返回地址等信息传递给被调用函数保存;
B)为被调用函数的局部变量分配存储区;
C)将控制转移到被调函数的入口。B
从被调用函数返回调用函数之前,也要做三件事情:
A)保存被调函数的计算结果;
B)释放被调函数的数据区;
C)依照被调函数保存的返回地址将控制转移到调用函数。
剩余11页未读,继续阅读
资源评论
swell624
- 粉丝: 5
- 资源: 5
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功