二叉树遍历
以下图为例：

image.png

二叉树的结构

树节点定义：

 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;
            }
        }

主程序：定义树的结构并采取某种遍历输出结果

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();
        }

◆中序遍历

◆先处理左子树，然后处理当前节点，再处理右子树。
◆对于一颗二叉查找树，所有的信息都是有序排列的，中序遍历可以是信息有序输出，且运行时间为O（n）。
◆递归实现中序遍历：

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

结果

image.png

◆先序遍历

◆先处理当前节点，在处理左右子树。
◆递归实现先序遍历：

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

image.png

◆后序遍历

◆先处理左右子树，然后再处理当前节点，运行时间为O（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);
                }
            }

        }

结果

image.png