# Binary Tree - 二叉樹 二叉樹是每個節點最多有兩個子樹的樹結構，子樹有左右之分，二叉樹常被用于實現**二叉查找樹**和**二叉堆**。 二叉樹的第i層至多有 2i?12^{i-1}2i?1 個結點；深度為k的二叉樹至多有 2k?12^k-12k?1 個結點；對任何一棵二叉樹T，如果其終端結點數為 n0n_0n0, 度為2的結點數為 n2n_2n2, 則 n0=n2+1n_0=n_2+1n0=n2+1。 一棵深度為 kkk, 且有 2k?12^k-12k?1 個節點稱之為**滿二叉樹**；深度為 kk k，有 nnn 個節點的二叉樹，當且僅當其每一個節點都與深度為 kkk 的滿二叉樹中序號為 111 至 nnn 的節點對應時，稱之為**完全二叉樹**。完全二叉樹中重在節點標號對應。 ### 編程實現 ### Python ~~~ class TreeNode: def __init__(self, val): self.val = val self.left, self.right = None, None ~~~ ### C++ ~~~ struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; ~~~ ### Java ~~~ public class TreeNode { public int val; public TreeNode left, right; public TreeNode(int val) { this.val = val; this.left = null; this.right = null; } } ~~~ ### 樹的遍歷 從二叉樹的根節點出發，節點的遍歷分為三個主要步驟：對當前節點進行操作（稱為“訪問”節點，或者根節點）、遍歷左邊子節點、遍歷右邊子節點。訪問節點順序的不同也就形成了不同的遍歷方式。需要注意的是樹的遍歷通常使用遞歸的方法進行理解和實現，在訪問元素時也需要使用遞歸的思想去理解。實際實現中對于前序和中序遍歷可嘗試使用遞歸實現。 按照訪問根元素(當前元素)的前后順序，遍歷方式可劃分為如下幾種： - 深度優先：先訪問子節點，再訪問父節點，最后訪問第二個子節點。根據根節點相對于左右子節點的訪問先后順序又可細分為以下三種方式。 1. 前序(pre-order)：先根后左再右 1. 中序(in-order)：先左后根再右 1. 后序(post-order)：先左后右再根 - 廣度優先：先訪問根節點，沿著樹的寬度遍歷子節點，直到所有節點均被訪問為止。 如下圖所示，遍歷順序在右側框中，紅色A為根節點。使用遞歸和整體的思想去分析遍歷順序較為清晰。 二叉樹的廣度優先遍歷和樹的前序/中序/后序遍歷不太一樣，前/中/后序遍歷使用遞歸，也就是棧的思想對二叉樹進行遍歷，廣度優先一般使用隊列的思想對二叉樹進行遍歷。 如果已知中序遍歷和前序遍歷或者后序遍歷，那么就可以完全恢復出原二叉樹結構。其中最為關鍵的是前序遍歷中第一個一定是根，而后序遍歷最后一個一定是根，中序遍歷在得知根節點后又可進一步遞歸得知左右子樹的根節點。但是這種方法也是有適用范圍的：元素不能重復！否則無法完成定位。  ### 樹類題的復雜度分析 對樹相關的題進行復雜度分析時可統計對每個節點被訪問的次數，進而求得總的時間復雜度。 ### Binary Search Tree - 二叉查找樹 一顆**二叉查找樹(BST)**是一顆二叉樹，其中每個節點都含有一個可進行比較的鍵及相應的值，且每個節點的鍵都**大于等于左子樹中的任意節點的鍵**，而**小于右子樹中的任意節點的鍵**。 使用中序遍歷可得到有序數組，這是二叉查找樹的又一個重要特征。 二叉查找樹使用的每個節點含有**兩個**鏈接，它是將鏈表插入的靈活性和有序數組查找的高效性結合起來的高效符號表實現。