두 갈래 나무의 깊이 우선 귀속, 비귀속 범람, 넓이 우선 범람 실례

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace BinaryTreeDemo
{
    class Program
    {
        static void Main(string[] args)
        {
            BinaryTree tree = new BinaryTree();
            int[] data = new int[] {4,8,10,34,17,1,45,3};
            for(int i=0;i<data.Length;i++)
            {
                tree.AddData(data[i]);
            }
            Console.Write("          ：");
            tree.PreOrder(tree.RootNode);
            Console.Write("
");

            Console.Write("          ：");
            tree.MidOrder(tree.RootNode);
            Console.Write("
");

            Console.Write("          ：");
            tree.AfterOrder(tree.RootNode);
            Console.Write("
");

            Console.Write("        ：");
            tree.DepthFirst();
            Console.Write("
");

            Console.WriteLine("----------------------------        ---------------------------");
            Console.Write("           ：");
            tree.nonrecursivePreOrder(tree.RootNode);
            Console.Write("
");

            Console.Write("           ：");
            tree.nonrecursiveMidOrder(tree.RootNode);
            Console.Write("
");

            Console.Write("           ：");
            tree.nonrecursiveAfterOrder(tree.RootNode);
            Console.Write("
");
            
        }
    }

    public class BinaryTree
    {
         public sealed class TreeNode
        {
            private int _nodevalue; //   
            private TreeNode _leftnode; //    
            private TreeNode _rightnode; //    

             //       
            public TreeNode(int nodevalue)
            {
                this._nodevalue = nodevalue;
                this._leftnode = null;
                this._rightnode = null;
            }

            //  
            public int NodeValue
            {
                get
                {
                    return this._nodevalue;
                }
            }

            public TreeNode LeftNode
            {
                get
                {
                    return this._leftnode;
                }
                set
                {
                    if (this._leftnode == null)
                    {
                        if (value != null)
                        {
                            this._leftnode = value;
                        }
                        else
                        {
                            //done
                        }
                    }
                    else
                    {
                        //done
                    }
                }
            }


            public TreeNode RightNode
            {
                get
                {
                    return this._rightnode;
                }
                set
                {
                    if (this._rightnode == null)
                    {
                        if (value != null)
                        {
                            this._rightnode = value;
                        }
                        else
                        {
                            //done
                        }
                    }
                    else
                    {
                        //done
                    }
                }
            }
        }

        private TreeNode _rootnode; //       

        public TreeNode RootNode
        {
            get
            {
                return this._rootnode;
            }
        }

        //        
        public BinaryTree()
        {
            this._rootnode = null;
        }

        //        --              ，       ，               （               ，           ，      ）     ，            。
        public void AddData(int num)
        {
            TreeNode node = new TreeNode(num);
            if (this._rootnode == null)
            {
                this._rootnode = node;
            }
            else //     ，      
            {
                TreeNode currentnode = this._rootnode; 
                this.compareData(currentnode, node);
            }
        }

        public void compareData(TreeNode currentnode, TreeNode newnode)
        {
            if (newnode.NodeValue <= currentnode.NodeValue) //       
            {
                if (currentnode.LeftNode == null) 
                {
                    currentnode.LeftNode = newnode; //    ，  
                }
                else //      ，        
                {
                    currentnode = currentnode.LeftNode; 
                    this.compareData(currentnode, newnode);
                }
            }
            else //       
            {
                if (currentnode.RightNode == null)
                {
                    currentnode.RightNode = newnode;  //    ，  
                }
                else //      ，        
                {
                    currentnode = currentnode.RightNode;
                    this.compareData(currentnode, newnode);
                }
            }
        }

        public void PreOrder(TreeNode node) //    
        {
            if (node != null)
            {               
                Console.Write(node.NodeValue.ToString() + "\t");
                this.PreOrder(node.LeftNode);
                this.PreOrder(node.RightNode);
            }
            else
            {
                //done
            }
        }

        public void MidOrder(TreeNode node) //    
        {
            if (node != null)
            {
                this.MidOrder(node.LeftNode);
                Console.Write(node.NodeValue.ToString()+"\t");
                this.MidOrder(node.RightNode);
            }
            else
            {
                //done
            }
        }

        public void AfterOrder(TreeNode node) //    
        {
            if (node != null)
            {
                AfterOrder(node.LeftNode);
                AfterOrder(node.RightNode);
                Console.Write(node.NodeValue.ToString() + "\t");
            }
        }

        public void DepthFirst() //      
        {

            Queue treequeue = new Queue();
            treequeue.Enqueue(this.RootNode);
            while (treequeue.Count > 0)
            {
                TreeNode node = (TreeNode)treequeue.Dequeue();
                Console.Write(node.NodeValue.ToString() + "\t");
                if (node.LeftNode != null)
                {
                    treequeue.Enqueue(node.LeftNode);
                }
                if (node.RightNode != null)
                {
                    treequeue.Enqueue(node.RightNode);
                }
            }
        }

        public void nonrecursivePreOrder(TreeNode node) //        
        {
            if (node != null)
            {
                Console.Write(node.NodeValue.ToString()+"\t"); //     
                Stack<TreeNode> treestack = new Stack<TreeNode>(); //     TreeNode    
                treestack.Push(node); //     
                TreeNode temp = node.LeftNode; //     
                while (treestack.Count > 0 ||temp !=null)
                {
                    while (temp != null)
                    {
                        Console.Write(temp.NodeValue.ToString()+"\t");
                        treestack.Push(temp);
                        temp = temp.LeftNode;//     
                    }
                    temp = treestack.Pop(); //          
                    temp = temp.RightNode; //              
                }
            }
            else
            {
                //done
            }
        } 

        public void nonrecursiveMidOrder(TreeNode node) //        
        {
            if (node != null)
            {
                Stack<TreeNode> treestack = new Stack<TreeNode>();
                treestack.Push(node);
                TreeNode temp = node.LeftNode;
                while (treestack.Count > 0 || temp != null)
                {
                    while (temp != null)
                    {
                        treestack.Push(temp);
                        temp = temp.LeftNode;
                        
                    }
                    temp = treestack.Pop();
                    Console.Write(temp.NodeValue.ToString()+"\t");
                    temp = temp.RightNode;
                }
            }
            else
            {
                //done
            }
        }

        public void nonrecursiveAfterOrder(TreeNode node) //        
        {
            if (node != null)
            {
                Stack<TreeNode> treestack = new Stack<TreeNode>();
                treestack.Push(node);
                TreeNode preNode = null;
                TreeNode currNode = null;
                while (treestack.Count > 0 )
                {
                    currNode = treestack.Peek();
                    if (preNode == null || preNode.LeftNode == currNode || preNode.RightNode == currNode)
                    {
                        if (currNode.LeftNode != null)
                        {
                            treestack.Push(currNode.LeftNode);
                        }
                        else  if(currNode.RightNode!=null)
                        {
                            treestack.Push(currNode.RightNode);
                        }
                    }
                    else if (currNode.LeftNode == preNode)
                    {
                        if (currNode.RightNode != null)
                        {
                            treestack.Push(currNode.RightNode);
                        }
                    }
                    else
                    {
                        Console.Write(currNode.NodeValue.ToString()+"\t");
                        treestack.Pop();
                    }
                    preNode = currNode;
                }
            }
            else
            {
                //done
            }
        }
    }
}