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

Annihilation 2018-12-11

二叉查找树(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);
    }

    //层次遍历可以利用队列的性质完成,其主要思路如下:先将根节点放入队列中,然后每次都从队列中取出一个节点打印该节点的值,若这个节点有子节点,则将它的子节点放入队列尾,直到队列为空。
    public void layerOrder() {
        if(this.root==null) {
            return;
        }
        Queue<BNode> queue=new LinkedList<>();
        queue.add(this.root);
        while(!queue.isEmpty()) {
            BNode p=queue.poll();
            System.out.print(p.data+" ");
            if(p.left!=null) {
                queue.add(p.left);
            }
            if(p.right!=null) {
                queue.add(p.right);
            }
        }

    }
 
    public static void main(String[] args) {
        BinaryTree test=new BinaryTree();
        test.insert(3);
        test.insert(2);
        test.insert(1);
        test.insert(4);
        test.insert(5);
        //test.inOrder();
        //test.preOrder();
        test.posOrder();

    }
}

总结:上诉测试结构test.inOrder()打印输出1 2 3 4 5,test.preOrder()打印输出3 2 1 4 5, test.posOrder()打印输出1 2 5 4 3,test.layerOrder()打印输出3 2 1 4 5。

相关推荐