二叉树遍历

[TOC] ## 遍历二叉树 构建一棵树后，我们希望遍历它，有四种遍历方法： 1. 先序遍历：先访问根节点，再访问左子树，最后访问右子树。 2. 后序遍历：先访问左子树，再访问右子树，最后访问根节点。 3. 中序遍历：先访问左子树，再访问根节点，最后访问右子树。 4. 层次遍历：每一层从左到右访问每一个节点。 先创建数数据 ``` // 二叉树 type TreeNode struct { Data string // 节点用来存放数据 Left *TreeNode // 左子树 Right *TreeNode // 右字树 } func main() { t := &TreeNode{Data: "A"} t.Left = &TreeNode{Data: "B"} t.Right = &TreeNode{Data: "C"} t.Left.Left = &TreeNode{Data: "D"} t.Left.Right = &TreeNode{Data: "E"} t.Right.Left = &TreeNode{Data: "F"} } ```  ### 先序遍历 先访问根节点，再访问左子树，最后访问右子树 方式一:前序递归遍历 ``` func preorderTraversal(root *TreeNode) { if root==nil{ return } // 先访问根再访问左右 fmt.Println(root.Data) preorderTraversal(root.Left) preorderTraversal(root.Right) } // 输出 // A B D E C F ``` - 尽可能深的搜索树的分支 - 这种算法不会根据图的结构等信息调整执行策略  ### 中序遍历 先访问左子树，再访问根节点，最后访问右子树 ``` func inorderTraversal(tree *TreeNode) { if tree == nil { return } // 先打印左子树 inorderTraversal(tree.Left) // 再打印根节点 fmt.Print(tree.Data, " ") // 再打印右字树 inorderTraversal(tree.Right) } // 输出 // D B E A F C ```  ### 后序遍历 先访问左子树，再访问右子树，最后访问根节点 ``` func inorderTraversal(tree *TreeNode) { if tree == nil { return } // 先打印左子树 inorderTraversal(tree.Left) // 再打印右字树 inorderTraversal(tree.Right) fmt.Print(tree.Data, " ") } // 输出 // D E B F C A ```