二叉樹遍歷
以下圖為例：

image.png

二叉樹的結(jié)構(gòu)

樹節(jié)點定義：

 public class TreeNode
        {
            public int val = 0;
            public TreeNode left = null;
            public TreeNode right = null;
            public TreeNode(int value)
            {
                this.val = value;
            }
            public TreeNode(int val,TreeNode left, TreeNode right)
            {
                this.left = left;
                this.right = right;
                this.val = val;
            }
        }

主程序：定義樹的結(jié)構(gòu)并采取某種遍歷輸出結(jié)果

static void Main(string[] args)
        {
            TreeNode e = new TreeNode(1);
            TreeNode g = new TreeNode(2);
            TreeNode h = new TreeNode(3);
            TreeNode i = new TreeNode(4);
            TreeNode d = new TreeNode(5, null, g);
            TreeNode f = new TreeNode(6, h, i);
            TreeNode b = new TreeNode(7, d, e);
            TreeNode c = new TreeNode(8, f, null);
            TreeNode root = new TreeNode(9, b, c);
            PrintTree(root);
            Console.ReadLine();
        }

◆中序遍歷

◆先處理左子樹，然后處理當(dāng)前節(jié)點伏伯，再處理右子樹橘洞。
◆對于一顆二叉查找樹，所有的信息都是有序排列的说搅，中序遍歷可以是信息有序輸出炸枣，且運行時間為O（n）。
◆遞歸實現(xiàn)中序遍歷：

 //中序遍歷
        public static void PrintTree(TreeNode t)
        {
            if (t != null)
            {
                PrintTree(t.left);
                Console.Write(t.val + " ");
                PrintTree(t.right);
;            }
        }

結(jié)果

image.png

◆先序遍歷

◆先處理當(dāng)前節(jié)點蜓堕，在處理左右子樹抛虏。
◆遞歸實現(xiàn)先序遍歷：

        //先序遍歷
        public static void PrintTree(TreeNode t)
        {
            if (t != null)
            {
                Console.Write(t.val + " ");
                PrintTree(t.left);
                PrintTree(t.right);
            }
        }

image.png

◆后序遍歷

◆先處理左右子樹，然后再處理當(dāng)前節(jié)點套才，運行時間為O（n）迂猴。
◆遞歸實現(xiàn)后序遍歷：

//后序遍歷
        public static void PrintTree(TreeNode t)
        {
            if (t != null)
            {
                PrintTree(t.left);
                PrintTree(t.right);
                Console.Write(t.val + " ");
            }
        }

image.png

◆層序遍歷:

層序遍歷就是按照層次由左向右輸出
◆算法思想：
利用隊列

 public static void PrintTree(TreeNode tree)
        {
            if (tree == null)
                return;

            Queue<TreeNode> queue = new Queue<TreeNode>();
            queue.Enqueue(tree);

            while (queue.Any())
            {
                var item = queue.Dequeue();
                Console.Write(item.val+" ");

                if (item.left != null)
                {
                    queue.Enqueue(item.left);
                }

                if (item.right != null)
                {
                    queue.Enqueue(item.right);
                }
            }

        }

結(jié)果

image.png