學習地址：【數(shù)據(jù)結(jié)構(gòu)與算法基礎-java版】? ? ? ? ? ? ? ? ??🚀數(shù)據(jù)結(jié)構(gòu)--Java專欄🚀

• 筆記01【01-09】【概述、數(shù)組基本使用】【源碼、課件】
• 筆記02【10-18】【棧、隊列、單鏈表(增刪節(jié)點)、循環(huán)鏈表、雙向循環(huán)鏈表、遞歸(斐波那契、漢諾塔)】
• 筆記03【19-27】【（時間、空間復雜度）；八大排序（冒泡、快速、插入、希爾、選擇、歸并、基數(shù)、隊列基數(shù)）】
• 筆記04【28-33】【樹結(jié)構(gòu)(二叉樹)概述、創(chuàng)建、遍歷、查找節(jié)點、刪除節(jié)點】
• 筆記05【34-39】【順序存儲二叉樹概述、二叉樹遍歷、堆排序、線索二叉樹實現(xiàn)及遍歷】
• 筆記06【40-48】【赫夫曼樹、概述、原理分析、代碼實現(xiàn)(數(shù)據(jù)壓縮、創(chuàng)建編碼表、解碼、壓縮文件、解壓文件)】
• 筆記07【49-54】【二叉排序樹（添加、查找、刪除節(jié)點）】
• 筆記08【55-57】【二叉平衡樹(AVL)-概述、單旋轉(zhuǎn)、雙旋轉(zhuǎn)】
• 筆記09【58-60】【計算機中數(shù)據(jù)的存儲原理、2-3樹的插入原理、B樹和B+樹】
• 筆記10【61-63】【哈希表概述、散列函數(shù)的設計、散列沖突解決方案】
• 筆記11【64-67】【圖結(jié)構(gòu)概述、圖遍歷原理(BFS\DFS)、圖遍歷代碼實現(xiàn)】

目? ?錄

P49 4.22 二叉排序樹的概述

P50 4.23 創(chuàng)建二叉排序樹&添加節(jié)點

P51 4.24 二叉排序樹中查找節(jié)點

P52 4.25 刪除葉子節(jié)點

P53 4.26 刪除只有一顆子樹的節(jié)點

P54 4.27 刪除有兩顆子樹的節(jié)點

代碼匯總

1、Node.java

2、BinarySortTree.java

3、TestBinarySortTree.java

---

P49 4.22 二叉排序樹的概述

BinarySortTree：插入（創(chuàng)建節(jié)點、直接插入）、查找性能較好！

P50 4.23 創(chuàng)建二叉排序樹&添加節(jié)點

P51 4.24 二叉排序樹中查找節(jié)點

P52 4.25 刪除葉子節(jié)點

能在Tree里實現(xiàn)的都在樹里，需要考慮左右節(jié)點的才會寫入Node中。

P53 4.26 刪除只有一顆子樹的節(jié)點

P54 4.27 刪除有兩顆子樹的節(jié)點

代碼匯總

1、Node.java

