두 갈래 나무가 여러 가지 방식을 두루 돌아다니며 총결하다

public class TreeNode
{
    public TreeNode left;
    public TreeNode right;
    public int value;
}
public class SearchTest
{    
    // 
    private void preOrder1(TreeNode root, List dataList)
    {
        if (root != null)
        {
            dataList.Add(root.value);
            preOrder1(root.left, dataList);
            preOrder1(root.right, dataList);
        }
    }
    // 
    private List preOrder2(TreeNode root)
    {
        if (root == null)
            return null;
        List dataList = new List();
        Stack stackList = new Stack();
        TreeNode node = root;

        while (node != null || stackList.Count != 0)
        {
            if (node != null)
            {
                dataList.Add(node.value);
                stackList.Push(node);
                node = node.left;
            }
            else
            {
                node = stackList.Pop();
                node = node.right;
            }
        }
        return dataList;
    }
    // 
    private List preOrder3(TreeNode root)
    {
        if (root == null)
            return null;
        List dataList = new List();
        Stack stackList = new Stack();
        TreeNode node = root;
        stackList.Push(node);

        while (stackList.Count != 0)
        {
            node = stackList.Pop();
            dataList.Add(node.value);

            if (node.right != null)
                stackList.Push(node.right);

            if (node.left != null)
                stackList.Push(node.left);
        }
        return dataList;
    }
    // 
    private void MidOrder1(TreeNode root, List dataList)
    {
        if (root != null)
        {
            preOrder1(root.left, dataList);
            dataList.Add(root.value);
            preOrder1(root.right, dataList);
        }
    }
    // 
    private List MidOrder1(TreeNode root)
    {
        if (root == null)
            return null;
        List dataList = new List();
        Stack stackList = new Stack();
        TreeNode node = root;

        while (node != null || stackList.Count != 0)
        {
            if (node != null)
            {
                stackList.Push(node);
                node = node.left;
            }
            else
            {
                node = stackList.Pop();
                dataList.Add(node.value);
                node = node.right;
            }
        }
        return dataList;
    }

    // 
    private void PostOrder1(TreeNode root, List dataList)
    {
        if (root != null)
        {
            preOrder1(root.left, dataList);
            preOrder1(root.right, dataList);
            dataList.Add(root.value);
        }
    }

    // 
    private List PostOrder2(TreeNode root)
    {
        if (root == null)
            return null;
        TreeNode pre = null;
        TreeNode cur = root;
        List dataList = new List();
        Stack stackList = new Stack();
        stackList.Push(cur);

        while (stackList.Count != 0)
        {
            cur = stackList.Peek();

            if (cur != null)
            {
                if (cur.left == null && cur.right == null
                    || (pre != null && (pre == cur.left || pre == cur.right)))
                {
                    cur = stackList.Pop();
                    dataList.Add(cur.value);
                    pre = cur;
                }
                else
                {
                    if (cur.right != null)
                        stackList.Push(cur.right);
                    if (cur.left != null)
                        stackList.Push(cur.left);
                }
            }
        }
        return dataList;
    }

    public class PNode
    {
        public TreeNode node;
        public bool isFirst;
        public PNode(TreeNode _node, bool _isFirst)
        {
            node = _node;
            isFirst = _isFirst;
        }
    }
    // 
    private List PostOrder3(TreeNode root)
    {
        if (root == null)
            return null;
        List dataList = new List();
        Stack stackList = new Stack();
        TreeNode node = root;

        while (node != null || stackList.Count != 0)
        {
            // 
            while (node != null)
            {
                PNode pNode = new PNode(node, true);
                stackList.Push(pNode);
                node = node.left;
            }

            if (stackList.Count != 0)
            {
                PNode pNode = stackList.Pop();
                node = pNode.node;
                if (pNode.isFirst)
                {
                    pNode.isFirst = false;
                    stackList.Push(pNode);
                    node = node.right;
                }
                else
                {
                    dataList.Add(node.value);
                    node = null;
                }
            }
        }
        return dataList;
    }

    // 
    private List Search(TreeNode root)
    {
        if (root == null)
            return null;
        List dataList = new List();
        TreeNode node = root;
        Queue queueList = new Queue();

        queueList.Enqueue(node);

        while (queueList.Count != 0)
        {
            node = queueList.Dequeue();
            dataList.Add(node.value);
            if (node.left != null)
            {
                queueList.Enqueue(node.left);
            }
            if (node.right != null)
            {
                queueList.Enqueue(node.right);
            }
        }
        return dataList;
    }
    //   
}