溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇內容介紹了“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;
}“Java中關于二叉樹的概念介紹”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
