二叉树

二叉搜索树

二叉搜索树满足条件：

1. 是一个二叉树。
2. 每个节点则左子节点小于该节点，右子节点大于该节点。

二叉树搜索树的添加节点

例如：4，5，10，2，7，13，8，6，9，11

删除节点

删除一个节点有三种情况：

1. 该节点为叶子节点
   直接删除
2. 该节点只有一个子节点
   该节点子节点替换为该节点。
   
3. 该节点下有左右两个子节点
   取该节点右子节点的最小叶子节点替换该节点。

代码实现二叉搜索树

package tree;

/** * @author zhw * @description * @date 2021-05-21 10:49 */
public class BinarySearchTree {
   
    private TreeNode root;
    //添加
    public void add(int key,String value) {
   
        if (root == null) {
   
            root = new TreeNode(key, value);
            return;
        }
        addOrModifyNode(root,key,value);
    }
    //获取
    public String get(int key){
   
        TreeNode node = getNode(root, key);
        if(node==null){
   
            return null;
        }
        return node.value;
    }
    //移除
    public void remove(int key){
   
        TreeNode node = getNode(root, key);
        if(node==null){
   
            return;
        }
        TreeNode iNode = node;
        if(iNode.right!=null&&iNode.left!=null){
   
            TreeNode n = iNode.right;
            while(n!=null){
   
                iNode = n;
                n = n.left;
            }
        }else if(iNode.right != null){
   
            iNode = iNode.right;
        }else if(iNode.left != null){
   
            iNode = iNode.left;
        }else{
   
            TreeNode parent = node.parent;
            if(parent.key>node.key){
   
                parent.left = null;
            }else {
   
                parent.right = null;
            }
            return;
        }
        iNode.parent.left=null;
        iNode.left = node.left;
        iNode.right = node.right;
        TreeNode parent = node.parent;
        if(parent.key>node.key){
   
            parent.left = iNode;
        }else {
   
            parent.right = iNode;
        }
    }
    private TreeNode getNode(TreeNode node,int key){
   
        //如果key相同则更新
        if(key==node.key){
   
            return node;
        }
        if(key<=node.key){
   
            if(node.left==null){
   
                return null;
            }
            return getNode(node.left,key);
        }else{
   
            if(node.right==null){
   
                return null;
            }
            return getNode(node.right,key);
        }
    }
    private void addOrModifyNode(TreeNode node,int key,String value){
   
        if(key == node.key){
   
            node.value = value;
            return;
        }
        if (key < node.key) {
   
            //左
            if(node.left==null){
   
                TreeNode treeNode = new TreeNode(key, value);
                node.left=treeNode;
                treeNode.parent = node;
            }else{
   
                addOrModifyNode(node.left,key,value);
            }
        } else {
   
            //右
            if(node.right==null){
   
                TreeNode treeNode = new TreeNode(key, value);
                node.right=treeNode;
                treeNode.parent = node;
            }else{
   
                addOrModifyNode(node.right,key,value);
            }
        }
    }
    private class TreeNode{
   
        int key;
        String value;
        TreeNode parent;
        TreeNode left;
        TreeNode right;
        public TreeNode(int key,String value){
   
            this.key = key;
            this.value = value;
        }
    }
}