前序遍历二叉树,中序遍历二叉树,后序遍历二叉树 c#实现

using System.Collections.Generic;
    using System.Collections;
    class BiTree
    {

       public BiTree leftChild;
        public BiTree rightChild;

        public object Data;

        public BiTree(object aData)
        {
            Data = aData;
        }

    }

    class TestUtil
    {

        public static void Main()
        {

            BiTree root = new BiTree("1");

            BiTree n1 = new BiTree("2");
            BiTree n2 = new BiTree("3");
            BiTree n3 = new BiTree("4");
            BiTree n4 = new BiTree("5");
            BiTree n5 = new BiTree("6");
            BiTree n6 = new BiTree("7");

            root.leftChild = n1;
            root.rightChild = n2;
            n1.leftChild = n3;
            n1.rightChild = n4;
            n2.leftChild = n5;
            n2.rightChild = n6;

            //PreTravelCur(root);
            Console.WriteLine("中序:");
            MidTravelStack(root);
            Console.WriteLine("前序:");
            PreTravelStack(root);
            Console.WriteLine("后序:");
            LastTravelStack(root);
            Console.Read();

        }

        /// <summary>
        /// 前序遍历,递归
        /// </summary>
        /// <param name="tree"></param>
        public static void PreTravelCur(BiTree tree)
        {
            if (tree != null)
            {
                Console.WriteLine(tree.Data);
                PreTravelCur(tree.leftChild);
                PreTravelCur(tree.rightChild);
            }
        }

        /// <summary>
        /// 中序遍历
        /// </summary>
        /// <param name="tree"></param>
        public static void MidTravelStack(BiTree tree)
        {
            if (tree == null)
            {
                return;
            }

            Stack<object> stack = new Stack<object>();

            BiTree p = tree;

            do
            {
                while (p != null)
                {
                    stack.Push(p);
                    p = p.leftChild;
                }
                p =(BiTree) stack.Pop();

                Console.WriteLine(p.Data);
                p = p.rightChild;

            } while (stack.Count > 0|| p != null);

        
        }

        /// <summary>
        /// 前序遍历
        /// </summary>
        /// <param name="tree"></param>
        public static void PreTravelStack(BiTree tree)
        {

            if (tree == null)
                return;
            Stack<object> stack = new Stack<object>();
            BiTree p = tree;

            do
            {
                while (p != null)
                {
                    Console.WriteLine(p.Data);
                    stack.Push(p);
                    p = p.leftChild;

                }
                p = (BiTree)stack.Pop();
                p = p.rightChild;

            } while (stack.Count > 0 || p != null);

        }

        /// <summary>
        /// 要用两个栈，比前两种复杂
        /// </summary>
        /// <param name="tree"></param>
        public static void LastTravelStack(BiTree tree)
        {

            if (tree == null)
                return;
            //放访问过的节点
            Stack<BiTree> stack1 = new Stack<BiTree>();
            //放节点是否访问过　标志
            Stack<bool> stackFlag = new Stack<bool>();

            BiTree p=tree;
            do
            {
                while (p != null)
                {
                    stack1.Push(p);
                    stackFlag.Push(false);
                    p = p.leftChild;
                }
               
                p = stack1.Pop();
                bool flag = stackFlag.Pop();

                //第一次访问
                if (!flag)
                {
                    stack1.Push(p);
                    stackFlag.Push(true);
                    p = p.rightChild;
                }//第二次访问　
                else
                {
                    Console.WriteLine(p.Data);
                    p = null;
                }

            }
            //栈不为空　或者　指针不为空
            while (stack1.Count > 0 || p != null);

        }
      
    }