手把手教你实现二叉树数据添加 | 带你学《Java语言高级特性》之三十九-阿里云开发者社区

开发者社区> Java开发者> 正文

手把手教你实现二叉树数据添加 | 带你学《Java语言高级特性》之三十九

简介: 二叉树可以优化查找效率的关键原因在于其特殊的数据保存方式,在保存时就借助比较器提前完成数据的有序摆放。本节将结合具体案例讲解实现二叉树数据保存的方法。

上一篇:初识二叉树,领悟树的概念 | 带你学《Java语言高级特性》之三十八

二叉树可以优化查找效率的关键原因在于其特殊的数据保存方式,在保存时就借助比较器提前完成数据的有序摆放。本节将结合具体案例讲解实现二叉树数据保存的方法。

【本节目标】
通过阅读本节内容,你将了解到二叉树保存数据的方式,并能够复习之前所学的比较器相关内容,借助比较器实现二叉树特殊的数据保存功能。

在实现二叉树的处理之中最为关键的问题在于数据的保存,而且数据由于牵扯到对象比较的问题,那么一定要有比较器的支持,而这个比较器首选一定是Comparable,所以本次将保存一个Person 类数据:

class Person implements Comparable<Person>{
    private String name;
    private int age;
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
    @Override
    public String toString() {
        return "【Person类对象】姓名:" + this.name + "、年龄:" + this.age + "\n";
    }

    @Override
    public int compareTo(Person per) {
        return this.age-per.age;//升序
    }
}

随后如果要想进行数据的保存,首先一定要有一个节点类。节点类中由于牵扯到数据保存问题,所以必须使用Comparable(可以区分大小);

import java.util.Arrays;
public class JavaAPIDemo {
    public static void main(String[] args) throws Exception{
        BinaryTree<Person> tree=new BinaryTree<Person>();
        tree.add(new Person("小强-80",80));
        tree.add(new Person("小强-30",30));
        tree.add(new Person("小强-50",50));
        tree.add(new Person("小强-60",60));
        tree.add(new Person("小强-90",90));
        System.out.println(Arrays.toString(tree.toArray()));
    }
}
/**
 * 实现二叉树操作
 * @param <T> 要进行二叉树的实现
 */
class BinaryTree<T extends Comparable<T>>{
    private class Node{
        private Comparable<T> data;  //存放Comparable,可以比较大小
        private Node parent;   //保存父节点
        private Node left;   //保存左子树
        private Node right;  //保存右子树
        public Node(Comparable<T> data){    //构造方法直接负责进行数据的存储
            this.data=data;
        }
        /**
         * 实现节点数据的适当位置的存储
         * @param newNode 创建的新节点
         * @throws IllegalArgumentException 保存的数据已存在
         */
        public void addNode(Node newNode) {
            if(newNode.data.compareTo((T)this.data) <= 0){   //比当前节点数据小
                if(this.left==null){   //没有左子树
                    //当前没有左子树
                    this.left=newNode;   //保存左子树
                    newNode.parent=this;   //保存父节点
                }else{   //需要向左边继续判断
                    this.left.addNode(newNode);    //继续向下判断
                }
            }else{     //比根节点的数据大
                if(this.right==null){    //当前没有右子树
                    this.right=newNode;    //保存左子树
                    newNode.parent=this;   //保存父节点
                }else{
                    this.right.addNode(newNode);  //继续向下判断
                }
            }
        }
        /**
         * 实现所有数据的获取处理,按照中序遍历的形式来完成
         */
        public void toArrayNode() {
            if(this.left!=null){     //有左子树
                this.left.toArrayNode();    //递归调用
            }
            BinaryTree.this.returnData[BinaryTree.this.foot++]=this.data;
            if(this.right!=null){
                this.right.toArrayNode();
            }
        }
    }
    //-------------------以下为二叉树的功能实现--------------
    private Node root;  //保存根节点
    private int count;   //保存数据个数
    private Object[] returnData;   //返回的数据
    private int foot=0;   //脚标控制
    /**
     * 进行数据的保存
     * @param data 要保存的数据内容
     * @exception NullPointerException 保存数据为空时抛出的异常
     */
    public void add(Comparable<T> data){
        if(data==null){
            throw new NullPointerException("保存的数据不允许为空!");
        }
        //所有的数据本身不具备节点关系的匹配,那么一定要将其包装在Node类之中
        Node newNode=new Node(data);   //保存节点
        if(this.root==null){    //现在没有根节点,则第一个节点作为根节点
            this.root=newNode;
        }else{    //需要为其保存到一个合适的节点
            this.root.addNode(newNode);  //交由node类负责处理
        }
        this.count++;
    }
    /**
     * 以对象数组的形式返回全部数据,如果没有数据返回null
     * @return 全部数据
     */
    public Object[] toArray(){
        if(this.count==0){
            return null;
        }
        this.returnData=new Object[this.count];//保存长度为数组长度
        this.foot=0;    //脚标清零
        this.root.toArrayNode();   //直接通过Node类负责
        return this.returnData;   //返回全部的数据
    }
}
class Person implements Comparable<Person>{
    private String name;
    private int age;
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
    @Override
    public String toString() {
        return "【Person类对象】姓名:" + this.name + "、年龄:" + this.age +"\n";
    }

    @Override
    public int compareTo(Person person) {
        return this.age-person.age;//升序
    }
}

执行结果:
[【Person类对象】姓名:小强-30、年龄:30
, 【Person类对象】姓名:小强-50、年龄:50
, 【Person类对象】姓名:小强-60、年龄:60
, 【Person类对象】姓名:小强-80、年龄:80
, 【Person类对象】姓名:小强-90、年龄:90
]
在进行数据添加的时候只是实现了节点关系的保存,而这种关系的保存后的结果就是所有的数据都属于有序排列。

想学习更多的Java的课程吗?从小白到大神,从入门到精通,更多精彩不容错过!免费为您提供更多的学习资源。
本内容视频来源于阿里云大学

下一篇:浅谈二叉树节点删除之道 | 带你学《Java语言高级特性》之四十
更多Java面向对象编程文章查看此处

版权声明:本文中所有内容均属于阿里云开发者社区所有,任何媒体、网站或个人未经阿里云开发者社区协议授权不得转载、链接、转贴或以其他方式复制发布/发表。申请授权请邮件developerteam@list.alibaba-inc.com,已获得阿里云开发者社区协议授权的媒体、网站,在转载使用时必须注明"稿件来源:阿里云开发者社区,原文作者姓名",违者本社区将依法追究责任。 如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:developer2020@service.aliyun.com 进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
+ 订阅

Java开发者成长课堂

官方博客
官网链接