二叉树遍历基础 -- 递归与非递归的实现方法
二叉树遍历基础 -- 递归与非递归的实现方法
之前也写过不少关于二叉树的东西了，但是总体来说，二叉树还是一个很绕的东西，所以单独择出来写一篇笔记，之前也没计划什么的，就想到什么写什么吧。不过该篇文章的主要内容是关于二叉树的三种遍历（前序、中序、后序）不同的实现方式（递归与非递归）。
首先，我觉得很有必要去彻底理解一下递归。
（1）递归的主体大概分两部分：递归停止的条件、递归内容。
（2）递归应用的实例：这个超级多，就比如最典型的斐波那契数列。个人认为，可以用循环实现的，递归基本上都可以实现，但有时递归的效率不如循环。
（3）递归又分为单递归与多递归（二叉树的三种遍历递归方法均用到了双递归！）
根据上面的三点，举个例子先。
假设当x=0时，F(x)=1；否则F(x)=F(n-1)*n。这个时候就可以用递归了，代码实现如下。
class Solution{
public int F(int n)
{
//递归停止条件
if (n == 0)
{
return 1;
}
//递归内容
else
{
return F(n - 1) * n;
}
}
}代码分析一下如下：
二叉树的三种遍历：前序（根左右）、中序（左根右）、后序（左右根）
首先看三种遍历的递归实现方法。（特点：代码清晰，量少，但不易理解）
// （1）前序遍历
public TreeNode PreOrder(TreeNode pRoot)
{
//递归终止条件
if (pRoot != null)
{
// 根->左->右
Console.Write(pRoot.data + " ");
PreOrder(pRoot.left);
PreOrder(pRoot.right);
}
}
// （2）中序遍历
public TreeNode MidOrder(TreeNode pRoot)
{
//递归终止条件
if (node != null)
{
// 左->根->右
MidOrder(pRoot.left);
Console.Write(pRoot.data + " ");
MidOrder(pRoot.right);
}
}
// （3）后序遍历
public TreeNode PostOrder(TreeNode pRoot)
{
//递归终止条件
if (pRoot != null)
{
// 左->右->根
PostOrder(pRoot.left);
PostOrder(pRoot.right);
Console.Write(pRoot.data + " ");
}
} 分析：
表达能力是多么重要的事情啊，会是一回事，表述清楚又是一回事。难受啊，马飞。。
当然，我写的东西可能有点乱，但是想表现几个想法：
递归和栈是密不可分的。
上述三个方法均存在一个打印，两个递归，但是唯一的区别就是顺序的不同，所以，如何理解呢！！！关键点：如果打印在递归后面，则递归是不受打印影响的，也就是，我递归要先执行完，才开始执行你打印，但是如果打印在递归前面，相当于打印已经属于这个递归体了，没次递归的时候都要执行一次打印！！！
非递归下如何实现三种遍历。
// 前序遍历
public void PreOrderNoRecurise(Node<T> node)
{
if (node == null)
{
return;
}
// 定义一个栈存放数据
Stack<Node<T>> stack = new Stack<Node<T>>();
//把根节点放进去
stack.Push(node);
//定义一个空节点名称
Node<T> tempNode = null;
while (stack.Count > 0)
{
// 根节点出栈打印
tempNode = stack.Pop();
Console.Write(tempNode.data);
// 右子节点进栈
if (tempNode.right != null)
{
stack.Push(tempNode.right);
}
// 左子节点进栈
if (tempNode.left != null)
{
stack.Push(tempNode.left);
}
}
}
//中序遍历
public void MidOrderNoRecurise(Node<T> node)
{
if (node == null)
{
return;
}
// 定义一个栈存放数据
Stack<Node<T>> stack = new Stack<Node<T>>();
//定义一个空节点
Node<T> tempNode = node;
while (tempNode != null || stack.Count > 0)
{
// 左子节点进栈
while(tempNode != null)
{
stack.Push(tempNode);
tempNode = tempNode.left;
}
// 2.出栈遍历节点并打印
tempNode = stack.Pop();
Console.Write(tempNode.data);
// 3.左子节点遍历结束则跳转到右子节点
tempNode = tempNode.right;
}
}
//后序遍历
public void PostOrderNoRecurise(Node<T> node)
{
if (root == null)
{
return;
}
// 两个栈：一个存储，一个输出
Stack<Node<T>> stackIn = new Stack<Node<T>>();
Stack<Node<T>> stackOut = new Stack<Node<T>>();
Node<T> currentNode = null;
// 根节点进栈
stackIn.Push(node);
// 左->右->根
while (stackIn.Count > 0)
{
currentNode = stackIn.Pop();
stackOut.Push(currentNode);
// 左子节点进栈
if (currentNode.left != null)
{
stackIn.Push(currentNode.left);
}
// 右子节点进栈
if (currentNode.right != null)
{
stackIn.Push(currentNode.right);
}
}
while (stackOut.Count > 0)
{
// 依次遍历各节点
Node<T> outNode = stackOut.Pop();
Console.Write(outNode.data);
}
}非递归方法变化多样，上述代码借鉴Edison Zhou的文章，自己不想写了，哈哈，但是道理并不难懂，不会向递归那样难理解，有时间的时候再慢慢修改补充吧。。