Java实现构造二叉排序树_java

文章目录

- 定义
- 特点
- 实现思想
- 实现细节
- - 整体代码实现
  - 测试

上一篇讲到了二叉树的构建以及遍历方式有广度遍历以深度遍历，深度遍历又包括先序遍历、中序遍历以及后序遍历…
☞上一篇链接
这篇主要来介绍什么是二叉排序树，以及如何构建二叉排序树

定义

二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。

特点

这棵二叉树的特点是：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树
（4）不存在键值相等的节点
（5）中序遍历的结果就是按照从小到大的规则排序后的结果

实现思想

1、判断是否为空树
2、如果是空树，则根节点等于插入新节点
3、如果不是，则将根节点设置为父节点，拿着新节点和父节点比较
如果小于父节点数据，则判断父节点是否为叶子结点（叶子结点是没有孩子的节点，即没有左、右节点）
如果是叶子结点，则将该节点插入到父节点的左边
如果不是叶子结点，则更新父节点为原来父节点的左子节点，后重复步骤3
如果大于父节点数据，则判断父节点是否为叶子结点
如果是叶子结点，则将该节点插入到父节点的右边
如果不是叶子结点，则更新父节点为原来父节点的右结点，重复步骤3

实现细节

/**
     * 添加节点
     * */
    public boolean add(Integer data) {
        if (root == null) {
            this.root = new TreeNode(data);
            size++;
            return true;
        } else {
            TreeNode current = root;
            TreeNode finalNode;
            while (current != null) {
                finalNode = current;
                if (data < current.getData()) {
                    if (current.getLeft() == null){
                        finalNode.setLeft(new TreeNode(data));
                        size++;
                        return true;
                    }else {
                        current = current.getLeft();
                    }
                }else {
                    if (current.getRight() == null){
                        finalNode.setRight(new TreeNode(data));
                        size++;
                        return true;
                    }else {
                        current = current.getRight();
                    }
                }
            }
        }
        return false;
    }

老样子，这里放了全部代码，便于大家测试

整体代码实现

public class BinarySortedTree {
    private static int size;
    private static class TreeNode {
        Integer data;
        TreeNode left;
        TreeNode right;

        public TreeNode(Integer data) {
            this.data = data;
        }

        public Integer getData() {
            return data;
        }

        public void setData(Integer data) {
            this.data = data;
        }

        public TreeNode getLeft() {
            return left;
        }

        public void setLeft(TreeNode left) {
            this.left = left;
        }

        public TreeNode getRight() {
            return right;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }
    }
    private TreeNode root;

    public static int getSize() {
        return size;
    }

    public TreeNode getRoot() {
        return root;
    }

    public void setRoot(TreeNode root) {
        this.root = root;
    }

    /**
     * 添加节点
     * */
    public boolean add(Integer data) {
        if (root == null) {
            this.root = new TreeNode(data);
            size++;
            return true;
        } else {
            TreeNode current = root;
            TreeNode finalNode;
            while (current != null) {
                finalNode = current;
                if (data < current.getData()) {
                    if (current.getLeft() == null){
                        finalNode.setLeft(new TreeNode(data));
                        size++;
                        return true;
                    }else {
                        current = current.getLeft();
                    }
                }else {
                    if (current.getRight() == null){
                        finalNode.setRight(new TreeNode(data));
                        size++;
                        return true;
                    }else {
                        current = current.getRight();
                    }
                }
            }
        }
        return false;
    }

    /**
     * 中序遍历
     * */
    public void mid_print(TreeNode root){
        if (root != null) {
            //左
            if(root.getLeft() != null){
                mid_print(root.getLeft());
            }
            //根
            System.out.print(root.getData()+"\t");
            //右
            if(root.getRight() != null){
                mid_print(root.getRight());
            }
        }else {
            System.out.println("当前为空树！");
            return;
        }
    }

}

测试

public class Test {
    public static void main(String[] args) {
        BinarySortedTree tree = new BinarySortedTree();
        tree.add(14);
        tree.add(25);
        tree.add(31);
        tree.add(146);
        tree.add(1);
        tree.add(46);
        tree.mid_print(tree.getRoot());
    }
}