C＃实现二叉树非递归中序遍历程序

本文讲解C#实现二叉树非递归中序遍历程序

1、非递归中序遍历
///
/// 非递归中序遍历
///
///
static void InOrder2(BiTNode T) {
SqStack S = new SqStack();
S.data = new BiTNode[MaxSize];
InitStack(ref S);
BiTNode p = T;
while (p!=null||!StackEmpty(S)) {
if (p != null)
{
Push(ref S, p);
p = p.lchild;
}
else {
PoP(ref S, ref p);
visit§;
p = p.rchild;
}

        }


    }

2、节点访问
///
/// 结点值的输出
///
static void visit(BiTNode T) {
Console.Write(T.data+" ");
}
3、栈结构的实现
///
/// 栈定义
///
public struct SqStack
{
public BiTNode[] data;
public int top;//栈顶

    }
    /// <summary>
    /// 判断栈是否为空
    /// </summary>
    /// <param name=""></param>
    /// <returns></returns>
    static bool StackEmpty(SqStack S)
    {
        if (S.top == -1)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    /// <summary>
    /// 栈初始化
    /// </summary>
    /// <param name="S"></param>
    static void InitStack(ref SqStack S)
    {
        S.top = -1;
    }
    /// <summary>
    /// 压栈
    /// </summary>
    /// <param name="S"></param>
    /// <returns></returns>
    static bool Push(ref SqStack S, BiTNode e)
    {
        if (S.top >= MaxSize - 1)
        {
            return false;
        }
        S.top = S.top + 1;
        S.data[S.top] = e;//先加1，再进栈
        return true;
    }
    /// <summary>
    /// 出栈
    /// </summary>
    /// <param name="S"></param>
    /// <param name="e"></param>
    /// <returns></returns>
    static bool PoP(ref SqStack S, ref BiTNode e)
    {
        if (S.top == -1) { return false; }
        e = S.data[S.top--];//出栈
        return true;
    }
    /// <summary>
    /// 
    ///读取栈顶元素
    /// </summary>
    /// <param name="S"></param>
    /// <param name="e"></param>
    /// <returns></returns>
    bool GetTop(ref SqStack S, ref BiTNode e)
    {

        if (S.top == -1) { return false; }
        e = S.data[S.top];//读取元素
        return true;

    }

5、main函数测试
public const int MaxSize = 50;
static void Main(string[] args)
{
BiTNode T = new BiTNode() ;
int x=0;
//创建二叉树
T.data = 1;
T.lchild= new BiTNode();
T.lchild.data = 2;
T.rchild = new BiTNode();
T.rchild.data = 3;
T.lchild.rchild=new BiTNode();
T.lchild.rchild.data = 4;
T.lchild.rchild.lchild= new BiTNode();
T.lchild.rchild.lchild.data = 6;
T.rchild.rchild = new BiTNode();
T.rchild.rchild.data = 5;
Console.WriteLine(“先序遍历的值：”);
PreOrder(T);
Console.WriteLine();
Console.WriteLine(“中序遍历的值：”);
InOrder(T);
Console.WriteLine();
Console.WriteLine(“后序遍历的值：”);
PostOrder(T);
Console.WriteLine();
Console.WriteLine(“非递归中序遍历的值：”);
InOrder2(T);
Console.WriteLine();
Console.WriteLine(“层次遍历的值：”);
LevelOrder(T);
Console.ReadLine();

    }