[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 ```