java手写BST

今天药忘吃喽~ 2022-05-09 05:06 138阅读 0赞

难易程度：★★★

重要性：★★★★★

今日头条的面试中有过要求：手写实现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;
                } else
                    break;
            }
    
            // 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);
            else
                return 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**、**python**、**爬虫**、**大数据**等技术，和**海量资料分享**：  
公众号**`菜鸟名企梦`**后台发送“**csdn**”即可免费领取【csdn】和【百度文库】下载服务；  
公众号**`菜鸟名企梦`**后台发送“**资料**”:即可领取**5T精品学习资料**、**java面试考点**和**java面经总结**，以及**几十个java、大数据项目**，**资料很全，你想找的几乎都有**

![扫码关注，及时获取更多精彩内容。（博主今日头条大数据工程师）][1240]

扫码关注，及时获取更多精彩内容。（博主今日头条大数据工程师）

[1240]: /images/20220509/a9b0245fa41944d8954c59a70a5eedff.png