之前也写过不少关于二叉树的东西了,但是总体来说,二叉树还是一个很绕的东西,所以单独择出来写一篇笔记,之前也没计划什么的,就想到什么写什么吧。不过该篇文章的主要内容是关于二叉树的三种遍历(前序、中序、后序)不同的实现方式(递归与非递归)。
首先,我觉得很有必要去彻底理解一下递归。
(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的文章,自己不想写了,哈哈,但是道理并不难懂,不会向递归那样难理解,有时间的时候再慢慢修改补充吧。。