二叉樹(Binary Tree)
二叉樹（Binary Tree）是一種樹形數(shù)據(jù)結(jié)構(gòu)，由節(jié)點構(gòu)成，每個節(jié)點最多有兩個子節(jié)點：一個左子節(jié)點和一個右子節(jié)點。
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) { this.val = val; }
}
基本概念
"二叉樹"（Binary Tree）這個名稱的由來是因為二叉樹的每個節(jié)點最多有兩個子節(jié)點，一個左子節(jié)點和一個右子節(jié)點。其中，“二叉”指的是兩個，因此“二叉樹”表示每個節(jié)點最多可以分支成兩個子節(jié)點?；径x：
- 每個節(jié)點包含一個值（或數(shù)據(jù)），另外最多有兩個子節(jié)點。
- 左子節(jié)點和右子節(jié)點的順序是固定的，左邊的子節(jié)點是左子節(jié)點，右邊的子節(jié)點是右子節(jié)點。
- 一個節(jié)點可以沒有子節(jié)點（葉節(jié)點），也可以有一個子節(jié)點或兩個子節(jié)點（內(nèi)部節(jié)點）。
相關(guān)基本概念：
- 根節(jié)點（Root）： 二叉樹的頂部節(jié)點稱為根節(jié)點，是樹的起始點。
- 節(jié)點（Node）： 二叉樹的基本構(gòu)建單元。每個節(jié)點包含一個值（或數(shù)據(jù)）以及指向左子節(jié)點和右子節(jié)點的指針。
- 父節(jié)點（Parent Node）： 一個節(jié)點的直接上級節(jié)點，如果存在的話。例如，一個節(jié)點的左子節(jié)點的父節(jié)點是該節(jié)點本身。
- 葉節(jié)點（Leaf Node）： 沒有子節(jié)點的節(jié)點稱為葉節(jié)點，即左子節(jié)點和右子節(jié)點都為空。
- 子樹（Subtree）： 以某個節(jié)點為根的樹，它包括該節(jié)點及其所有后代節(jié)點。
- 高度（Height）： 從某個節(jié)點到其最遠葉節(jié)點的最長路徑上的邊數(shù)，也稱為節(jié)點的層數(shù)。葉節(jié)點的高度為0。
在二叉樹基本定義上，加上一些規(guī)則，可以衍生出更多種類的二叉樹。比如：
二叉搜索樹（Binary Search Tree，BST）： 一種特殊的二叉樹，滿足以下性質(zhì)：對于樹中的每個節(jié)點，其左子樹中的值都小于該節(jié)點的值，而其右子樹中的值都大于該節(jié)點的值。BST通常用于實現(xiàn)有序數(shù)據(jù)集合。
完全二叉樹（Complete Binary Tree）： 一個二叉樹，其所有層次（深度）除了最后一層外，都是完全填充的，且最后一層的節(jié)點從左到右填充，沒有空隙。
平衡二叉樹（Balanced Binary Tree）： 一種高度平衡的二叉樹，其中每個節(jié)點的兩棵子樹的高度差不超過1。平衡二叉樹通常用于提高查找、插入和刪除操作的性能。
預(yù)備基礎(chǔ)算法 —— 遞歸（Recursion）
下一部分要寫的是二叉樹基本遍歷代碼實現(xiàn)其實可以有多種，思量后用遞歸實現(xiàn)應(yīng)該是初接觸者比較簡潔好理解的方式。為此，在寫二叉樹下一部分內(nèi)容之前簡單寫下基礎(chǔ)遞歸算法，以保證本系列文章承前啟后。
遞歸(Recursion),在數(shù)學(xué)與計算機科學(xué)中對其描述的說法有很多，比如：
- 指在函數(shù)的定義中使用函數(shù)自身的方法；
- 指一種通過重復(fù)將問題分解為同類的子問題而解決問題的方法；
（PS：這里同類子問題對于于上一種說法就是函數(shù)自身） - 指由一種（或多種）簡單的基本情況定義的一類對象或方法，并規(guī)定其他所有情況都能被還原為其基本情況。
（PS：這里描述的基本情況對應(yīng)于第一種說法中的函數(shù)自身了）
當(dāng)然本文非學(xué)術(shù)著作"哪種描述比較合適"在此不多做分析，從編碼實踐的角度第一種說法更為地氣一點。
“將問題分解為同類的子問題” 這一點是用遞歸的方式來解題的關(guān)鍵，這里用個簡單的累加和的例子:
設(shè)計一個函數(shù)，輸入?yún)?shù)為 n ，返回 1+2+...n 的和。
public int sum(int n){
int result = 0;
for (int i = 1; i <= n ; i++) {
result = result + i;
}
return result;
}
想想初學(xué) C 語言for循環(huán)的時候應(yīng)該都有寫過上述代碼，從 1開始遞增加到 n 這其實是典型的遞推。那如果用遞歸的思路來思考的話：
求 1+2+..n 的和（問題） -> 就是 n 加上 求 1+2+..（n-1） 的和（同類的子問題）;
其中最基本的情況 1 的和 為 1。
public int sum( int n ) {
if( 1 == n) return 1;
return n + sum(n-1);
}
可以看到遞歸的代碼實現(xiàn)上是不是非常簡潔。大部分初學(xué)者思考上比較習(xí)慣于遞推，如果第一次接觸遞歸角度思考會有些不適應(yīng)（或者無法獨立分析出來遞歸）也是正常。當(dāng)慢慢熟悉后，會發(fā)現(xiàn)用遞歸的思路解決某些算法問題往往會非常簡單（在本篇接下來的內(nèi)容中就能發(fā)現(xiàn)這點）。
在 初學(xué)遞歸 過度到 熟悉遞歸 這個階段，筆者建議可以考慮把一些用遞推已經(jīng)解決了的問題 用 遞歸的思路嘗試解決，習(xí)慣遞歸思路后會打開一片新世界。
基本遍歷（Traversal）
二叉樹的遍歷是指按照一定的順序訪問二叉樹的所有節(jié)點。在二叉樹中，有三種常見的遍歷方式，它們分別是前序遍歷、中序遍歷和后序遍歷。
先序遍歷（Preorder Traversal）
從根節(jié)點開始，首先訪問根節(jié)點，然后按照前序遍歷的方式依次訪問左子樹和右子樹。前序遍歷通常用于復(fù)制一棵樹或計算表達式的值。
訪問順序：根節(jié)點 -> 左子樹 -> 右子樹
Leetcode 144. 二叉樹的前序遍歷【簡單】
給你二叉樹的根節(jié)點 root ，返回它節(jié)點值的 前序 遍歷。
中序遍歷（Inorder Traversal）
從根節(jié)點開始，首先按照中序遍歷的方式訪問左子樹，然后訪問根節(jié)點，最后訪問右子樹。中序遍歷通常用于訪問二叉搜索樹中的節(jié)點，以升序或降序訪問節(jié)點值。
訪問順序：左子樹 -> 根節(jié)點 -> 右子樹
Leetcode 94. 二叉樹的中遍歷【簡單】
給定一個二叉樹的根節(jié)點 root ，返回 它的 中序 遍歷 。
針對后序遍歷（Postorder Traversal）從根節(jié)點開始，首先按照后序遍歷的方式訪問左子樹，然后訪問右子樹，最后訪問根節(jié)點。后序遍歷通常用于釋放二叉樹的內(nèi)存，或計算表達式的值。訪問順序：左子樹 -> 右子樹 -> 根節(jié)點，在此不過多描述相信一定能夠完成編碼。
反向構(gòu)建
Leetcode 105. 從前序與中序遍歷序列構(gòu)造二叉樹【中等】
給定兩個整數(shù)數(shù)組 preorder 和 inorder ，其中 preorder 是二叉樹的先序遍歷， inorder 是同一棵樹的中序遍歷，請構(gòu)造二叉樹并返回其根節(jié)點。
綜合應(yīng)用
本系列文章中已經(jīng)介紹了鏈表、遞歸、二叉樹，解決算法問題往往會需要綜合應(yīng)用。不妨來看下下面這個問題：
Leetcode 114. 二叉樹展開為鏈表【中等】
給你二叉樹的根結(jié)點 root ，請你將它展開為一個單鏈表：
展開后的單鏈表應(yīng)該同樣使用 TreeNode ，其中 right 子指針指向鏈表中下一個結(jié)點，而左子指針始終為 null 。
展開后的單鏈表應(yīng)該與二叉樹 先序遍歷 順序相同。文章來源：http://www.zghlxwxcb.cn/news/detail-711484.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-711484.html
總結(jié)下
- 介紹了二叉樹的的一些基本概念包括：根節(jié)點、葉子節(jié)點、高度等等；
- 介紹了基礎(chǔ)算法遞歸的思想：“重復(fù)將問題分解為同類的子問題而解決問題的方法”；
- 介紹了基本的二叉樹遍歷 和 反向構(gòu)建的相關(guān)思路；
- 結(jié)合本系列先前文章內(nèi)容，解決綜合鏈表、遞歸、二叉樹的問題，靈活處理使用數(shù)據(jù)結(jié)構(gòu)的特征是關(guān)鍵。
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法 | 二叉樹(Binary Tree)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