package demo11;public class Node {int value;Node left;Node right;public Node(int value) {this.value = value;}/*** 向子樹中添加節(jié)點* * @param node*/public void add(Node node) {if (node == null) {return;}// 判斷傳入的節(jié)點的值比當前子樹的根節(jié)點的值大還是小// 添加的節(jié)點比當前節(jié)點的值更小if (node.value < this.value) {// 如果左節(jié)點為空if (this.left == null) {this.left = node;// 如果不為空} else {this.left.add(node);}} else {if (this.right == null) {this.right = node;} else {this.right.add(node);}}}/*** 中序遍歷* * @param node*/public void midShow(Node node) {if (node == null) {return;}midShow(node.left);System.out.print(node.value + "、");midShow(node.right);}/*** 查找節(jié)點* * @param value2*/public Node search(int value) {if (this.value == value) {return this;} else if (value < this.value) {if (left == null) {return null;}return left.search(value);} else {if (right == null) {return null;}return right.search(value);}}/*** 搜索父節(jié)點* * @param value* @return*/public Node searchParent(int value) {if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {return this;} else {if (this.value > value && this.left != null) {return this.left.searchParent(value);} else if (this.value < value && this.right != null) {return this.right.searchParent(value);}return null;}} }

2、BinarySortTree.java

package demo11;public class BinarySortTree {Node root;/*** 向二叉排序樹中添加節(jié)點* @param node*/public void add(Node node) {// 如果是一顆空樹if (root == null) {root = node;} else {root.add(node);}}/*** 中序遍歷二叉排序樹，從小到大的順序*/public void midShow() {if (root != null) {root.midShow(root);}}/*** 節(jié)點的查找* * @param value* @return*/public Node search(int value) {if (root == null) {return null;} else {return root.search(value);}}/*** 刪除節(jié)點* * @param value*/public void delete(int value) {if (root == null) {return;} else {// 找到這個節(jié)點Node target = search(value);// 如果沒有這個節(jié)點if (target == null) {return;}// 找到他的父節(jié)點Node parent = searchParent(value);// 要刪除的節(jié)點是葉子節(jié)點if (target.left == null && target.right == null) {// 要刪除的節(jié)點是父節(jié)點的左子節(jié)點if (parent.left.value == value) {parent.left = null;// 要刪除的節(jié)點是父節(jié)點的右子節(jié)點} else {parent.right = null;}// 要刪除的節(jié)點有兩個子節(jié)點的情況} else if (target.left != null && target.right != null) {// 刪除右子樹中值最小的節(jié)點，并獲取到該節(jié)點的值int min = deleteMin(target.right);// 替換目標節(jié)點中的值target.value = min;// 要刪除的節(jié)點有一個左子節(jié)點或右子節(jié)點} else {// 有左子節(jié)點if (target.left != null) {// 要刪除的節(jié)點是父節(jié)點的左子節(jié)點if (parent.left.value == value) {parent.left = target.left;// 要刪除的節(jié)點是父節(jié)點的右子節(jié)點} else {parent.right = target.left;}// 有右子節(jié)點} else {// 要刪除的節(jié)點是父節(jié)點的左子節(jié)點if (parent.left.value == value) {parent.left = target.right;// 要刪除的節(jié)點是父節(jié)點的右子節(jié)點} else {parent.right = target.right;}}}}}/*** 刪除一顆樹中最小的節(jié)點* * @param right* @return*/private int deleteMin(Node node) {Node target = node;// 遞歸向左找while (target.left != null) {target = target.left;}// 刪除最小的這個節(jié)點delete(target.value);return target.value;}/*** 搜索父節(jié)點* * @param value* @return*/public Node searchParent(int value) {if (root == null) {return null;} else {return root.searchParent(value);}} }

3、TestBinarySortTree.java

package demo11;public class TestBinarySortTree {public static void main(String[] args) {int[] arr = new int[] { 7, 3, 10, 12, 5, 1, 9 };// 創(chuàng)建一顆二叉排序樹BinarySortTree bst = new BinarySortTree();// 循環(huán)添加for (int i : arr) {bst.add(new Node(i));} // // 查看樹中的值 // bst.midShow(); // System.out.println("-----"); // // 查找 // Node node = bst.search(10); // System.out.println(node.value); // // Node node2 = bst.search(20); // System.out.println(node2); // //測試查找父節(jié)點 // Node p1 = bst.searchParent(12); // System.out.println(p1.value); // System.out.println("-----"); // //刪除葉子節(jié)點 // bst.delete(5); // bst.midShow(); // System.out.println("==="); // // 刪除只有一個子節(jié)點的節(jié)點 // bst.delete(3);bst.midShow();// 刪除有兩個子節(jié)點的節(jié)點bst.delete(3);System.out.println("----");bst.midShow();}}

嘿嘿嘿~

總結(jié)

以上是生活随笔為你收集整理的数据结构Java07【二叉排序树（添加查找删除-节点）】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。