BST树Java实现

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了BST树Java实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2413字，纯文字阅读大概需要4分钟。

内容图文

package com.app.main.datastructure;

/**
 * BST 树 实现
 * Created with IDEA
 * author:Dingsheng Huang
 * Date:2019/8/19
 * Time:下午7:22
 */
public class BstTree {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        // construct
        TreeNode(int val) {
            this.val = val;
        }
    }

    TreeNode root;

    // insert
    public void  insertIntoBST(int val) {
        root = insertIntoBST(root, val);
    }

    private TreeNode insertIntoBST(TreeNode root, int val) {
        // 如果根节点为空，将新插入节点作为根节点
        if (root == null) {
            root = new TreeNode(val);
        }

        // 根节点不为空
        // 待插入值比根节点小，插入左子树. 注意理解“根节点”是一个上下文环境的相对概念
        if (val < root.val) {
            root.left = insertIntoBST(root.left, val);
        } else if (val > root.val) {
            root.right = insertIntoBST(root.right, val);
        }
        return root;
    }

    // delete
    public void deleteNode(int val) {
        root = deleteNode(root, val);
    }

    // delete 考虑不同分支情况， 删除操作也需要自顶向下遍历查找到待删除节点位置
    // 0. 待删除节点为根节点
    // 1. 待删除节点无左孩子，用右孩子替代删除节点
    // 2. 待删除节点无右孩子，用左孩子替代删除节点
    // 3. 待删除节点既有右孩子又有左孩子，找到右子树的最小值替换待删除节点，然后删除右子树最小值
    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 {
            if (curNode.left == null) {
                return curNode.right;
            } else if (curNode.right == null) {
                return curNode.left;
            }

            TreeNode minNode = findMin(curNode.right);
            curNode.val = minNode.val;
            curNode.right =  deleteNode(curNode.right, curNode.val);

        }
        return curNode;
    }

    private TreeNode findMin(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    // search
    public int searchBST(int val) {
        TreeNode target = searchBST(root, val);
        return target == null ? -1 : target.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);
        }
    }




    // test
    public static void main (String[] args) {
        BstTree bstTree = new BstTree();
        bstTree.insertIntoBST(5);
        bstTree.insertIntoBST(1);
        bstTree.insertIntoBST(2);
        bstTree.insertIntoBST(3);
        System.out.println(bstTree.searchBST(3));
        System.out.println(bstTree.searchBST(9));
        bstTree.deleteNode(3);
        bstTree.insertIntoBST(9);
        System.out.println(bstTree.searchBST(3));
        System.out.println(bstTree.searchBST(9));
    }
}

内容总结

以上是互联网集市为您收集整理的BST树Java实现全部内容，希望文章能够帮你解决BST树Java实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端