[TOC] ## 概述 樹是一種比較高級的基礎數據結構 樹的定義： 1. 有節點間的層次關系，分為父節點和子節點。 2. 有唯一一個根節點，該根節點沒有父節點。 3. 除了根節點，每個節點有且只有一個父節點。 4. 每一個節點本身以及它的后代也是一棵樹，是一個遞歸的結構。 5. 沒有后代的節點稱為葉子節點，沒有節點的樹稱為空樹。 ### 二叉樹 * 每個節點最多只有兩個子節點的樹 ### 滿二叉樹 * 葉子節點與葉子節點之間的高度差為`0`的二叉樹，即整棵樹是滿的，樹呈滿三角形結構 ### 完全二叉樹 * 完全二叉樹是由滿二叉樹而引出來的，設二叉樹的深度為`k`，除第`k`層外，其他各層的節點數都達到最大值，且第`k`層所有的節點都連續集中在最左邊 樹根據兒子節點的多寡，有二叉樹，三叉樹，四叉樹等 ## 二叉樹的實現 數組也可以用來表示二叉樹，一般用來表示完全二叉樹 ``` // 二叉樹 type TreeNode struct { Data string // 節點用來存放數據 Left *TreeNode // 左子樹 Right *TreeNode // 右字樹 } ```  :-: 一個完全二叉樹