C ＃ implementation of binary tree non recursive middle order traversal program

This article explains C# Implementation of binary tree non recursive middle order traversal program

1、 Non recursive middle order traversal
///
/// Non recursive middle order traversal
///
///
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、 Node access
///
/// Output of node value
///
static void visit(BiTNode T) {
Console.Write(T.data+" ");
}
3、 Implementation of stack structure
///
/// Stack definition
///
public struct SqStack
{
public BiTNode[] data;
public int top;// To the top of the stack

    }
    /// <summary>
    ///  Judge whether the stack is empty 
    /// </summary>
    /// <param name=""></param>
    /// <returns></returns>
    static bool StackEmpty(SqStack S)
    {
        if (S.top == -1)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    /// <summary>
    ///  Stack initialization 
    /// </summary>
    /// <param name="S"></param>
    static void InitStack(ref SqStack S)
    {
        S.top = -1;
    }
    /// <summary>
    ///  Pressing stack 
    /// </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;// First plus 1, Go back to the stack 
        return true;
    }
    /// <summary>
    ///  Out of the stack 
    /// </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--];// Out of the stack 
        return true;
    }
    /// <summary>
    /// 
    /// Read the top element of the stack 
    /// </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];// Read elements 
        return true;

    }

5、main Function test
public const int MaxSize = 50;
static void Main(string[] args)
{
BiTNode T = new BiTNode() ;
int x=0;
// Create a binary tree
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(“ The value of traversal first ：”);
PreOrder(T);
Console.WriteLine();
Console.WriteLine(“ The value of middle order traversal ：”);
InOrder(T);
Console.WriteLine();
Console.WriteLine(“ The value of post order traversal ：”);
PostOrder(T);
Console.WriteLine();
Console.WriteLine(“ The value of an ordered traversal in non recursion ：”);
InOrder2(T);
Console.WriteLine();
Console.WriteLine(“ Value of hierarchy traversal ：”);
LevelOrder(T);
Console.ReadLine();

    }