Arithmetic

java-9.二叉搜索(排序)树

PineappleCat · 3月21日 · 2021年 124次已读

介绍

定义结点

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

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

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

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public Node getLeft() {
        return left;
    }

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

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    //添加
    public boolean addChild(int v) {
        if (v < this.value) {
            if (this.left != null) {
                return this.left.addChild(v);
            } else {
                this.left = new Node(v);
            }
            return true;
        } else if (v > this.value) {
            if (this.right != null) {
                return this.right.addChild(v);
            } else {
                this.right = new Node(v);
            }
            return true;
        }
        return false;
    }

    //遍历 -> 中序遍历
    public void middleList() {
        //左 中 右
        //先判断左边有没有元素
        if (this.left != null) {
            this.left.middleList();
        }
        //根结点
        System.out.print(this.value + " ");
        //先判断右边有没有元素
        if (this.right != null) {
            this.right.middleList();
        }
    }
}

定义管理类

public class BinarySortTree {
    //根结点
    private Node root;
    //个数
    public int size;
    //添加元素
    public void add(int v){
        if (root == null){
            this.root = new Node(v);
            size++;
        }else{
            if (root.addChild(v)) {
                size++;
            }
        }
    }

    public void middleList(){
        root.middleList();
    }
}

测试

public class BinarySortTreeTest {
    public static void main(String[] args) {
        BinarySortTree tree = new BinarySortTree();
        tree.add(10);
        tree.add(8);
        tree.add(15);
        tree.add(3);
        tree.add(9);
        tree.add(20);
        tree.add(13);
        //tree.add(13);
        //中序遍历
        tree.middleList();
        System.out.println();
        System.out.println(tree.size);
    }
}

Click here to view the copyright notice of this site(点击此处查看本站版权声明)
0 条回应

必须 注册 为本站用户, 登录 后才可以发表评论!