• 118489

    文章

  • 803

    评论

  • 12

    友链

  • 最近新加了换肤功能,大家多来逛逛吧~~~~
  • 喜欢这个网站的朋友可以加一下QQ群,我们一起交流技术。

二叉树原理及实现(内部类实现)

撸了今年阿里、腾讯和美团的面试,我有一个重要发现.......>>

二叉树简单介绍

在二叉树的是实现中,其基本的实现原理如下:取第一个数据为保存的根节点,小于该节点的数据放在该节点的左子树,而大于该节点的数据要放在该节点的右子树。

如果要进行数据检索的话,此时就需要进行每个节点的判断,但是它的判断是区分左右的,所以不会是整个结构都进行判断处理,所以它的时间复杂度就是“O(logn)”。

对于二叉树而言,获取数据有三种形式:先序遍历(根-左-右)、中序遍历(左-根-右)、后序遍历(左-右-根)

例如上述遍历结果

  • 先序:50-30-20-10-25-38-80-100
  • 中序:10-20-25-30-38-50-80-100(中序遍历为排序的结果)
  • 后序:10-25-20-38-30-100-80-50

二叉树实现

数据涉及到对象比较问题,所以可以用Comparable比较器的支持。

要操作的对象:

public class Person implements Comparable<Person>{
    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public int getAge() {
        return age;
    }

    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

    //按照年龄升序排序
    @Override
    public int compareTo(Person o) {
        return this.age - o.age;
//        return o.age-this.age;//降序
    }
}

首先确定二叉树的Node类,同样采用内部类的方式

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;
        }

    }

确定二叉树的类及属性

public class BinaryTree<T extends Comparable<T>> {
    private Node root;//根节点
    private int count;//数据个数
    private Object[] returnData;//返回的数据
    private int foot=0;//数组角标
}

数据添加

 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++;
    }

此时Node类中应该添加如下方法:

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 Object[] toArray(){
        if (this.count==0){//没有数据
            return null;
        }
        this.returnData = new Object[this.count];//长度即为数据的个数
        this.foot=0;//角标清零
        this.root.toArrayNode();//交由Node类处理
        return this.returnData;
    }

之后在Node类中添加操作的方法

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();//寻找最右子树
            }
        }

数据添加及遍历测试

 BinaryTree<Person> tree = new BinaryTree<>();
        tree.add(new Person("张三",30));
        tree.add(new Person("李四",20));
        tree.add(new Person("王五",70));
        tree.add(new Person("王五2",80));
        tree.add(new Person("王五3",40));
        System.out.println(Arrays.toString(tree.toArray()));

运行结果:
[Person{name='李四', age=20},
 Person{name='张三', age=30},
 Person{name='王五3', age=40},
 Person{name='王五', age=70},
 Person{name='王五2', age=80}]

判断数据是否存在

 public boolean contains(Comparable<T> data) {
        return this.root.containsNode(data);//交由Node类处理
    }

Node类中的代码:

public boolean containsNode(Comparable<T> data) {
            if (data.compareTo((T)this.data)==0){//根据排序的属性找到相同的值
                //判断其他属性是否相同
                String s = (String) this.data.toString();
                String s1 = (String) data.toString();
               if (s.equals(s1))
                    return true;//其他属性也相同
                else {//继续向下寻找
                    boolean flag = false;//记录是否寻找成功
                    if (this.left!=null){//向左寻找
                        flag = this.left.containsNode(data);
                    }
                    if (this.right!=null){//向右寻找
                        flag = this.right.containsNode(data);
                    }
                    return flag;//返回记录的值
               }
            }else if (data.compareTo((T)this.data)<0){//data比节点小,向左寻找
                if (this.left != null){//向左寻找
                    return this.left.containsNode(data);
                }else{
                    return false;
                }
            }else{//data比节点大,向右寻找
                if (this.right != null){
                    return this.right.containsNode(data);
                }else {
                    return false;
                }
            }
        }
    }

数据判断方法写完之后可以对添加方法进行优化,在添加之前看看是否存在:

 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{
            if (contains(data)){//如果数据已存在
                throw new IllegalArgumentException("数据已存在") ;
            }
            this.root.addNode(newNode);//交由Node类处理
        }
        this.count++;
    }

修改节点

public boolean update(Comparable<T> data,Comparable<T> newData){
        if (this.root !=null){//二叉树根节点存在
            Node updateNode = this.root.getNode(data);//找到要修改的节点
            if (updateNode !=null){
                updateNode.data = newData;
                return true;
            }
        }
        return false;
    }

此时Node类中的方法

