Java实现二叉排序树

简介: 二叉排序树(Binary Sort Tree)或者是一颗空树;或者是具有如下性质的二叉树:

java实现二叉排序树

二叉排序树(Binary Sort Tree)或者是一颗空树;或者是具有如下性质的二叉树:

(1) 若它的左子树不空,则 左子树上所有结点的值 均小于它的根结点的值;

(2) 若它的右子树不空,则 右子树上所有结点的值 均大于它的根结点的值;
(3) 它的 左、右子树又分别为二叉排序树。

下图中的这颗二叉树就是一颗典型的二叉排序树:

在这里插入图片描述

初始时是 无序序列
在这里插入图片描述
上面构造出的二叉排序树的中序遍历结果.

下面是java的代码实现,具有删除、查询、添加等功能.

//二叉排序树
public class BinarySortTree {

    public static void main(String[] args) {

        int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};
        BinaryTree binaryTree = new BinaryTree();
        for (int i : arr) {
            binaryTree.add(new Node(i));
        }
        binaryTree.infixOrder();

        //删除叶子节点测试
//        System.out.println("~~~~~~~~~~~~~~~~~~~~~~");
//        binaryTree.delNode(2);
//        binaryTree.delNode(7);
//        binaryTree.infixOrder();
    }
}

class BinaryTree {
    private Node root;

    public BinaryTree() {
    }

    public BinaryTree(Node root) {
        this.root = root;
    }

    //查找待删除结点
    public Node sreach(int value) {
        if (root == null) {
            return null;
        } else {
            return root.sreach(value);
        }
    }

    //查找待删除结点的父节点
    public Node sreachParent(int value) {
        if (root == null) {
            return null;
        } else {
            return root.sreachParent(value);
        }
    }

    /**
     * 查找以当前结点为根结点的二叉树的最小值,并删除该结点
     *
     * @param node 需要查找的根节点
     * @return 返回以node为根节点的二叉树的最小值
     */
    public int delRightTreeMin(Node node) {
        Node target = node.right;
        while (target.left != null) {
            target = target.left;
        }
        delNode(target.value);
        return target.value;
    }

    /**
     * 查找当前结点为根节点的二叉树的最大值,并删除该结点
     *
     * @param node 需要查找的二叉树的根节点
     * @return 返回以node为根节点的二叉树的最大值
     */
    public int delLeftTreeMax(Node node) {
        Node target = node.left;
        while (target.left != null) {
            target = target.left;
        }
        delNode(target.value);
        return target.value;
    }

    public void delNode(int value) {
        if (root == null) {
            return;
        }
        Node target = sreach(value);
        Node parent = sreachParent(value);
        if (target != null && parent != null) {
            //判断当前结点是不是叶子结点
            if (target.left == null && target.right == null) {
                if (parent.left != null && parent.left.value == value) {
                    parent.left = null;
                } else if (parent.right != null && parent.right.value == value) {
                    parent.right = null;
                }
            } else if (target.left != null && target.right != null) {
                target.value = delRightTreeMin(target);
            } else {
                if (parent.left != null && parent.left.value == value && target.left != null) {
                    parent.left = target.left;
                } else if (parent.left != null && parent.left.value == value && target.right != null) {
                    parent.left = target.right;
                } else if (parent.right != null && parent.right.value == value && target.right != null) {
                    parent.right = target.right;
                } else if (parent.right != null && parent.right.value == value && target.left != null) {
                    parent.right = target.left;
                }
            }
        } else if (target != null && parent == null) {
            //判断当前结点是不是叶子结点
            if (target.left == null && target.right == null) {
                target = null;
            } else if (target.left != null && target.right != null) {
                target.value = delRightTreeMin(target);
            } else {
                if (target.left != null) {
                    target = target.left;
                } else if (target.right != null) {
                    target = target.right;
                }
            }
        }


    }

    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    public void infixOrder() {
        if (root == null) {
            System.out.println("二叉树为空,中序遍历失败!");
        } else {
            root.infixOrder(root);
        }
    }
}

class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    //查找当前结点
    public Node sreach(int value) {
        if (this.value == value) {
            return this;
        } else {
            if (this.left != null && value < this.value) {
                return this.left.sreach(value);
            } else if (this.right != null && this.value < value) {
                return this.right.sreach(value);
            } else {
                return null;
            }
        }
    }

    //查找当前结点的父节点
    public Node sreachParent(int value) {
        if (this.left == null && this.right == null) {
            return null;
        } else {
            if (this.left != null && this.left.value == value) {
                return this;
            } else if (this.right != null && this.right.value == value) {
                return this;
            } else if (this.left != null && this.value > value) {
                return this.left.sreachParent(value);
            } else if (this.right != null && this.value < value) {
                return this.right.sreachParent(value);
            } else {
                return null;
            }
        }
    }


    //添加结点
    public void add(Node node) {
        if (node == null) {
            return;
        }
        if (node.value < this.value) {
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        } else {
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }
    }

    //中序遍历二叉树
    public void infixOrder(Node root) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            root.left.infixOrder(root.left);
        }
        System.out.println(root);
        if (root.right != null) {
            root.right.infixOrder(root.right);
        }
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
}
目录
相关文章
|
6月前
|
Java
二叉排序树(java)
二叉排序树(java)
|
7月前
|
Java BI
Java 实现二叉排序树(BST)
Java 实现二叉排序树(BST)
53 0
|
Java C语言
面试整理 - 二叉排序树 c语言 及java 例子
面试整理 - 二叉排序树 c语言 及java 例子
|
Java
Java 实现汉字按照首字母分组排序
Java 实现汉字按照首字母分组排序
726 0
二叉搜索树(二叉排序树)—Java(下)
二叉搜索树(二叉排序树)—Java(下)
二叉搜索树(二叉排序树)—Java(上)
二叉搜索树(二叉排序树)—Java(上)
105 0
|
Java 数据安全/隐私保护
JAVA 实现上传图片添加水印(详细版)(上)
JAVA 实现上传图片添加水印(详细版)
1293 0
JAVA 实现上传图片添加水印(详细版)(上)
|
算法 Java
Java开发 - 树(二叉树,二叉排序树,红黑树)(三)
Java开发 - 树(二叉树,二叉排序树,红黑树)
112 0
 Java开发 - 树(二叉树,二叉排序树,红黑树)(三)
|
存储 Java 程序员
Java开发 - 树(二叉树,二叉排序树,红黑树)(一)
Java开发 - 树(二叉树,二叉排序树,红黑树)
152 0
Java开发 - 树(二叉树,二叉排序树,红黑树)(一)
|
网络协议 Java
Java网络编程:UDP/TCP实现实时聊天、上传图片、下载资源等
ip地址的分类: 1、ipv4、ipv6 127.0.0.1:4个字节组成,0-255,42亿;30亿都在北美,亚洲就只有4亿 2011年就用尽了。
Java网络编程:UDP/TCP实现实时聊天、上传图片、下载资源等