数据结构之二叉查找树Java实现源码及注释

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。以下是楼主用Java写的一个二叉搜索树类的，包含创建，添加新元素，以及常用的四种遍历方式。

//首先定义一个BNode节点，里面包含left、right初始化为null，以及int型数组data。
class BNode{
    BNode left=null;
    BNode right=null;
    int data;
    public BNode(int data){
        this.data=data;
    }
}

public class BinaryTree{
    BNode root=null;
//插入新的元素
    public void insert(int data) {
        BNode newBNode=new BNode(data);
        if(root==null) {
            root=newBNode;
        }else {

//定义一个Node型父亲节点parsent
            BNode parent=root;　　　　　 

//循环至找到节点存放的合适位置

//如果节点数值小于当前位置所指向值，判断当前节点左孩子是否存在？若当前节点左孩子不存在，将新的节点插入到前节点左方并返回结束循环，若当前节点左孩子存在，则parsent指向自身的左孩子
            while(true) {　　　　　　　     
                if(data<parent.data) {　　　　 
                    if(parent.left==null) {　　　
                        parent.left=newBNode;　 
                        return;
                    }else {
                        parent=parent.left;　　　　
                    }
                }

//如果节点数值大于当前位置所指向值，判断当前节点右孩子是否存在？若当前节点右孩子不存在，将新的节点插入到前节点右方并返回结束循环，若当前节点右孩子存在，则parsent指向自身的右孩子

　　　　else if(data>parent.data) {　　
                    if(parent.right==null) {　　　 
                        parent.right=newBNode;　
                        return;
                    }else {
                        parent=parent.right;　　
                    }
                }
            }
        }
    }

//递归思想遍历二叉树，很容易理解这里就不啰嗦了

    //中序遍历（左-根-右）
    public void inOrder(BNode root) {
        if(root!=null) {
            inOrder(root.left);　　　　　　　　
            System.out.print(root.data+" ");
            inOrder(root.right);
        }
    }
    public void inOrder() {
        this.inOrder(this.root);
    }
   
    //先序遍历（根-左-右）
    public void preOrder(BNode root) {
        if(root!=null) {
            System.out.print(root.data+" ");
            preOrder(root.left);
            preOrder(root.right);
        }
    }
    public void preOrder() {
        this.preOrder(this.root);
    }
   
    //后续遍历（左-右-根）
    public void posOrder(BNode root) {
        if(root!=null) {
            posOrder(root.left);
            posOrder(root.right);
            System.out.print(root.data+" ");
        }
    }
    public void posOrder() {
        this.posOrder(this.root);
    }