摘要:本文專門針對笨蛋介紹如何編寫二叉樹,包括二叉樹的結構如何添加節點如何刪除節點。二叉樹的結構有三個要點每個節點最多有兩個子節點,分別稱作左子節點和右子節點。通過這種生長方式,我們無論何時都能得到滿足前面三個要素的二叉樹。
本文專門針對笨蛋介紹如何編寫二叉樹,包括二叉樹的結構、如何添加節點、如何刪除節點。
首先介紹二叉樹的結構。
二叉樹的結構有三個要點:
每個節點最多有兩個子節點,分別稱作左子節點和右子節點。
每個節點的左子節點的值比它小,右子節點的值比它大。
每個節點的左子樹每個節點的值都比它小,右子樹每個節點的值都比它大。
看上面這個例子,就完全符合這三點。
這時候笨蛋就會問了:前面兩點我理解,但是第三點是怎么做到的?
所以接下來介紹下二叉樹是如何 “生長” 起來的:
如上圖所示,當加入一個新節點時,從根節點開始對它進行比較。如果它比根節點小,則放入根節點的左子樹,如果比根節點大,則放入根節點的右子樹。
然后再進行下一級節點的比較,直到遇到最后一級節點,才將新節點加入為該節點的左或右子節點。
以第四幅圖的節點 25 為例,它第一次會與根節點 10 比較,結果就是 25 應該放入 10 的右子樹,這就排除了它放入左子樹的可能,即 25 不可能放到 4 的下面。
然后 25 再和節點 33 比較,結果是它比較小,所以應該放入 33 的左子樹。因為 33 沒有左子節點,那么 25 就直接作為 33 的左子節點了。
通過這種生長方式,我們無論何時都能得到滿足前面三個要素的二叉樹。
那么寫代碼該如何實現呢?所謂慢工出細活,我們一步一步來。
首先我們創建二叉樹節點的基本結構。每個二叉樹都有四個成員,如下所示。
public class BasicBTree { public int value; // 節點的值 public BasicBTree left; // 節點的左子節點 public BasicBTree right; // 節點的右子節點 public BasicBTree parent; // 節點的父節點。如果為 null 則表示該節點是根節點 // 構造方法 public BasicBTree(int value) { this.value = value; } }
回頭看第一張圖,你會發現每個節點最多有三根線連著,上面的線就代表 BasicBTree 的 parent,下面兩根線就分別代表 left 和 right 了。而節點中的數字就是 BasicBTree 的 value。
接下來我們要為 BasicBTree 編寫兩個簡單的方法,用來給它添加左子節點和右子節點:
// 將一個節點加為當前節點的左子節點 public void setLeft(BasicBTree node) { if (this.left != null) { this.left.parent = null; // 解除當前的左子節點 } this.left = node; if (this.left != null) { this.left.parent = this; // 設置新子節點的父節點為自身 } } // 將一個節點加為當前節點的右子節點 public void setRight(BasicBTree node) { if (this.right != null) { this.right.parent = null; // 解除當前的右子節點 } this.right = node; if (this.right != null) { this.right.parent = this; // 設置新子節點的父節點為自身 } }
在上面兩個方法的基礎上,我們可以添加一個添加任意值節點的方法:
// 將一個節點加為當前節點的左或右子節點 public void setChild(BasicBTree node) { if (node == null) { return; } if (node.value < this.value) { setLeft(node); } else if (node.value > this.value) { setRight(node); } }
另外我們再添加一個刪除左子節點或右子節點的方法:
// 刪除當前節點的一個直接子節點 public void deleteChild(BasicBTree node) { if (node == null) { return; } if (node == this.left) { node.parent = null; this.left = null; } else if (node == right) { node.parent = null; this.right = null; } }
這幾個方法都是非常簡單的,其中 setChild() 和 deleteChild() 這兩個方法,我們后面介紹刪除節點的時候會用到。
現在我們正式實現構造樹的方法,就是把一個一個數字加到樹里面去,讓樹越長越大的方法:
// 向當前節點下面的樹中添加一個值作為新節點 public void add(int value) { if (value < this.value) { // 表示應該放入左子樹 if (this.left == null) { // 如果左子樹為空則構建一個節點加進去 setLeft(new BasicBTree(value)); } else { this.left.add(value); // 否則對左子樹同樣調用 add 方法(即遞歸) } } else if (value > this.value) { // 表示應該放入右子樹 if (this.right == null) { // 如果右子樹為空則構建一個節點加進去 setRight(new BasicBTree(value)); } else { this.right.add(value); // 否則對右子樹同樣調用 add 方法(即遞歸) } } }
這個方法稍微復雜一些,主要是因為邏輯上使用了遞歸。這個方法怎么用呢?以最開始的樹為例,演示如何長成這棵樹:
public static void main(String[] args) { // 根節點 BasicBTree tree = new BasicBTree(10); // 第一層子節點 tree.add(4); tree.add(33); // 第二層子節點 tree.add(25); tree.add(46); tree.add(8); tree.add(1); }
你可能會注意到,加入每一層的子節點時,層內節點的添加順序可以任意調換,構造出來的樹都是一樣的;但是如果將不同層的節點順序互換,構造出來的二叉樹就會變樣了。這當中的原因可以自己想想。
最后來介紹二叉樹中最復雜的操作:刪除節點。為什么這個操作最復雜呢?因為刪除一個節點之后,要把它下面的節點接上來,同時要保持這棵樹繼續滿足三要素。
如何把下面的節點接上來呢?最笨的方法當然是把被刪節點的所有子節點一個個重新往樹里面加。但是這樣做效率實在不高。想想如果被刪節點有上百萬個子節點,那操作步驟就太多了(如下圖所示)。
怎么做才能效率高呢?有一個辦法,就是從被刪節點的子節點中找到一個合適的,替換掉被刪節點。這樣做的步驟就少得多了。
不過這樣的節點是否存在呢?答案是,除非被刪節點沒有子節點,否則是一定存在的。
而且這樣的節點可能不止一個。原則上講,被刪節點的左子樹的最大值,或右子樹的最小值,都是滿足條件的,都可以用來替換被刪節點。比如說,將左子樹的最大值節點替換上去之后,左子樹的剩余節點的值都仍然小于該位置的節點。下面是一個例子:
比如要刪除節點 33,而該節點左子樹的最大值為 31,那么直接將 31 替換到 33 的位置即可,整棵樹仍然滿足三要素。
同理,被刪節點右子樹的最小值也可以用來替換被刪節點。比如上圖中 33 節點的右子節點 46 也可以用來替換 33,整棵樹仍然滿足三要素。
所以這個問題就轉化為:如何尋找被刪節點的左子樹的最大值和右子樹的最小值。顯然,因為二叉樹所有的左節點都比較小,右節點都比較大,所以要找最大值,順著右節點找即可;要找最小值,順著左節點找即可。下面是實現的代碼:
// 搜索當前節點左子樹中的最大值節點,如果沒有左子節點則返回 null public BasicBTree leftMax() { if (this.left == null) { return null; } BasicBTree result = this.left; // 起始節點 while (result.right != null) { // 順著右節點找 result = result.right; } return result; } // 搜索當前節點右子樹中的最小值節點,如果沒有右子節點則返回 null public BasicBTree rightMin() { if (this.right == null) { return null; } BasicBTree result = this.right; // 起始節點 while (result.left != null) { // 順著左節點找 result = result.left; } return result; }
我們還剩下兩個準備工作,第一個是實現節點的查找:
// 查詢指定值的節點,如果找不到則返回 null public BasicBTree find(int value) { BasicBTree result = this; // 起始節點 if (result.value == value) { return result; } while (result.left != null || result.right != null) { // 如果查找的值比當前節點小則順著左子樹查找; // 如果比當前節點大則順著右子樹查找。 if (value < result.value && result.left != null) { result = result.left; } else if (value > result.value && result.right != null) { result = result.right; } if (result.value == value) { return result; } } return null; }
第二個是實現節點的替換:
// 將節點 node 替換為節點 replace public BasicBTree replace(BasicBTree node, BasicBTree replace) { // 1. replace 接管 node 的子節點 replace.setLeft(node.left); replace.setRight(node.right); // 2. replace 從原來的 parent 脫離 if (replace.parent != null) { replace.parent.deleteChild(replace); } // 3. node 原來的 parent 接管 replace if (node.parent != null) { node.parent.setChild(replace); } // 注意 2 必須在 3 之前,1 位置不論 return replace; }
注意這里用到了之前的 setChild() 和 deleteChild() 兩個方法。而 replace() 方法之所以設計為返回 replace 參數,是為了使用方便。
最后我們就可以正式實現二叉樹刪除節點的方法了:
// 從樹的子節點中刪除指定的值,并重組剩余節點 public BasicBTree delete(int value) { BasicBTree node = find(value); if (node == null) { return this; } // 沒有子節點,直接刪除即可 if (node.left == null && node.right == null) { if (node.parent != null) { node.parent.deleteChild(node); return this; } else { // 表示整棵樹唯一的根節點刪了,只能返回 null return null; } } // 如果有子節點,則取左子樹的最大值或者右子樹的最小值都可以, // 來取代該節點。這里優先取左子樹的最大值 BasicBTree replace; if (node.left != null) { replace = replace(node, node.leftMax()); } else { replace = replace(node, node.rightMin()); } // 如果被刪除的是根節點,則返回用于替換的節點,否則還是返回根節點 return node == this ? replace : this; }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/71034.html
摘要:是棧,它繼承于。滿二叉樹除了葉結點外每一個結點都有左右子葉且葉子結點都處在最底層的二叉樹。沒有鍵值相等的節點。這是數據庫選用樹的最主要原因。 在我們學習Java的時候,很多人會面臨我不知道繼續學什么或者面試會問什么的尷尬情況(我本人之前就很迷茫)。所以,我決定通過這個開源平臺來幫助一些有需要的人,通過下面的內容,你會掌握系統的Java學習以及面試的相關知識。本來是想通過Gitbook的...
摘要:當集合為空時,稱該二叉樹為空二叉樹。也就是說,如果一個二叉樹的層數為,且結點總數是,則它就是滿二叉樹。完全二叉樹完全二叉樹是效率很高的數據結構,完全二叉樹是由滿二叉樹而引出來的。 ...
摘要:正如我標題所說,簡歷被拒。看了我簡歷之后說頭條競爭激烈,我背景不夠,點到為止。。三準備面試其實從三月份投遞簡歷開始準備面試到四月份收,也不過個月的時間,但這都是建立在我過去一年的積累啊。 本文是 無精瘋 同學投稿的面試經歷 關注微信公眾號:進擊的java程序員K,即可獲取最新BAT面試資料一份 在此感謝 無精瘋 同學的分享 目錄: 印象中的頭條 面試背景 準備面試 ...
摘要:正如我標題所說,簡歷被拒。看了我簡歷之后說頭條競爭激烈,我背景不夠,點到為止。。三準備面試其實從三月份投遞簡歷開始準備面試到四月份收,也不過個月的時間,但這都是建立在我過去一年的積累啊。 本文是 無精瘋 同學投稿的面試經歷 關注微信公眾號:進擊的java程序員K,即可獲取最新BAT面試資料一份 在此感謝 無精瘋 同學的分享目錄:印象中的頭條面試背景準備面試頭條一面(Java+項目)頭條...
閱讀 3278·2023-04-26 00:57
閱讀 600·2021-10-08 10:05
閱讀 1345·2021-09-08 09:36
閱讀 4147·2021-08-12 13:31
閱讀 2542·2019-08-30 15:55
閱讀 2237·2019-08-30 15:55
閱讀 1013·2019-08-30 15:55
閱讀 2684·2019-08-29 13:17