二叉排序树BST（Java实现）_随笔

二叉排序树BST（Java实现）

BST的定义
添加节点
- 步骤
- 代码实现
查找节点
- 步骤
- 代码实现
删除节点
- 几种情况分析
- 代码实现
全部代码

BST的定义

英文全称：Binary Sort Tree，它满足以下3个特点：

若它的左子树不为空，则左子树上所有节点的值要均小于根节点的值
若它的右子树不为空，则右子树上所有节点的值要均大于根节点的值
左、右子树也分别是排序二叉树

如下图：
二叉排序树，中序遍历输出结果是有序的

添加节点步骤

先找到添加位置，先让添加的节点和根节点比较大小，依次往下比较。
找到合适位置进行节点插入。

新元素被插入之后一定是个叶子节点，如某个key已存在，那么新值覆盖旧值

代码实现

public void add (int key, String data) {

    
    if (root == null) {
        root = new Node(key, data);
        return;
    }

    
    Node cur = root;    // cur：表示要判断的当前节点。cur从根节点开始判断，因此初始值为root
    Node pre = null;    // pre表示cur的上个节点 也就是父节点
    // 实际上当cur==null时 说明我们已经找到合适的位置了
    while (cur != null) {
        if (key < cur.key) {    // 向左子树寻找
            pre = cur;
            cur = cur.left;
        }else if (key > cur.key) {  // 向右子树寻找
            pre = cur;
            cur = cur.right;
        }else { // key == cur.key  则表示当前key已存在
            cur.data = data;   // 新值覆盖旧值，并返回结束
            return;
        }
    }
    // 循环结束 cur为null则表示已经找到了合适的添加位置

    
    if (key < pre.key)  // 插入到父节点的左边
        pre.left = new Node(key, data);
    else                // 插入到父节点的右边
        pre.right = new Node(key, data);
}

查找节点步骤

1、拿着待查元素和根节点比较；
2、如果比根节点小，继续在左子树中查找；
3、如果比根节点大，继续在右子树中查找；
4、如果当前元素查找到null也没找到，说明该元素不存在。

代码实现

非递归方式：

public Node find(int key) {
    // cur从根节点开始搜索
    Node cur = root;
    while (cur != null) {
        // 如果当前节点的key与搜索的key值相等 则说明找到了，直接返回当前节点
        if (cur.key == key)
            return cur;

        // 下面是当前节点大于key和小于key的情况（向下搜索）
        if (key < cur.key)
            cur = cur.left;
        else {  // key > cur.key
            cur = cur.right;
        }
    }
    // 如果走出循环还没找到 则表示已经找到末尾了还没找到
    return null;
}

递归方式：

public Node dgFind(Node node, int key) {
    // 如果节点为空 则表示已经找到末尾了还没找到
    if (node == null)
        return null;

    // 如果cur.key == key 则表示找到了,直接返回
    if (node.key == key)
        return node;

    // 下面是当前节点大于key和小于key的情况
    if (key < node.key)
        return dgFind(node.left, key);  // 切记这里是return dgFind(xxx, xxx)  不是直接调用dgFind(xxx, xxx)
    else    // key > node.key
        return dgFind(node.right, key);
}

删除节点几种情况分析

