Java中關於二叉樹的概念以及搜索二叉樹詳解
hello, everyone. Long time no see. 本期文章，我們主要講解一下二叉樹的相關概念，順便也把搜索二叉樹（也叫二叉排序樹）講一下。我們直接進入正題吧！GitHub源碼鏈接
一、二叉樹的概念
為什麼要使用二叉樹？
為什麼要用到樹呢?因為它通常結合瞭另外兩種數據結構的優點:一種是有序數組，另一種是鏈表。在樹中查找數據項的速度和在有序數組中查找一樣快，並且插入數據項和刪除數據項的速度也和鏈表一樣。下面，我們先來稍微思考一下這些話題，然後再深入地研究樹的細節。
在有序數組中插入數據太慢瞭，而在鏈表中查找數據也太慢瞭。所以到後來就有瞭二叉樹這種數據結構。
樹是什麼？
在深入講解二叉樹前，我們先簡單地認識一下樹這個概念。樹是由若幹個節點和邊組合而成，例如，可以把城市看成節點，將各個城市之間的交通路線看成邊。當然說的更準確一點，這個例子更應該是屬於圖的范疇內，關於圖的相關知識點。我們到後面再來討論。如下圖，就是一棵樹。
樹的相關術語！
如下圖所示
根節點
樹最頂端的節點稱為根節點，一棵樹隻有一個根節點，一般也是整棵樹遍歷的開始。
路徑
設想一下，從樹中的一個節點，沿著邊走向另一個節點，所經過的節點順序排列就稱為“路徑”。
父節點
就像這個名稱一樣，在二叉樹中扮演“父親”的角色， 在二叉樹中的每一個節點（除瞭根節點），都有一個邊向上可以找到該節點的”父節點“。
子節點
每個節點都可能有一條或多條邊向下連接其他節點，下面的這些節點就稱為它的“子節點”。
葉節點
沒有子節點的節點稱為“葉子節點”或簡稱“葉節點”。樹中隻有一個根，但是可以有很多葉節點。
子樹
每個節點都可以作為“子樹”的根，它和它所有的子節點，子節點的子節點等都含在子樹中。就像傢族中那樣，一個節點的子樹包含它所有的子孫。
訪問
當程序控制流程到達某個節點時，就稱為“訪問”這個節點，通常是為瞭在這個節點處執行某種操作，例如查看節點某個數據字段的值或顯示節點。如果僅僅是在路徑上從某個節點到另一個節點時經過瞭一個節點，不認為是訪問瞭這個節點。
層（深度）
也就相當於我們人一樣，我們這一輩人，就可以看做一層。而爸媽那一輩，又是另外一層。
關鍵字
如圖中所示，每個節點裡，有一個數值，這個數值我們就稱為關鍵字。
滿二叉樹
在一顆二叉樹中，如果所有分支節點都存在左子樹和右子樹，並且所有的葉節點都在同一層上，這樣的二叉樹，稱為滿二叉樹。如上圖所示。
完全二叉樹
對一顆具有n個節點的二叉樹按從上至下，從左到右的順序編號，如果編號為i(1 <= i <= n)的節點與同樣深度的滿二叉樹中編號為i的節點在二叉樹中的位置完全一樣，則這棵樹就被稱為完全二叉樹。
從字面上的意思來看，滿二叉樹一定是完全二叉樹，而完全二叉樹不一定是滿的。如下圖：
二叉樹的五大性質
1.在二叉樹的第i層上，最多有2（i-1）的次方個節點。例如：第三層上，最多也就有4個節點。
2.深度為k的二叉樹，最多有2k的次方 – 1個節點。 例如：深度為3的二叉樹，最多也就隻有7個節點。
3.對任何一顆二叉樹，葉子節點的總數記為n0，度為2的節點的總數記為n2。則n0 = n2 + 1。解釋：度為2的節點，指的是該節點左右子節點都有的情況，我們稱為度為2的節點。那如果左右子節點，有且僅有一個的時候，我們就叫度為1的節點。
4.具有n個節點的完全二叉樹的深度為 log2n + 1。（此處的對數 向下取整）
由滿二叉樹的定義我們可以知道，深度為k的 滿二叉樹的節點數n一定等於 2k的次方 – 1。因為這是最多的節點數，再由這個公式，我們就可以倒推出
k = log2(n + 1)。比如節點數為8的滿二叉樹，深度就是3。
5.如果對一顆有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;
}
最後自己再寫一個中序遍歷的方法，看看自己寫的代碼是否正確瞭呢。切記：搜索二叉樹中序遍歷的結果，一定是一個升序的。不知道怎麼寫遍歷方法的，可以看一下前期文章：通俗易懂講解C語言與Java中二叉樹的三種非遞歸遍歷方式。
好啦，本期文章就到此結束啦，我們下期見！！！
到此這篇關於Java中關於二叉樹的概念以及搜索二叉樹詳解的文章就介紹到這瞭,更多相關Java 二叉樹內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！