hello, everyone. Long time no see. 本期文章，我們主要講解一下二叉樹的相關概念，順便也把搜索二叉樹（也叫二叉排序樹）講一下，我們直接進入正題吧！GitHub原始碼鏈接
文章目錄
- 一、二叉樹的概念
- 二、搜索二叉樹
一、二叉樹的概念
為什么要使用二叉樹？
為什么要用到樹呢?因為它通常結合了另外兩種資料結構的優點:一種是有序陣列，另一種是鏈表，在樹中查找資料項的速度和在有序陣列中查找一樣快，并且插入資料項和洗掉資料項的速度也和鏈表一樣，下面，我們先來稍微思考一下這些話題，然后再深入地研究樹的細節，
在有序陣列中插入資料太慢了，而在鏈表中查找資料也太慢了，所以到后來就有了二叉樹這種資料結構，
樹是什么？
在深入講解二叉樹前，我們先簡單地認識一下樹這個概念，樹是由若干個節點和邊組合而成，例如，可以把城市看成節點，將各個城市之間的交通路線看成邊，當然說的更準確一點，這個例子更應該是屬于圖的范疇內，關于圖的相關知識點，我們到后面再來討論，如下圖，就是一棵樹，
樹的相關術語！
? 如下圖所示
根節點
? 樹最頂端的節點稱為根節點，一棵樹只有一個根節點，一般也是整棵樹遍歷的開始，
路徑
? 設想一下，從樹中的一個節點，沿著邊走向另一個節點，所經過的節點順序排列就稱為“路徑”，
父節點
? 就像這個名稱一樣，在二叉樹中扮演“父親”的角色， 在二叉樹中的每一個節點（除了根節點），都有一個邊向上可以找到該節點的”父節點“，
子節點
? 每個節點都可能有一潭訓多條邊向下連接其他節點，下面的這些節點就稱為它的“子節點”，
葉節點
? 沒有子節點的節點稱為“葉子節點”或簡稱“葉節點”，樹中只有一個根，但是可以有很多葉節點，
子樹
? 每個節點都可以作為“子樹”的根，它和它所有的子節點，子節點的子節點等都含在子樹中，就像家族中那樣，一個節點的子樹包含它所有的子孫，
訪問
? 當程式控制流程到達某個節點時，就稱為“訪問”這個節點，通常是為了在這個節點處執行某種操作，例如查看節點某個資料欄位的值或顯示節點，如果僅僅是在路徑上從某個節點到另一個節點時經過了一個節點，不認為是訪問了這個節點，
層（深度）
? 也就相當于我們人一樣，我們這一輩人，就可以看做一層，而爸媽那一輩，又是另外一層，
關鍵字
? 如圖中所示，每個節點里，有一個數值，這個數值我們就稱為關鍵字，
滿二叉樹
? 在一顆二叉樹中，如果所有分支節點都存在左子樹和右子樹，并且所有的葉節點都在同一層上，這樣的二叉樹，稱為滿二叉樹，如上圖所示，
完全二叉樹
? 對一顆具有n個節點的二叉樹按從上至下，從左到右的順序編號，如果編號為i(1 <= i <= n)的節點與同樣深度的滿二叉樹中編號為i的節點在二叉樹中的位置完全一樣，則這棵樹就被稱為完全二叉樹，
從字面上的意思來看，滿二叉樹一定是完全二叉樹，而完全二叉樹不一定是滿的，如下圖：
二叉樹的五大性質
-
在二叉樹的第i層上，最多有2i-1個節點，例如：第三層上，最多也就有4個節點，
-
深度為k的二叉樹，最多有2k - 1個節點， 例如：深度為3的二叉樹，最多也就只有7個節點，
-
對任何一顆二叉樹，葉子節點的總數記為n0，度為2的節點的總數記為n2，則n0 = n2 + 1，解釋：度為2的節點，指的是該節點左右子節點都有的情況，我們稱為度為2的節點，那如果左右子節點，有且僅有一個的時候，我們就叫度為1的節點，
-
具有n個節點的完全二叉樹的深度為 log2n + 1，（此處的對數 向下取整）
由滿二叉樹的定義我們可以知道，深度為k的 滿二叉樹的節點數n一定等于 2k - 1，因為這是最多的節點數，再由這個公式，我們就可以倒推出
k = log2(n + 1)，比如節點數為8的滿二叉樹，深度就是3，
-
如果對一顆有n個節點的完全二叉樹的節點，按照從上至下，從左到右，對每一個節點進行編號：則有如下性質：
? 1). 如果i=1，則該節點就是這棵樹的根結點，若i不等于1，則i節點的父節點就是i / 2節點，
? 2). 如果2i > n，(n為整棵樹的總節點數)，則i節點沒有左子節點，反之就是2i就是左子節點，
? 3). 如果2i + 1 > n，(n為整棵樹的總節點數)，則i節點沒有右子節點，反之就是2i + 1就是右子節點，
二、搜索二叉樹
上面我們講解完了二叉樹的一些基本的概念，現在我們繼續來看下一個知識點：搜索二叉樹，
定義：一個節點的左子節點的關鍵字值小于這個節點，右子節點的關鍵字值大于或等于這個父節點，如下圖，就是一個搜索二叉樹，
可能會有同學已經發現了一個規律，那就是==搜索二叉樹的中序遍歷的結果就是一個升序的，==所以在判斷一顆樹是不是搜索二叉樹時，就可以從這里入手，
知道了定義，我們就可以根據定義來實作相應的代碼，
節點結構
class TreeNode {
int val; //關鍵字
TreeNode left; //左子節點
TreeNode right; //右子節點
public TreeNode(int val) {
this.val = val;
}
}
搜索二叉樹的整體框架結構
public class BST {
private TreeNode root; //根結點
public void insert(int val) { //插入新的節點
}
public void remove(int val) { //洗掉對應的節點
}
public boolean contains(int val) { //查詢是否有該值
}
}
我們就一個一個的講解每一方法具體的實作：
插入
插入新的節點，這個算是比較簡單的，我們拿到依次比較當前節點的值和傳遞進來的形參值，如果形參值更小一點，我們就往左子樹上做遞回，繼續這個操作即可，
//遞回解法
public void insert(int val) {
root = process(val, root);
}
private TreeNode process(int val, TreeNode node) {
if (node == null) { //如果當前節點為null，說明已經走到頭了，此時創建節點，回傳即可
return new TreeNode(val);
}
if (val < node.val) { //小于當前節點
node.left = process(val, node.left);
} else {
node.right = process(val, node.right); //大于等于當前節點
}
return node;
}
//非遞回解法
public void insert(int val) {
TreeNode node = new TreeNode(val); //先創建好節點
TreeNode parent = null; //父節點，用于連接新的節點
TreeNode cur = root; //當前移動的節點
if (root == null) {
root = node; //還沒有根結點的情況
} else {
while (true) {
parent = cur;
if (val < cur.val) { //小于當前節點的情況
cur = cur.left;
if (cur == null) { //如果為null了，說明走到了最后的節點
parent.left = node;
return;
}
} else { //大于當前節點的情況
cur = cur.right;
if (cur == null) {
parent.right = node; //如果為null，就走到最后節點了
return;
}
}
}
}
}
遞回與非遞回的解法，差異只是在于空間復雜度，當整棵樹很大時，遞回去呼叫，就會耗費大量的堆疊空間，而非遞回的解法，只是耗費了幾個參考的空間，
洗掉
洗掉是一個比較難的點，洗掉之后，還需要保持搜索二叉樹的結構，所以我們需要分為三種情況：
- 被洗掉節點是葉節點，
- 被洗掉節點只有一個孩子節點，
- 被洗掉節點有兩個孩子節點，
我們需要回圈遍歷這顆樹，找到需要被洗掉的節點，并且在遍歷的程序中，還需要記錄被洗掉節點的父節點是誰，以及被洗掉節點是父節點的左孩子還是右孩子，所以回圈時，有三個變數，分別是parent、cur和isLeftChild，
在找到需要被洗掉的節點后，再對這個節點進行判斷，看這個節點是葉節點？還是只有一個孩子節點？又或者是有兩個孩子節點的情況，
- 如果是葉節點，parent的left（或者是right）置為null
- 如果只有一個節點，我們就需要繞過cur節點，直接連接cur的left或者right
- 如果是有兩個節點，我們就需要找到cur的后繼節點，也就是cur的右子樹中，最小的節點，
其次我們還需要判斷被洗掉的節點，是不是root根結點？如果是，就需要更換根結點，
非遞回版本大致框架：
//非遞回版本
public boolean remove(int val) { //洗掉對應的節點
if (root == null) {
throw new RuntimeException("root is null.");
}
TreeNode parent = root;
TreeNode cur = root;
boolean isLeftChild = true;
while (cur != null && cur.val != val) { //回圈查找需要被洗掉的節點
parent = cur;
if (val < cur.val) {
cur = cur.left;
isLeftChild = true;
} else {
cur = cur.right;
isLeftChild = false;
}
}
if (cur == null) { //沒找到需要洗掉的節點
return false;
}
//找到了需要被洗掉的節點
if ( cur.left== null && cur.right == null) { //葉節點的情況
if (cur == root) {
root = null;
} else if (isLeftChild) {
parent.left = null;
} else {
parent.right = null;
}
} else if (cur.right == null) {
if (cur == root) {
root = root.left;
} else if (isLeftChild) {
parent.left = cur.left;
} else {
parent.right = cur.left;
}
} else if (cur.left == null) { //只有一個孩子節點的情況
if (cur == root) {
root = root.right;
} else if (isLeftChild) {
parent.left = cur.right;
} else {
parent.right = cur.right;
}
} else { //有兩個孩子節點的情況
TreeNode minNode = findMinNode(cur.right);
if (cur == root) {
root = minNode;
} else if (isLeftChild) {
parent.left = minNode;
} else {
parent.right = minNode;
}
minNode.left = cur.left; //新節點minNode的左孩子指向被洗掉節點cur的左孩子
// C/C++語言，需要回收cur記憶體空間
}
return true;
}
private TreeNode findMinNode(TreeNode head) {
TreeNode pre = null;
TreeNode cur = head;
TreeNode next = head.left;
while (next != null) {
pre = cur;
cur = next;
next = next.left; //一直尋找該樹的最左的節點
}
if (pre != null) {
pre.left = cur.right; //cur就是最左邊的節點，pre的cur的父節點，父節點的left指向cur的right
cur.right = head; //cur的right指向head這個根結點
}
return cur; //回傳最左邊的節點
}
//遞回版本
public void remove2(int val) {
if (root == null) {
throw new RuntimeException("root is null.");
}
process2(val, root);
}
private TreeNode process2(int val, TreeNode node) {
if (node == null) {
return null;
}
if (val < node.val) { //小于
node.left = process2(val, node.left);
} else if (val > node.val){ //大于
node.right = process2(val, node.right);
} else if (node.left != null && node.right != null) { //上面的if沒成立，說明val相等，這里是兩個孩子節點的情況
node.val = getMinNodeVal(node.right); //覆寫右子樹中最小的節點值
node.right = process2(node.val, node.right); // 重新對已經覆寫的數值進行洗掉
} else { //只有一個孩子節點或者沒有節點的情況
node = node.left != null? node.left : node.right;
}
return node;
}
private int getMinNodeVal(TreeNode node) {
TreeNode pre = null;
TreeNode cur = node;
while (cur != null) {
pre = cur;
cur = cur.left;
}
return pre.val;
}
遞回版本的洗掉，只是將右子樹最小節點的值，賦值給了cur，然后遞回呼叫去洗掉右子樹上最小值的節點，
最后一個contains方法就簡單了，遍歷整顆二叉樹，找到了val就回傳true，否則回傳false，
public boolean contains(int val) {
TreeNode cur = root;
while (cur != null) {
if (cur.val == val) {
return true;
} else if (val < cur.val) {
cur = cur.left;
} else {
cur = cur.right;
}
}
return false;
}
最后自己再寫一個中序遍歷的方法，看看自己寫的代碼是否正確了呢，切記：搜索二叉樹中序遍歷的結果，一定是一個升序的，不知道怎么寫遍歷方法的，可以看一下前期文章：二叉樹的三種非遞回遍歷方式，
好啦，本期文章就到此結束啦，我們下期見！！！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/295407.html
標籤：其他