用java构造一个二叉搜索树

java树的构造

public class BinearySearchTree<T extends Comparable<T>> { //让T具有可比性
    //树的结点
    private class Node{
        private T ele;    //结点的值
        private Node left,right;    //分别指向左右孩子的索引
        //构造方法
        public Node(T e){
            this.ele=e;
            this.left=this.right=null;
        }
    }

    //树的属性
    private Node root;  //根节点
    private int size;   //树中结点个数

    public BinearySearchTree(){
        this.root=null;
        this.size=0;
    }

    //获取树中结点的个数
    public int getSize(){
        return this.size;
    }

    //向以root为根的二分搜索树中添加元素
    public void add(T e){
        //跟新根节点，因为递归完后根节点的左右孩子可能会有变化
        this.root=addDG(root,e);
        this.size++;
    }

    //向以root为根的二分搜索树中添加元素递归
    private Node addDG(Node root,T e){
        //递归中止的条件
        if(root==null){
            return new Node(e);
        }
        //递归操作
        //待插入元素小于当前节点元素，往左边添加
        if(root.ele.compareTo(e)>0){
            root.left=addDG(root.left,e);
        }else{
            root.right=addDG(root.right, e);
        }
        return root;
    }

    //查询
    public boolean search(T e){
        return searchDG(this.root,e);
    }

    //从以root为根节点的二分搜索树中查询e递归
    private boolean searchDG(Node root,T e){
        //递归中止的条件
        if(root==null){
            return false;
        }
        //递归操作
        if(root.ele.compareTo(e)==0){   //如果相等说明找到了返回true
            return true;
        }else if(root.ele.compareTo(e)>0){  //如果待查找元素小于根节点，就从左孩子处继续找
            return searchDG(root.left,e);
        }else{
            return searchDG(root.right,e);
        }
    }

    //二分搜索树的遍历

    //先序遍历 NLR
    public void preTravel(){
        List<T> list=new ArrayList<>();
        preTravelDG(this.root,list);
        //显示list里的item
        //先把list变成流然后拆箱再对其中的每个元素收藏到一个string里进行显示
        System.out.println(list.stream().map(item->item.toString()+"-->").collect(Collectors.joining()));
    }
    //先序遍历以root为根的树,将结果保存在list中
    private void preTravelDG(Node root,List<T> list){
        //递归中止条件
        if(root==null){
            return;
        }
        //先序遍历按中左右的顺序遍历
        //递归操作:
        //把元素添加到list里
        list.add(root.ele);
        //遍历左
        preTravelDG(root.left,list);
        //遍历右
        preTravelDG(root.right,list);
    }

    //中序遍历 LNR
    public void midTravel(){
        List<T> list=new ArrayList<>();
        midTravelDG(this.root,list);
        //显示list里的item
        //先把list变成流然后拆箱再对其中的每个元素收藏到一个string里进行显示
        System.out.println(list.stream().map(item->item.toString()+"-->").collect(Collectors.joining()));
    }
    //先序遍历以root为根的树,将结果保存在list中
    private void midTravelDG(Node root,List<T> list){
        //递归中止条件
        if(root==null){
            return;
        }
        //先序遍历按中左右的顺序遍历
        //递归操作:
        //遍历左
        midTravelDG(root.left,list);
        //把元素添加到list里
        list.add(root.ele);
        //遍历右
        midTravelDG(root.right,list);
    }

    //后序遍历 LRN
    public void suffixTravel(){
        List<T> list=new ArrayList<>();
        suffixTravelDG(this.root,list);
        //显示list里的item
        //先把list变成流然后拆箱再对其中的每个元素收藏到一个string里进行显示
        System.out.println(list.stream().map(item->item.toString()+"-->").collect(Collectors.joining()));
    }
    //先序遍历以root为根的树,将结果保存在list中
    private void suffixTravelDG(Node root,List<T> list){
        //递归中止条件
        if(root==null){
            return;
        }
        //先序遍历按中左右的顺序遍历
        //递归操作:
        //遍历左
        suffixTravelDG(root.left,list);
        //遍历右
        suffixTravelDG(root.right,list);
        //把元素添加到list里
        list.add(root.ele);
    }
}