public Node getNode(Comparable<T> data) {
            if (data.compareTo((T) this.data) == 0) {//根据排序的属性找到相同的值
                //判断其他属性是否相同
                String s = (String) this.data.toString();
                String s1 = (String) data.toString();
                if (s.equals(s1))
                    return this;//其他属性也相同
                else {//继续向下寻找
                    Node tempNode = null;
                    if (this.left != null) {//向左寻找
                        tempNode = this.left.getNode(data);
                    }
                    if (this.right != null) {//向右寻找
                        tempNode = this.right.getNode(data);
                    }
                    return tempNode;//返回记录的值
                }
            } else if (data.compareTo((T) this.data) < 0) {//data比节点小,向左寻找
                if (this.left != null) {//向左寻找
                    return this.left.getNode(data);
                } else {
                    return null;
                }
            } else {//data比节点大,向右寻找
                if (this.right != null) {
                    return this.right.getNode(data);
                } else {
                    return null;
                }
            }
        }

    }

数据删除

删除操作分为以下几种情况:

  • 如果待删除的节点没有子节点,那么直接删除

  • 如果待删除的节点只有一个子节点,那么直接删掉,并用其子节点去顶替他
    • 只有一个左节点
    • 只有一个右节点
  • 如果待删除的节点有两个子节点,需要首先找出他的后继节点,然后处理

删除代码:

public void remove(Comparable<T> data) {
        if (this.root != null) {//根节点存在
            if (this.root.data.compareTo((T) data) == 0) {//要删除根节点
                Node moveNode = this.root.right;
                while (moveNode.left != null) {//还有左边的节点
                    moveNode = moveNode.left;//一直向左找
                }
                moveNode.left = this.root.left;
                moveNode.right = this.root.right;
                moveNode.parent.left = null;//断开原有连接
                this.root = moveNode;//改变根节点
            }

            Node removeNode = this.root.getNode(data);//找到要删除的节点
            if (removeNode != null) {//找到要删除的信息
                //没有任何子节点
                if (removeNode.left == null && removeNode.right == null) {
                    removeNode.parent.left = null;
                    removeNode.parent.right = null;
                    removeNode.parent = null;//直接断开引用
                } else if (removeNode.left != null && removeNode.right == null) {
                    //左边不为空
                    removeNode.parent.left = removeNode.left;
                    removeNode.left.parent = removeNode.parent;
                } else if (removeNode.left == null && removeNode.right != null) {
                    removeNode.parent.left = removeNode.right;
                    removeNode.right.parent = removeNode.parent;
                } else {//两边都有节点,则将右边节点的最左边节点找到,改变其引用
                    Node moveNode = removeNode.right;
                    while (moveNode.left != null) {//还有左边的节点
                        moveNode = moveNode.left;//一直向左找
                    }
                    removeNode.parent.left = moveNode;
                    moveNode.parent.left = null;//断开原有连接
                    moveNode.parent = removeNode.parent;
                    moveNode.right = removeNode.right;//改变原始右节点的指向
                    moveNode.left = removeNode.left;
                }
                this.count--;
            }
        }
    }

所有功能完整代码:

package 二叉树;

