c#实现二叉树+二叉树遍历彻底理解

天上白玉宫 2017-07-12

展开全文

本来只是一个复习的，但是为了能系统的理解性复习所以在此花了一段时间来写这个博文，同时为了贡献自己的知识，让那些初学者彻底理解递归调用，写了写自我的理解。一直受那句的影响：只有对一个知识和技术有足够的理解后，才能写出简单易懂的教程。

1.二叉树的实现

二叉树的插入：首先给一个初始节点，接下来：如果插入的节点比这个节点大，插入到树的左边，否则插入到树的右边，这是在左右节点为空的情况下。但是此时我们如果左边有节点怎么办，此时如果我们在Insert函数中再次调用Insert函数时，系统会执行进栈操作，系统会把当前的节点压入栈中，调用左孩子或者右孩子的Insert函数，所以如果一直有左孩子，会一直执行进栈操作直到没有判断的这个节点没有左孩子为止，这样就新建一个节点赋给这个节点的左孩子。二叉树的遍历：同插入类似：由于在主函数中初始的那个值作为根节点（那个t，它的值就是1），在遍历的时候首先判断它有没有左孩子，如果有左孩子就一直执行进栈操作，这样节点的打印操作都无法执行，但是一旦发现节点没有左孩子，就先执行一个打印操作，这样输出的树中最左边孩子节点的值，接着判断有没有右孩子如果有，就再次执行进栈操作，这样如果既没有左孩子右没有了右孩子就执行退栈操作。同时为了能使节点数据能用于比计较（可以想象成节点泛型数据是数值型数据集合）需要使数据类型继承IComparable接口（其实数值型数据能直接比较大小就是继承了这个接口）。

[csharp] view plain copy

using System;
public class Tree<TItem> where TItem : IComparable<TItem> //继承的这个接口用于通用比较
{
public Tree(TItem nodeValue)
{
this.NodeData = nodeValue;//泛型数据
this.LeftTree = null; //左孩子
this.RightTree = null; //右孩子
}
public void Insert(TItem newItem) //树的插入操作实现二叉排序树
{
TItem currentNodeValue = this.NodeData;
if (currentNodeValue.CompareTo(newItem) > 0)
{
if (this.LeftTree == null)
{
this.LeftTree = new Tree<TItem>(newItem);
}
else
{
this.LeftTree.Insert(newItem);
}
}
else
{
if (this.RightTree == null)
{
this.RightTree = new Tree<TItem>(newItem);
}
else
{
this.RightTree.Insert(newItem);
}
}
}
//以下执行左中右的遍历方式
public void WalkTree() //树的遍历
{
if (this.LeftTree != null)
{
this.LeftTree.WalkTree();
}
Console.WriteLine(this.NodeData.ToString());
if (this.RightTree != null)
{
this.RightTree.WalkTree();
}
}
private TItem NodeData; //节点
private Tree<TItem> LeftTree; //左孩子
private Tree<TItem> RightTree; //右孩子
}
class Test
{
public static void Main()
{
Tree<int> t = new Tree<int>(1); //二叉树初始节点
t.Insert(2);
t.Insert(-1);
t.Insert(3);
t.Insert(-3);
t.Insert(-2);
t.WalkTree();//二叉树的遍历
}
}

2.二叉树遍历的理解

如果对于上述遍历仍然不清楚可以看看下面对于二叉树的遍历理解

要想彻底的理解递归就必须对程序调用子程序的过程有所了解，也就是系统对程序点的压栈和出栈操作，在主程序调用子程序的时候，系统是将子程序的入口点做压栈操作，在调用完子程序后，系统执行退栈操作，继续从主程序的位置往下执行。如果子程序中还有子程序，就会多次执行压栈和退栈操作。如图左边是二叉树，右边是遍历代码。

首先判断根节点A的左子树是否为空，因为A有左子树所以执行代码1，这是相当于执行子程序了，系统为了保证程序能正常执行，需要现将1位置处的断点压栈，为的就是在执行完子程序后能让主程序继续执行，所以：我们可以想象系统在执行节点A时将代码1位置的断点压栈（我们在这里为了简单就说将A压栈），接着执行节点A的左子树B的遍历，由于节点B还是有左子树，所以继续将B压栈，由于D没有左子树，所以执行D层中的打印语句（也就是代码2），接着判断D有没有右子树，发现D没有右子树，于是系统开始出栈操作，这时的栈中有那些断点呢

栈：A B
B出栈，断点出栈后，程序是从断点的下一条指令开始执行，因为if语句中没有指令了，于是就从2开始执行，调用打印B的操作，接着由于B有右子树，所以开始执行3，此时再次将B层的这个断点压栈，去执行E层的代码，由于E没有左子树所以执行打印E的操作，同时E没有右孩子，所以退栈到B层，但是B层的下一条指令没有了，于是B层执行完了跳出B层回到A层，此时栈中保存的是A层的1处的断点，所以继续上面的思路执行A层的代码2打印A，接着由于A有右孩子，于是C进栈，和前面的思路一样，打印完F，退回到C层打印C，最后打印G，在G层执行完后退回到C层3处，同样C层没有可执行的代码跳出C层，继续退回到A层3出，A层3处的下一条指令也没有了，于是A层执行完跳出，至此栈中也空程序执行完毕。