非root节点（这种情况下再分三种情况）
- 叶子节点：若删除节点为叶子节点，理论上直接删除即可。但 *** 作上，会找到删除节点的父节点parent，后判断删除节点是parent的左节点还是右节点，最后将parent的左节点或者右节点置null即可
- 只有一棵子树：若删除节点只有一棵子树，那么就找该节点的父节点parent，判断待删除的节点是parent的左节点还是右节点，最后将parent的左节点或者右节点指向待删除节点的子节点。那么待删除节点就会被回收删除了。
- 有两棵子树：若删除节点有两棵子树，即左、右节点都存在。那么只需要从待删除的左子树中找到最大节点（也可以是右子树的最小值，都可以），然后用其替换待删除节点的位置。实际 *** 作：将这个最大节点先备份为temp，然后将这个节点从树中删除。然后将temp的左右指针分别指向root的左右节点、再将parent的左指针或者右指针指向temp
root节点，那么parent就为null（这种情况下再分三种情况）
- 叶子节点：若删除节点为叶子节点。正确 *** 作：直接将root置为null即可
- 只有一棵子树：若删除节点只有一棵子树。正确 *** 作：直接将待删除节点的子节点设置为root节点即可
- 有两棵子树：若删除节点有两棵子树。正确 *** 作：从待删除节点的左子树中找到最大节点（也可以是右子树的最小节点），然后用其替换root节点的位置。实际 *** 作：将这个最大节点先备份为temp，然后将这个节点从树中删除。然后将temp的左右指针分别指向root的左右节点。最后将temp设置为root节点

通过上面描述，我们需要封装两个方法。
找到指定key的父节点的方法：public Node findParent(int key)
找寻指定节点下面的的最大节点的方法：public Node searchMax(Node node)

代码实现

找到指定key父节点的方法：

public Node findParent(int key) {
    // 如果搜索的key是根节点的key 那么直接返回null 因为root没有父节点
    if (key == root.key)
        return null;

    Node cur = root;
    while (cur != null) {
        // 如果左节点不为null 且左节点的key与搜索的key相同 怎直接返回当前节点
        if (cur.left!=null && cur.left.key==key)
            return cur;
        // 与上面类似
        if (cur.right!=null && cur.right.key==key)
            return cur;

        // 向下搜索
        if (key < cur.key)
            cur = cur.left;
        if (key > cur.key)
            cur = cur.right;
    }

    // 如果走出循环还没找到 则表示已经找到末尾了还没找到
    return null;
}

找寻指定节点下面的的最大节点：

public Node searchMax(Node node){
    // 循环找到最大节点(只要右子节点存在，就移入)
    Node target = node;
    while(target.right != null){ // 无需递归
        target = target.right;
    }
    // 已到达最大节点
    return target;
}

删除主要代码：

public boolean delNode(int key) {
    
    // 找到要删除的节点
    Node targetNode = find(key);
    if (targetNode == null)   // 如果node为null  这说明树中不存在指定key的节点，直接返回false
        return false;

    // 找到要删除节点的父节点
    Node parent = findParent(key);
    if (parent != null) {   // parent不为null，则表示删除节点不是root节点
        if (targetNode.left==null && targetNode.right==null) {  // 1、删除节点是叶子节点
            if (parent.left!=null && parent.left.key == targetNode.key) // 待删除节点是父节点的左节点
                parent.left = null;
            else    // 待删除节点是父节点的右节点
                parent.right = null;
        }else if (targetNode.left!=null && targetNode.right!=null) {    // 3、待删除节点有两棵子树
            // 备份一下要替换的节点
            Node maxNode = searchMax(targetNode.left);
            Node temp = new Node(maxNode.key, maxNode.data);
            // 将这个节点从树中删除
            delNode(maxNode.key);
            // temp节点 的左、右指针指向 待删除节点的左、右节点
            temp.left = targetNode.left; temp.right = targetNode.right;
            // 父节点的左指针或者右指针指向temp节点， 备份节点彻底替换掉待删除节点
            if (parent.left!=null && parent.left.key == targetNode.key)
                parent.left = temp;
            else
                parent.right = temp;
        }else {         // 2、待删除节点有一颗子树
            if (parent.left!=null && parent.left.key == targetNode.key) {    // 如果待删除节点是parent的左节点
                if (targetNode.left != null)    // 若待删除节点唯一存在的子树是左子树
                    parent.left = targetNode.left;
                if (targetNode.right != null)   // 若待删除节点唯一存在的子树是右子树
                    parent.left = targetNode.right;
            }else {     // 如果待删除节点是parent的右节点
                if (targetNode.left != null)
                    parent.right = targetNode.left;
                if (targetNode.right != null)
                    parent.right = targetNode.right;
            }
        }
    }else { // parent为null，则表示删除节点是root节点
        if (targetNode.left==null && targetNode.right==null) {
            root = null;
        }else if (targetNode.left!=null && targetNode.right!=null) {
            Node maxNode = searchMax(targetNode.left);
            Node temp = new Node(maxNode.key, maxNode.data);
            delNode(maxNode.key);
            temp.right = targetNode.right; temp.left = targetNode.left;
            // 将这个备份节点设置为root节点
            this.root = temp;
        }else {
            if (targetNode.left != null)
                this.root = targetNode.left;
            else
                this.root = targetNode.right;
        }
    }

    return true;
}