public 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 要保存的新节点
         */
        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();//寻找最右子树
            }
        }

        /**
         * 判断节点是否存在
         *
         * @param data 要查询的节点
         * @return 找到返回true
         */
        public boolean containsNode(Comparable<T> data) {
            if (data.compareTo((T) this.data) == 0) {//根据排序的属性找到相同的值
                //判断其他属性是否相同
                String s = (String) this.data.toString();
                String s1 = (String) data.toString();
                if (s.equals(s1))
                    return true;//其他属性也相同
                else {//继续向下寻找
                    boolean flag = false;//记录是否寻找成功
                    if (this.left != null) {//向左寻找
                        flag = this.left.containsNode(data);
                    }
                    if (this.right != null) {//向右寻找
                        flag = this.right.containsNode(data);
                    }
                    return flag;//返回记录的值
                }
            } else if (data.compareTo((T) this.data) < 0) {//data比节点小,向左寻找
                if (this.left != null) {//向左寻找
                    return this.left.containsNode(data);
                } else {
                    return false;
                }
            } else {//data比节点大,向右寻找
                if (this.right != null) {
                    return this.right.containsNode(data);
                } else {
                    return false;
                }
            }
        }



        /**
         * 获取要删除或修改的节点对象
         *
         * @param data
         * @return
         */
        public Node getNode(Comparable<T> data) {
            if (data.compareTo((T) this.data) == 0) {//根据排序的属性找到相同的值
                //判断其他属性是否相同
                String s = (String) this.data.toString();
                String s1 = (String) data.toString();
                if (s.equals(s1))
                    return this;//其他属性也相同
                else {//继续向下寻找
                    Node tempNode = null;
                    if (this.left != null) {//向左寻找
                        tempNode = this.left.getNode(data);
                    }
                    if (this.right != null) {//向右寻找
                        tempNode = this.right.getNode(data);
                    }
                    return tempNode;//返回记录的值
                }
            } else if (data.compareTo((T) this.data) < 0) {//data比节点小,向左寻找
                if (this.left != null) {//向左寻找
                    return this.left.getNode(data);
                } else {
                    return null;
                }
            } else {//data比节点大,向右寻找
                if (this.right != null) {
                    return this.right.getNode(data);
                } else {
                    return null;
                }
            }
        }

    }

    /*
    二叉树的功能实现
     */
    private Node root;//根节点
    private int count;//数据个数
    private Object[] returnData;//返回的数据
    private int foot = 0;//数组角标

    /**
     * 数据保存
     *
     * @param data 要保存的数据内容
     * @throws NullPointerException     保存数据为空时抛异常
     * @throws IllegalArgumentException 数据已存在异常
     */
    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 {
            if (contains(data)) {//如果数据已存在
                throw new IllegalArgumentException("数据已存在");
            }
            this.root.addNode(newNode);//交由Node类处理
        }
        this.count++;
    }


    /**
     * 树的遍历
     *
     * @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;
    }

    public void remove(Comparable<T> data) {
        if (this.root != null) {//根节点存在
            if (this.root.data.compareTo((T) data) == 0) {//要删除根节点
                Node moveNode = this.root.right;
                while (moveNode.left != null) {//还有左边的节点
                    moveNode = moveNode.left;//一直向左找
                }
                moveNode.left = this.root.left;
                moveNode.right = this.root.right;
                moveNode.parent.left = null;//断开原有连接
                this.root = moveNode;//改变根节点
            }

            Node removeNode = this.root.getNode(data);//找到要删除的节点
            if (removeNode != null) {//找到要删除的信息
                //没有任何子节点
                if (removeNode.left == null && removeNode.right == null) {
                    removeNode.parent.left = null;
                    removeNode.parent.right = null;
                    removeNode.parent = null;//直接断开引用
                } else if (removeNode.left != null && removeNode.right == null) {
                    //左边不为空
                    removeNode.parent.left = removeNode.left;
                    removeNode.left.parent = removeNode.parent;
                } else if (removeNode.left == null && removeNode.right != null) {
                    removeNode.parent.left = removeNode.right;
                    removeNode.right.parent = removeNode.parent;
                } else {//两边都有节点,则将右边节点的最左边节点找到,改变其引用
                    Node moveNode = removeNode.right;
                    while (moveNode.left != null) {//还有左边的节点
                        moveNode = moveNode.left;//一直向左找
                    }
                    removeNode.parent.left = moveNode;
                    moveNode.parent.left = null;//断开原有连接
                    moveNode.parent = removeNode.parent;
                    moveNode.right = removeNode.right;//改变原始右节点的指向
                    moveNode.left = removeNode.left;
                }
                this.count--;
            }
        }
    }

    /**
     *
     * @param data 要修改的数据
     * @param newData 修改后的数据
     * @return 修改成功true
     */
    public boolean update(Comparable<T> data,Comparable<T> newData){
        if (this.root !=null){//二叉树根节点存在
            Node updateNode = this.root.getNode(data);//找到要修改的节点
            if (updateNode !=null){
                updateNode.data = newData;
                return true;
            }
        }
        return false;
    }

    /**
     * 判断节点是否存在
     *
     * @param data
     * @return
     */
    public boolean contains(Comparable<T> data) {
        return this.root.containsNode(data);//交由Node类处理
    }

}

测试类:


import java.util.Arrays;

public class DemoTree {
    public static void main(String[] args) {
        BinaryTree<Person> tree = new BinaryTree<>();
        tree.add(new Person("张三-7",80));
        tree.add(new Person("张三-3",50));
        tree.add(new Person("张三-5",60));
        tree.add(new Person("张三-2",30));
        tree.add(new Person("张三-9",90));
        tree.add(new Person("张三-1",10));
        tree.add(new Person("张三-4",55));
        tree.add(new Person("张三-6",70));
        tree.add(new Person("张三-8",85));
        tree.add(new Person("张三-10",95));

        System.out.println(Arrays.toString(tree.toArray()));

        //删除最左节点
        tree.remove(new Person("张三-7",80));
       System.out.println(Arrays.toString(tree.toArray()));

    }
}

树的删除非常繁琐


695856371Web网页设计师②群 | 喜欢本站的朋友可以收藏本站,或者加入我们大家一起来交流技术!

0条评论

Loading...


自定义皮肤 主体内容背景
打开支付宝扫码付款购买视频教程
遇到问题联系客服QQ:419400980
注册梁钟霖个人博客