溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇內容介紹了“Java中關于二叉樹的概念介紹”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！
一、二叉樹的概念
為什么要使用二叉樹？
樹是什么？
樹的相關術語！
根節(jié)點
路徑
父節(jié)點
子節(jié)點
葉節(jié)點
子樹
訪問
層（深度）
關鍵字
滿二叉樹
完全二叉樹
二叉樹的五大性質
二、搜索二叉樹
插入
刪除
hello, everyone. Long time no see. 本期文章，我們主要講解一下二叉樹的相關概念，順便也把搜索二叉樹（也叫二叉排序樹）講一下。我們直接進入正題吧！GitHub源碼鏈接
為什么要用到樹呢?因為它通常結合了另外兩種數(shù)據(jù)結構的優(yōu)點:一種是有序數(shù)組，另一種是鏈表。在樹中查找數(shù)據(jù)項的速度和在有序數(shù)組中查找一樣快，并且插入數(shù)據(jù)項和刪除數(shù)據(jù)項的速度也和鏈表一樣。下面，我們先來稍微思考一下這些話題，然后再深入地研究樹的細節(jié)。
在有序數(shù)組中插入數(shù)據(jù)太慢了，而在鏈表中查找數(shù)據(jù)也太慢了。所以到后來就有了二叉樹這種數(shù)據(jù)結構。
在深入講解二叉樹前，我們先簡單地認識一下樹這個概念。樹是由若干個節(jié)點和邊組合而成，例如，可以把城市看成節(jié)點，將各個城市之間的交通路線看成邊。當然說的更準確一點，這個例子更應該是屬于圖的范疇內，關于圖的相關知識點。我們到后面再來討論。如下圖，就是一棵樹。
如下圖所示
樹最頂端的節(jié)點稱為根節(jié)點，一棵樹只有一個根節(jié)點，一般也是整棵樹遍歷的開始。
設想一下，從樹中的一個節(jié)點，沿著邊走向另一個節(jié)點，所經過的節(jié)點順序排列就稱為“路徑”。
就像這個名稱一樣，在二叉樹中扮演“父親”的角色， 在二叉樹中的每一個節(jié)點（除了根節(jié)點），都有一個邊向上可以找到該節(jié)點的”父節(jié)點“。
每個節(jié)點都可能有一條或多條邊向下連接其他節(jié)點，下面的這些節(jié)點就稱為它的“子節(jié)點”。
沒有子節(jié)點的節(jié)點稱為“葉子節(jié)點”或簡稱“葉節(jié)點”。樹中只有一個根，但是可以有很多葉節(jié)點。
每個節(jié)點都可以作為“子樹”的根，它和它所有的子節(jié)點，子節(jié)點的子節(jié)點等都含在子樹中。就像家族中那樣，一個節(jié)點的子樹包含它所有的子孫。
當程序控制流程到達某個節(jié)點時，就稱為“訪問”這個節(jié)點，通常是為了在這個節(jié)點處執(zhí)行某種操作，例如查看節(jié)點某個數(shù)據(jù)字段的值或顯示節(jié)點。如果僅僅是在路徑上從某個節(jié)點到另一個節(jié)點時經過了一個節(jié)點，不認為是訪問了這個節(jié)點。
也就相當于我們人一樣，我們這一輩人，就可以看做一層。而爸媽那一輩，又是另外一層。
如圖中所示，每個節(jié)點里，有一個數(shù)值，這個數(shù)值我們就稱為關鍵字。
在一顆二叉樹中，如果所有分支節(jié)點都存在左子樹和右子樹，并且所有的葉節(jié)點都在同一層上，這樣的二叉樹，稱為滿二叉樹。如上圖所示。
對一顆具有n個節(jié)點的二叉樹按從上至下，從左到右的順序編號，如果編號為i(1 <= i <= n)的節(jié)點與同樣深度的滿二叉樹中編號為i的節(jié)點在二叉樹中的位置完全一樣，則這棵樹就被稱為完全二叉樹。
從字面上的意思來看，滿二叉樹一定是完全二叉樹，而完全二叉樹不一定是滿的。如下圖：
1.在二叉樹的第i層上，最多有2（i-1）的次方個節(jié)點。例如：第三層上，最多也就有4個節(jié)點。
2.深度為k的二叉樹，最多有2k的次方 - 1個節(jié)點。 例如：深度為3的二叉樹，最多也就只有7個節(jié)點。
3.對任何一顆二叉樹，葉子節(jié)點的總數(shù)記為n0，度為2的節(jié)點的總數(shù)記為n2。則n0 = n2 + 1。解釋：度為2的節(jié)點，指的是該節(jié)點左右子節(jié)點都有的情況，我們稱為度為2的節(jié)點。那如果左右子節(jié)點，有且僅有一個的時候，我們就叫度為1的節(jié)點。
4.具有n個節(jié)點的完全二叉樹的深度為 log2n + 1。（此處的對數(shù) 向下取整）
由滿二叉樹的定義我們可以知道，深度為k的 滿二叉樹的節(jié)點數(shù)n一定等于 2k的次方 - 1。因為這是最多的節(jié)點數(shù)，再由這個公式，我們就可以倒推出
k = log2(n + 1)。比如節(jié)點數(shù)為8的滿二叉樹，深度就是3。
5.如果對一顆有n個節(jié)點的完全二叉樹的節(jié)點，按照從上至下，從左到右，對每一個節(jié)點進行編號：則有如下性質：
1). 如果i=1，則該節(jié)點就是這棵樹的根結點。若i不等于1，則i節(jié)點的父節(jié)點就是i / 2節(jié)點。
2). 如果2i > n，(n為整棵樹的總節(jié)點數(shù))，則i節(jié)點沒有左子節(jié)點，反之就是2i就是左子節(jié)點。
3). 如果2i + 1 > n，(n為整棵樹的總節(jié)點數(shù))，則i節(jié)點沒有右子節(jié)點，反之就是2i + 1就是右子節(jié)點。
上面我們講解完了二叉樹的一些基本的概念，現(xiàn)在我們繼續(xù)來看下一個知識點：搜索二叉樹。
定義：一個節(jié)點的左子節(jié)點的關鍵字值小于這個節(jié)點，右子節(jié)點的關鍵字值大于或等于這個父節(jié)點。如下圖，就是一個搜索二叉樹。
可能會有同學已經發(fā)現(xiàn)了一個規(guī)律，那就是搜索二叉樹的中序遍歷的結果就是一個升序的。所以在判斷一顆樹是不是搜索二叉樹時，就可以從這里入手。
知道了定義，我們就可以根據(jù)定義來實現(xiàn)相應的代碼。
節(jié)點結構
class TreeNode {
int val; //關鍵字
TreeNode left; //左子節(jié)點
TreeNode right; //右子節(jié)點
public TreeNode(int val) {
this.val = val;
}
}搜索二叉樹的整體框架結構
public class BST {
private TreeNode root; //根結點
public void insert(int val) { //插入新的節(jié)點
}
public void remove(int val) { //刪除對應的節(jié)點
}
public boolean contains(int val) { //查詢是否有該值
}
}我們就一個一個的講解每一方法具體的實現(xiàn)：
插入新的節(jié)點，這個算是比較簡單的。我們拿到依次比較當前節(jié)點的值和傳遞進來的形參值，如果形參值更小一點，我們就往左子樹上做遞歸，繼續(xù)這個操作即可。
//遞歸解法
public void insert(int val) {
root = process(val, root);
}
private TreeNode process(int val, TreeNode node) {
if (node == null) { //如果當前節(jié)點為null，說明已經走到頭了，此時創(chuàng)建節(jié)點，返回即可
return new TreeNode(val);
}
if (val < node.val) { //小于當前節(jié)點
node.left = process(val, node.left);
} else {
node.right = process(val, node.right); //大于等于當前節(jié)點
}
return node;
}//非遞歸解法
public void insert(int val) {
TreeNode node = new TreeNode(val); //先創(chuàng)建好節(jié)點
TreeNode parent = null; //父節(jié)點，用于連接新的節(jié)點
TreeNode cur = root; //當前移動的節(jié)點
if (root == null) {
root = node; //還沒有根結點的情況
} else {
while (true) {
parent = cur;
if (val < cur.val) { //小于當前節(jié)點的情況
cur = cur.left;
if (cur == null) { //如果為null了，說明走到了最后的節(jié)點
parent.left = node;
return;
}
} else { //大于當前節(jié)點的情況
cur = cur.right;
if (cur == null) {
parent.right = node; //如果為null，就走到最后節(jié)點了
return;
}
}
}
}
}遞歸與非遞歸的解法，差異只是在于空間復雜度。當整棵樹很大時，遞歸去調用，就會耗費大量的棧空間。而非遞歸的解法，只是耗費了幾個引用的空間。
刪除是一個比較難的點，刪除之后，還需要保持搜索二叉樹的結構。所以我們需要分為三種情況：
被刪除節(jié)點是葉節(jié)點。
被刪除節(jié)點只有一個孩子節(jié)點。
被刪除節(jié)點有兩個孩子節(jié)點。
我們需要循環(huán)遍歷這顆樹，找到需要被刪除的節(jié)點，并且在遍歷的過程中，還需要記錄被刪除節(jié)點的父節(jié)點是誰，以及被刪除節(jié)點是父節(jié)點的左孩子還是右孩子。所以循環(huán)時，有三個變量，分別是parent、cur和isLeftChild。
在找到需要被刪除的節(jié)點后。再對這個節(jié)點進行判斷，看這個節(jié)點是葉節(jié)點？還是只有一個孩子節(jié)點？又或者是有兩個孩子節(jié)點的情況。
如果是葉節(jié)點，parent的left（或者是right）置為null
如果只有一個節(jié)點，我們就需要繞過cur節(jié)點，直接連接cur的left或者right
如果是有兩個節(jié)點，我們就需要找到cur的后繼節(jié)點。也就是cur的右子樹中，最小的節(jié)點。
其次我們還需要判斷被刪除的節(jié)點，是不是root根結點？如果是，就需要更換根結點。
非遞歸版本大致框架：
//非遞歸版本
public boolean remove(int val) { //刪除對應的節(jié)點
if (root == null) {
throw new RuntimeException("root is null.");
}
TreeNode parent = root;
TreeNode cur = root;
boolean isLeftChild = true;
while (cur != null && cur.val != val) { //循環(huán)查找需要被刪除的節(jié)點
parent = cur;
if (val < cur.val) {
cur = cur.left;
isLeftChild = true;
} else {
cur = cur.right;
isLeftChild = false;
}
}
if (cur == null) { //沒找到需要刪除的節(jié)點
return false;
}
//找到了需要被刪除的節(jié)點
if ( cur.left== null && cur.right == null) { //葉節(jié)點的情況
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) { //只有一個孩子節(jié)點的情況
if (cur == root) {
root = root.right;
} else if (isLeftChild) {
parent.left = cur.right;
} else {
parent.right = cur.right;
}
} else { //有兩個孩子節(jié)點的情況
TreeNode minNode = findMinNode(cur.right);
if (cur == root) {
root = minNode;
} else if (isLeftChild) {
parent.left = minNode;
} else {
parent.right = minNode;
}
minNode.left = cur.left; //新節(jié)點minNode的左孩子指向被刪除節(jié)點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; //一直尋找該樹的最左的節(jié)點
}
if (pre != null) {
pre.left = cur.right; //cur就是最左邊的節(jié)點，pre的cur的父節(jié)點。父節(jié)點的left指向cur的right
cur.right = head; //cur的right指向head這個根結點
}
return cur; //返回最左邊的節(jié)點
}//遞歸版本
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相等。這里是兩個孩子節(jié)點的情況
node.val = getMinNodeVal(node.right); //覆蓋右子樹中最小的節(jié)點值
node.right = process2(node.val, node.right); // 重新對已經覆蓋的數(shù)值進行刪除
} else { //只有一個孩子節(jié)點或者沒有節(jié)點的情況
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;
}遞歸版本的刪除，只是將右子樹最小節(jié)點的值，賦值給了cur，然后遞歸調用去刪除右子樹上最小值的節(jié)點。
最后一個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中關于二叉樹的概念介紹”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！
免責聲明：本站發(fā)布的內容（圖片、視頻和文字）以原創(chuàng)、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關證據(jù)，一經查實，將立刻刪除涉嫌侵權內容。