全部代码

public class BinarySortTreeDemo {
    public static void main(String[] args) {
        // 创建一个二叉排序树
        BinarySortTree BST = new BinarySortTree();
        // 并未BST设置一个root节点
        Node root = new Node(0, "root");
        BST.root = root;
        // 手动添加节点
        BST.add(3, "z3"); BST.add(5, "z5"); BST.add(8, "z8");
        BST.add(2, "z2"); BST.add(2, "z22"); BST.add(9, "z9");
        BST.add(7, "z7"); BST.add(66, "z66"); BST.add(52, "z52");
        BST.delNode(66);
        BST.midOrder(BST.root);
    }
}

class Node {
    // key 值用来比较、排序
    public int key;
    public String data;
    public Node left = null;
    public Node right = null;

    public Node(int key, String data) {
        this.key = key;
        this.data = data;
    }

    @Override
    public String toString() {
        return "Node{" +
                "key=" + key +
                ", data='" + data + ''' +
                '}';
    }
}

class BinarySortTree {
    // 二叉排序树的根节点
    public Node root;

    
    public void add (int key, String data) {

        
        if (root == null) {
            root = new Node(key, data);
            return;
        }

        
        Node cur = root;    // cur：表示要判断的当前节点。cur从根节点开始判断，因此初始值为root
        Node pre = null;    // pre表示cur的上个节点 也就是父节点
        // 实际上当cur==null时 说明我们已经找到合适的位置了
        while (cur != null) {
            if (key < cur.key) {    // 向左子树寻找
                pre = cur;
                cur = cur.left;
            }else if (key > cur.key) {  // 向右子树寻找
                pre = cur;
                cur = cur.right;
            }else { // key == cur.key  则表示当前key已存在
                cur.data = data;   // 新值覆盖旧值，并返回结束
                return;
            }
        }
        // 循环结束 cur为null则表示已经找到了合适的添加位置

        
        if (key < pre.key)  // 插入到父节点的左边
            pre.left = new Node(key, data);
        else                // 插入到父节点的右边
            pre.right = new Node(key, data);
    }

    
    public void midOrder(Node node) {
        if (node != null) {
            midOrder(node.left);
            System.out.println("节点的key："+node.key+" 节点的值："+node.data);
            midOrder(node.right);
        }
    }

    
    public Node find(int key) {
        // cur从根节点开始搜索
        Node cur = root;
        while (cur != null) {
            // 如果当前节点的key与搜索的key值相等 则说明找到了，直接返回当前节点
            if (cur.key == key)
                return cur;

            // 下面是当前节点大于key和小于key的情况（向下搜索）
            if (key < cur.key)
                cur = cur.left;
            else {  // key > cur.key
                cur = cur.right;
            }
        }
        // 如果走出循环还没找到 则表示已经找到末尾了还没找到
        return null;
    }

    
    public Node dgFind(Node node, int key) {
        // 如果节点为空 则表示已经找到末尾了还没找到
        if (node == null)
            return null;

        // 如果cur.key == key 则表示找到了,直接返回
        if (node.key == key)
            return node;

        // 下面是当前节点大于key和小于key的情况
        if (key < node.key)
            return dgFind(node.left, key);  // 切记这里是return dgFind(xxx, xxx)  不是直接调用dgFind(xxx, xxx)
        else    // key > node.key
            return dgFind(node.right, key);
    }

    
    public Node findParent(int key) {
        // 如果搜索的key是根节点的key 那么直接返回null 因为root没有父节点
        if (key == root.key)
            return null;

        Node cur = root;
        while (cur != null) {
            // 如果左节点不为null 且左节点的key与搜索的key相同 怎直接返回当前节点
            if (cur.left!=null && cur.left.key==key)
                return cur;
            // 与上面类似
            if (cur.right!=null && cur.right.key==key)
                return cur;

            // 向下搜索
            if (key < cur.key)
                cur = cur.left;
            if (key > cur.key)
                cur = cur.right;
        }

        // 如果走出循环还没找到 则表示已经找到末尾了还没找到
        return null;
    }

    
    public boolean delNode(int key) {
        
        // 找到要删除的节点
        Node targetNode = find(key);
        if (targetNode == null)   // 如果node为null  这说明树中不存在指定key的节点，直接返回false
            return false;

        // 找到要删除节点的父节点
        Node parent = findParent(key);
        if (parent != null) {   // parent不为null，则表示删除节点不是root节点
            if (targetNode.left==null && targetNode.right==null) {  // 1、删除节点是叶子节点
                if (parent.left!=null && parent.left.key == targetNode.key) // 待删除节点是父节点的左节点
                    parent.left = null;
                else    // 待删除节点是父节点的右节点
                    parent.right = null;
            }else if (targetNode.left!=null && targetNode.right!=null) {    // 3、待删除节点有两棵子树
                // 备份一下要替换的节点
                Node maxNode = searchMax(targetNode.left);
                Node temp = new Node(maxNode.key, maxNode.data);
                // 将这个节点从树中删除
                delNode(maxNode.key);
                // temp节点 的左、右指针指向 待删除节点的左、右节点
                temp.left = targetNode.left; temp.right = targetNode.right;
                // 父节点的左指针或者右指针指向temp节点， 备份节点彻底替换掉待删除节点
                if (parent.left!=null && parent.left.key == targetNode.key)
                    parent.left = temp;
                else
                    parent.right = temp;
            }else {         // 2、待删除节点有一颗子树
                if (parent.left!=null && parent.left.key == targetNode.key) {    // 如果待删除节点是parent的左节点
                    if (targetNode.left != null)    // 若待删除节点唯一存在的子树是左子树
                        parent.left = targetNode.left;
                    if (targetNode.right != null)   // 若待删除节点唯一存在的子树是右子树
                        parent.left = targetNode.right;
                }else {     // 如果待删除节点是parent的右节点
                    if (targetNode.left != null)
                        parent.right = targetNode.left;
                    if (targetNode.right != null)
                        parent.right = targetNode.right;
                }
            }
        }else { // parent为null，则表示删除节点是root节点
            if (targetNode.left==null && targetNode.right==null) {
                root = null;
            }else if (targetNode.left!=null && targetNode.right!=null) {
                Node maxNode = searchMax(targetNode.left);
                Node temp = new Node(maxNode.key, maxNode.data);
                delNode(maxNode.key);
                temp.right = targetNode.right; temp.left = targetNode.left;
                // 将这个备份节点设置为root节点
                this.root = temp;
            }else {
                if (targetNode.left != null)
                    this.root = targetNode.left;
                else
                    this.root = targetNode.right;
            }
        }

        return true;
    }

    
    public Node searchMax(Node node){
        // 循环找到最大节点(只要右子节点存在，就移入)
        Node target = node;
        while(target.right != null){ // 无需递归
            target = target.right;
        }
        // 已到达最大节点
        return target;
    }

}

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/zaji/5158195.html

二叉排序树BST（Java实现）

发表评论

评论列表（0条）