手机版
你好,游客 登录 注册
背景:
阅读新闻

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

[日期:2018-12-11] 来源:Linux社区  作者:Linux [字体: ]

二叉查找树(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。

Linux公社的RSS地址https://www.linuxidc.com/rssFeed.aspx

本文永久更新链接地址https://www.linuxidc.com/Linux/2018-12/155784.htm

linux
相关资讯       二叉查找树 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款