二叉树基于栈的递归消除

递归转非递归的原因

递归执行效率低；（有进入、保存、出来、恢复四个操作）
有些运行环境没有递归机制

递归转换的两种方法

• 直接尾递归
  可转化为直线型：用循环代替递归，例如求阶乘
• 复杂情况
  采用工作栈消除递归，例如二叉树的遍历

基于栈的递归消除

在大量复杂的情况下，递归的问题无法直接转换成循环，需要采用工作栈消除递归。
将递归中系统隐含的栈=》用户自己操纵的栈（工作栈提供一种控制结构）

递归进层时，需要保留信息 递归进层的三件事如下：

1. 保存本层参数，返回地址（断点）
2. 传递参数，分配局部数据空间（给下一层参数赋值）
3. 控制转移。（转向下一个开始）

递归退层时，需要恢复信息

1. 恢复上层（恢复返回结果和保存的断点信息）
2. 传递结果
3. 转断点执行。

从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;
        }
    }
}

非递归中序遍历

二叉树中序遍历的非递归算法的关键：在中序遍历过某结点的整个左子树后，如何找到该结点的根及右子树。

基本思想：

1. 建立一个栈
2. 根结点进栈，遍历左子树
3. 根节点出栈，输出根节点，遍历右子树

下面是我的算法实现，其中的栈是自定义的（顺便复习一下栈），也可以用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;
                }
            }
        }
    }
}