難易程度：★★★

重要性：★★★★★

今日頭條的面試中有過要求：手寫實現BST

import java.util.*;public class MyBSTImpl {// BST中的節點TreeNode root;static class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}}// 插入操作public void insertIntoBST(int val) {root = insertIntoBST(root, val);}private TreeNode insertIntoBST(TreeNode root, int val) {if (root == null) {root = new TreeNode(val);return root;}if (val < root.val)root.left = insertIntoBST(root.left, val);else if (val > root.val)root.right = insertIntoBST(root.right, val);return root;}/** 待刪除節點可能有四種情況：* 1.待刪除節點：沒有左孩子也沒有右孩子，刪除節點后return null即可* 2.待刪除節點：只有左孩子，刪除節點后return 該節點的左子樹即可* 3.待刪除節點：只有右孩子，刪除節點后return 該節點的右子樹即可* 4.待刪除節點：左孩子和右孩子都不為null：用待刪除節點的右子樹中最小的節點值，* 也就是用待刪除節點的右子樹最左端的節點值替換待刪除節點的值，然后刪除待刪除節點的右子樹最左端的節點即可* （該節點沒有左孩子），因為是最左端節點。*/public void deleteNode(int val) {root = deleteNode(root, val);}private TreeNode deleteNode(TreeNode curNode, int key) {if (curNode == null) {return null;}if (key < curNode.val) {curNode.left = deleteNode(curNode.left, key);} else if (key > curNode.val) {curNode.right = deleteNode(curNode.right, key);} else {// curNode為帶輸出節點if (curNode.left == null) {// 待刪除節點只有右孩子或者沒有孩子節點return curNode.right;} else if (curNode.right == null) {// 待刪除節點只有左孩子return curNode.left;}// 左右孩子都有// 找到待刪除節點右子樹中最left的節點，也就是右子樹中值最小的節點TreeNode minNode = findMin(curNode.right);curNode.val = minNode.val;// 更新curNode的值為待刪除節點右子樹中值最小的節點的值// 刪除curNode右子樹中值最left的節點curNode.right = deleteNode(curNode.right, curNode.val);}return curNode;}// 找到以node為根節點的所有節點中值最小的節點，也就是最左端的節點private TreeNode findMin(TreeNode node) {while (node.left != null) {node = node.left;}return node;}// 迭代的方式刪除private TreeNode deleteNode1(TreeNode root, int key) {TreeNode cur = root;TreeNode pre = null;while (cur != null) {pre = cur;if (key < cur.val) {cur = cur.left;} else if (key > cur.val) {cur = cur.right;} elsebreak;}// cur指向待刪除節點if (cur == null)return null;// 沒找到待刪除節點if (pre == null) {// 刪除根節點root = deleteRootNode(cur);} else if (pre.left == cur) {// 刪除左節點pre.left = deleteRootNode(cur);} else {// 刪除有節點pre.right = deleteRootNode(cur);}return root;}private TreeNode deleteRootNode(TreeNode root) {if (root == null) {return null;}if (root.left == null) {return root.right;}if (root.right == null) {return root.left;}TreeNode next = root.right;TreeNode pre = root;// next指向待刪除節點的右分支最小節點// pre指向next的父節點for (; next.left != null; pre = next, next = next.left);next.left = root.left;if (root.right != next) {// 不是要刪除next節點本身pre.left = next.right;next.right = root.right;}return next;}//查找操作public int searchBST(int val) {TreeNode search = searchBST(root, val);return search == null ? -1 : search.val;}// 遞歸查找private TreeNode searchBST(TreeNode root, int val) {if (root == null || root.val == val)return root;if (val > root.val)return searchBST(root.right, val);elsereturn searchBST(root.left, val);}// 迭代查找private TreeNode searchBST1(TreeNode root, int val) {if (root == null) {return null;}while (true) {if (root.val == val) {return root;} else if (root.val < val) {root = root.right;} else {root = root.left;}if (root == null) {return null;}}} } 復制代碼

推薦閱讀

java學習筆記、10T資料、100多個java項目分享

---

掃描下方二維碼，及時獲取更多互聯網求職面經、java、python、爬蟲、大數據等技術，和海量資料分享： 公眾號**菜鳥名企夢后臺發送“csdn”即可免費領取【csdn】和【百度文庫】下載服務； 公眾號菜鳥名企夢后臺發送“資料”:即可領取5T精品學習資料**、java面試考點和java面經總結，以及幾十個java、大數據項目，資料很全，你想找的幾乎都有

轉載于:https://juejin.im/post/5cbd75d7f265da03b8584f31

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的java手写实现BST的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。