递归转非递归的原因
递归执行效率低；（有进入、保存、出来、恢复四个操作）
有些运行环境没有递归机制
递归转换的两种方法
- 直接尾递归
可转化为直线型：用循环代替递归，例如求阶乘 - 复杂情况
采用工作栈消除递归，例如二叉树的遍历
基于栈的递归消除
在大量复杂的情况下，递归的问题无法直接转换成循环，需要采用工作栈消除递归。
将递归中系统隐含的栈=》用户自己操纵的栈（工作栈提供一种控制结构）
递归进层时，需要保留信息 递归进层的三件事如下：
- 保存本层参数，返回地址（断点）
- 传递参数，分配局部数据空间（给下一层参数赋值）
- 控制转移。（转向下一个开始）
递归退层时，需要恢复信息
- 恢复上层（恢复返回结果和保存的断点信息）
- 传递结果
- 转断点执行。
从C++中序遍历二叉树分析递归
void Inorde(BiTree root)
{
if(root!=null) //L1断点
Inorder(root->LChild);
Visit(root->data); //L2断点
Inorder(root->RChild); //L3断点
}
非递归先序遍历
static void PreOrderNoRecursion(TreeNode<string> tree)
{
if (tree == null)
return;
Stack<TreeNode<string>> stack = new Stack<TreeNode<string>>();
TreeNode<string> node = tree;
while (node != null || stack.Any()) //栈不空
{
if (node != null)
{
stack.Push(node);
Console.WriteLine(node.data);
node = node.lchrild;
}
else
{
var item = stack.Pop();
node = item.rchrild;
}
}
}
非递归中序遍历
二叉树中序遍历的非递归算法的关键：在中序遍历过某结点的整个左子树后，如何找到该结点的根及右子树。
基本思想：
- 建立一个栈
- 根结点进栈，遍历左子树
- 根节点出栈，输出根节点，遍历右子树
下面是我的算法实现，其中的栈是自定义的（顺便复习一下栈），也可以用C#系统提供的栈
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace NotRecursion
{
/// <summary>
///链栈的结点
/// </summary>
/// <typeparam name="T"></typeparam>
class StackNode<T>
{
public T data;
public StackNode<T> next;
public StackNode()
{
this.data = default(T);
this.next = null;
}
public StackNode(T data)
{
this.data = data;
}
}
/// <summary>
/// 链栈类
/// </summary>
/// <typeparam name="T"></typeparam>
class LinkStack<T>
{
StackNode<T> head;
/// <summary>
/// 构造
/// </summary>
public LinkStack()
{
head = new StackNode<T>();
}
/// <summary>
/// 判空
/// </summary>
/// <returns></returns>
public bool IsEmpty()
{
return head.next == null;
}
/// <summary>
/// 入栈
/// </summary>
/// <param name="data"></param>
public void Push(T data)
{
StackNode<T> node = new StackNode<T>(data);
//挂载结点
node.next = head.next;
head.next = node;
}
/// <summary>
/// 出栈
/// </summary>
/// <returns></returns>
public T Pop()
{
if (IsEmpty())
{
Console.WriteLine("栈空");
return default(T);
}
//保留首结点
StackNode<T> node = head.next;
//悬空首结点
head.next = head.next.next;
return node.data;
}
/// <summary>
/// 读栈顶
/// </summary>
/// <returns></returns>
public T Peek()
{
return head.next.data;
}
}
/// <summary>
/// 二叉树结点
/// </summary>
/// <typeparam name="T"></typeparam>
class TreeNode<T>
{
public T data;
public TreeNode<T> lchrild;
public TreeNode<T> rchrild;
public TreeNode(T data)
{
this.data = data;
}
}
class Program
{
static void Main(string[] args)
{
TreeNode<string> A = new TreeNode<string>("a");
TreeNode<string> B = new TreeNode<string>("b");
TreeNode<string> C = new TreeNode<string>("c");
TreeNode<string> D = new TreeNode<string>("d");
TreeNode<string> E = new TreeNode<string>("e");
TreeNode<string> F = new TreeNode<string>("f");
TreeNode<string> G = new TreeNode<string>("g");
TreeNode<string> H = new TreeNode<string>("h");
A.lchrild = B;
B.rchrild = D;
A.rchrild = C;
D.lchrild = F;
D.rchrild = G;
C.rchrild = E;
E.rchrild = H;
PreOrderNoRecursion(A);
}
//中序遍历非递归算法
static void PreOrderNoRecursion(TreeNode<string> tree)
{
//创建栈对象
LinkStack<TreeNode<string>> linkStack = new LinkStack<TreeNode<string>>();
TreeNode<string> p = tree;
while (p != null || !linkStack.IsEmpty())
{
if (p != null)
{ //将根节点入栈
linkStack.Push(p);
//访问其左子树
p = p.lchrild;
}
else
{
//将根节点出栈
TreeNode<string> q = linkStack.Pop();
//打印根节点
Console.WriteLine(q.data);
//访问其右子树
p = q.rchrild;
}
}
}
}
}
网友评论