乐趣区

关于java:我所知道的数据结构之树

作者：

jiezi

在

后面咱们学了不同的数据结构，明天学习的是一种特地的数据结构：树

首先咱们思考一下：什么是树呢？为什么咱们须要学习这种数据结构呢？

一、为什么须要树这种数据结构

咱们比照之前学习的数据结构，剖析看看之前的数据结构有什么特点又有什么缺点

一、数组存储形式的剖析

长处:通过下标形式拜访元素，速度快。对于有序数组，能够应用二分查找进步检索速度。

毛病:如果要操作具体插入值，那么会整体挪动(按肯定程序)，效率较低

如果我以后有数组arr {1,3,5,8,10}，若此时插入数据：6 那么能放的进去吗？

实际上是不能的，因为数组是当时调配空间的，指说原创立好空间长度就不能动静增长，然而数组在动静增加数据的时候，底层有一个动作：数组扩容。

那么是如何扩容的呢？创立新的数组，并将数据拷贝，以及插入数据后移

那么这时会有小伙伴提出：咱们应用汇合ArrayList不是能够动静增长吗？

其实咱们察看汇合ArrayList，发现也保护了数组扩容，只是策略不同。

那么咱们一起看看ArrayList 源码

private static final Object [] DEFAULTCAPACITY_ EMPTY_ ELEMENTDATA = {};

//ArrayList的结构器
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_ EMPTY_ ELEMENTDATA ;
}

咱们发现ArrayList无参结构器，上来时将空数值给到elementData数组。

那么elementData是什么？

transient 0bject [] elementData;

其实是一个对象Object数组，也就是说ArrayList保护的0bject [] elementData数组

在ArrayList容量不够的时候，有办法grow()依照不同的策略进行扩容，但依然是一个数组扩容

private void grow(int minCapacity) {
    
    int oldCapacity = elementData.length;
    int newCapacity - oldCapacity + (oldCapacity >> 1);
    
    if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;
     
    if (newCapacity - MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);
    
    elementData = Arrays.copy0f(elementData, newCapacity);
}

小结

  • ArrayList 中保护了一个Object类型的数组elementData.
  • 当创建对象时， 如果应用的是无参结构器，则初始elementData容量为0 (jdk7是10)
  • 如果应用的是指定容量capacity的结构器，则初始elementData 容量为capacity.
  • 当增加元素时: 先判断是否须要扩容，如果须要扩容，则调用grow办法，否则间接增加元素到适合地位
  • 如果应用的是无参结构器，如果第一次增加，须要扩容的话，则扩容elementData为10，如果须要再次扩容的话，则扩容elementData为1.5倍。
  • 如果应用的是指定容量capacity的结构器，如果还须要扩容，则间接扩容elementData为1.5倍。

咱们发现ArrayList为了解决扩容，依照一种策略进行的，还是会整体挪动的，效率比拟低，于是咱们看看链式存储形式能不能更好解决问题

二、链式存储形式的剖析

长处:在肯定水平上对数组存储形式有优化(比方:插入数值节点，只须要将插入节点，链接到链表中即可，删除效率也很好)。

毛病:在进行检索时，效率依然较低(比方:检索某个值，须要从头节点开始遍历)

咱们发现数组与链式都有各自的长处与毛病，那么接下来介绍新的数据结构：树 有什么不同呢？

二、什么是树？


在树的家族中，有一种高频应用的一种树结构：二叉树。

在二叉树中，每个节点最多有两个分支，即每个节点最多有两个节点，别离称为左节点与右节点。

在二叉树中，还有两个非凡的类型：满二叉树与齐全二叉树。

满二叉树：除了叶子节点外，所有节点都有两个节点。

齐全二叉树：除了最初一层以外，其余层节点个数都达到最大，并且最初一层的叶子节点向左排列

齐全二叉树看上去并不齐全，为什么这么称说它？

这和存储二叉树的两种存储办法：链式存储法与数组程序法。无关了

基于指针的链式存储法，也就是像链表一样，每个节点有三个字段。一个存储数据，两外两个别离存储指向左右节点的指针，如下图所示

基于数组的顺序存储法，就是依照法则把节点寄存在数组里，如下图所示。为了不便依照法则计算，把起始数据放在下标为一的地位上

若是非齐全二叉树则会节约大量的数组存储空间，如下图所示

树的基本操作

以二叉树为例介绍树的操作

  • 比照之前的数据结构，发现有些都是”一对一“的关系，即后面的数据只跟上面的一个数据产生连贯关系。如链表、栈、队列等
  • 树结构则是”一对多“的关系，即后面的父节点跟若干个子节点产生了连贯关系

与之前的数据结构相比，遍历一个树。

有十分经典的三种办法，别离是前序遍历、中序遍历、后序遍历

  • 前序是先输入父节点，再遍历左子树和右子树
  • 中序是先遍历左子树，再输入父节点，再遍历右子树
  • 后序是先遍历左子树，再遍历右子树，最初输入父节点

三、意识二叉树不同遍历形式

示例一：应用前序、中序、后序对上面二叉树进行遍历

咱们依据图片定义英雄节点HeroNode 信息

//创立英雄节点HeroNode
class HeroNode {

    private int no;         //英雄节点编号
    private String name;    //英雄节点名称

    private HeroNode left;  //默认null 左节点
    private HeroNode right; //默认null 右节点

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode [no =" + no +", name =" + name +"]";
    }

    /**
     * 前序遍历形式
     * 前序是先输入父节点，再遍历左子树和右子树
     */
    public void preOrder(){

        //先输入父节点
        System.out.println(this);

        //递归向左节点进行前序遍历
        if(this.left!=null){
            this.left.preOrder();
        }

        //递归向右节点进行前序遍历
        if(this.right!=null){
            this.right.preOrder();
        }

    }

    /**
     * 中序遍历形式
     * 中序是先遍历左子树，再输入父节点，再遍历右子树
     */
    public void infixOrder(){

        //递归向左节点进行前序遍历
        if(this.left!=null){
            this.left.infixOrder();
        }

        //先输入父节点
        System.out.println(this);

        //递归向右节点进行前序遍历
        if(this.right!=null){
            this.right.infixOrder();
        }

    }

    /**
     * 后序遍历形式
     * 后序是先遍历左子树，再遍历右子树，最初输入父节点
     */
    public void postOrder(){

        //递归向左节点进行前序遍历
        if(this.left!=null){
            this.left.postOrder();
        }

        //递归向右节点进行前序遍历
        if(this.right!=null){
            this.right.postOrder();
        }

        //先输入父节点
        System.out.println(this);

    }
}

咱们创立一颗二叉树 BinaryTree 信息

//定义二叉树
class BinaryTree{

    private HeroNode root;  //根节点

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    //root根节点前序遍历的办法
    public void preOrder(){
        if(this.root!=null){
            this.root.preOrder();
        }else{
            System.out.println("二叉树为空，无奈遍历");
        }
    }

    //root根节点中序遍历的办法
    public void infixOrder(){
        if(this.root!=null){
            this.root.infixOrder();
        }else{
            System.out.println("二叉树为空，无奈遍历");
        }
    }


    //root根节点后序遍历的办法
    public void postOrder(){
        if(this.root!=null){
            this.root.postOrder();
        }else{
            System.out.println("二叉树为空，无奈遍历");
        }
    }
}

当初让咱们如图所示创立二叉树与英雄节点来测试遍历看看


public class BinaryTreeDemo {

    public static void  main(String [] agrs){

        //创立二叉树
        BinaryTree tree =new BinaryTree();

        //创立英雄节点
        HeroNode root = new HeroNode(1,"松江");
        HeroNode node2 =new HeroNode(2,"吴用");
        HeroNode node3 =new HeroNode(3,"卢俊");
        HeroNode node4 =new HeroNode(4,"林冲");

        //手动创立二叉树依赖
        root.setLeft(node2);
        root.setRight(node3);
        node3.setRight(node4);
        
        //将root 节点给到二叉树
        tree.setRoot(root);
    }
}

咱们测试前序遍历，看看是否后果是[宋江-->吴用-->卢俊-->林冲]

//前序遍历
tree.preOrder();

HeroNode [no =1, name =松江]
HeroNode [no =2, name =吴用]
HeroNode [no =3, name =卢俊]
HeroNode [no =4, name =林冲]

咱们测试中序遍历，看看是否后果是[吴用-->松江-->卢俊-->林冲]

//中序遍历
tree.infixOrder();

HeroNode [no =2, name =吴用]
HeroNode [no =1, name =松江]
HeroNode [no =3, name =卢俊]
HeroNode [no =4, name =林冲]

咱们测试后序遍历，看看是否后果是[吴用-->林冲-->卢俊-->松江]

//后序遍历
tree.postOrder();

HeroNode [no =2, name =吴用]
HeroNode [no =4, name =林冲]
HeroNode [no =3, name =卢俊]
HeroNode [no =1, name =松江]

增强小练习

1.上图的3号节点”卢俊”,增加左节点[5,关胜]
2.应用前序、中序、后序 写出各自输入程序是啥？

四、意识二叉树不同遍历的查找形式

示例二:应用前序、中序、后序不同遍历对上面二叉树进行查找

剖析前序遍历查找思路

  • 判断以后节点是否符合要求等于要查找的,相等则返回以后节点
  • 不相等则,判断以后节点的左节点是否为空，不为空递归前序查找
  • 找到符合要求的节点则返回，否则持续递归查找
  • 不相等则,判断以后节点的右节点是否为空，不为空递归前序查找

剖析中序遍历查找思路

  • 判断以后节点的左节点是否为空，不为空递归中序查找
  • 符合要求的节点则返回，没有则和以后节点进行比拟，满足则返回
  • 不相等则进行右递归中序查找

剖析后序遍历查找思路

  • 判断以后节点的左节点是否为空，不为空递归后序查找
  • 符合要求的节点则返回，没有则进行右递归后序查找
  • 符合要求的节点则返回，没有则和以后节点进行比拟，满足则返回

接下来咱们在别离在HeroNode、BinaryTree增加代码

//增加前序、中序、后序查找代码
class HeroNode {
    
    //省略之前序、中序、后序遍历代码
    
    /**
     * @param no 查找no
     * @return 如果找到返回node，没有返回null
     */
    public HeroNode preOrderSearch(int no){

        System.out.println("进入前序遍历查找~~~~");

        //比拟以后节点看看是不是
        if(this.no == no){
            return this;
        }

        //1.判断以后节点的左节点是否为空，不为空递归前序查找,找到符合要求的节点则返回
        HeroNode resnode = null;
        if(this.left!=null){
            resnode = this.left.preOrderSearch(no);
        }
        //阐明左节点找到了，相等
        if(resnode != null){
            return resnode;
        }

        //不相等则,判断以后节点的右节点是否为空，不为空递归前序查找
        if(this.right != null){
            resnode = this.right.preOrderSearch(no);
        }

        return resnode;
    }

    /**
     * @param no 查找no
     * @return 如果找到返回node，没有返回null
     */
    public HeroNode infixOrderSearch(int no){

        //1.判断以后节点的左节点是否为空，不为空递归中序查找,找到符合要求的节点则返回
        HeroNode resnode = null;
        if(this.left!=null){
            resnode = this.left.infixOrderSearch(no);
        }

        //阐明符合要求的节点找到了，相等
        if(resnode != null){
            return resnode;
        }

        System.out.println("进入中序遍历查找~~~~");
        //没有则和以后节点进行比拟，满足则返回
        if(this.no == no){
            return this;
        }

        //不相等则,判断以后节点的右节点是否为空，不为空递归前序查找
        if(this.right != null){
            resnode = this.right.infixOrderSearch(no);
        }

        return resnode;
    }


    /**
     * @param no 查找no
     * @return 如果找到返回node，没有返回null
     */
    public HeroNode postOrderSearch(int no){

        //1.判断以后节点的左节点是否为空，不为空递归后序查找,找到符合要求的节点则返回
        HeroNode resnode = null;
        if(this.left!=null){
            resnode = this.left.postOrderSearch(no);
        }

        //阐明符合要求的节点找到了，相等
        if(resnode != null){
            return resnode;
        }

        //不相等则,判断以后节点的右节点是否为空，不为空右递归后序查找
        if(this.right != null){
            resnode = this.right.postOrderSearch(no);
        }
        
        
        //阐明符合要求的节点找到了，相等
        if(resnode != null){
            return resnode;
        }

        
        System.out.println("进入后序遍历查找~~~~");
        //没有则和以后节点进行比拟，满足则返回
        if(this.no == no){
            return this;
        }

        return resnode;
    }
}
//增加前序、中序、后序查找代码
class BinaryTree{
       
    //省略之前序、中序、后序遍历代码
    
    //root节点前序查找办法
    public HeroNode preOrderSearch(int no){
        if(this.root != null){
            return this.root.preOrderSearch(no);
        }else{
            return null;
        }
    }

    //root节点中序查找办法
    public HeroNode infixOrderSearch(int no){
        if(this.root != null){
            return this.root.infixOrderSearch(no);
        }else{
            return null;
        }
    }

    //root节点后序查找办法
    public HeroNode postOrderSearch(int no){
        if(this.root != null){
            return this.root.postOrderSearch(no);
        }else{
            return null;
        }
    }
}

[舒适提醒]：小伙伴肯定要增加好关胜英雄数据并关联起树的关系哦

//创立英雄节点
HeroNode node5 =new HeroNode(5,"关胜");

//手动关联二叉树依赖关系
node3.setLeft(node5);

应用前序遍历查找测试[编号：5 关胜]看看，看看是否找到并是否四次找到

System.out.println("==========================应用前序遍历查找形式");
HeroNode resNode = tree.preOrderSearch(5);
if (resNode != null) {
    System. out.printf("找到了，信息为no=%d name=%s", resNode.getNo(), resNode. getName());
} else {
    System.out. printf("没有找到no = %d的英雄",5);
}

运行输入后果如下:
==========================应用前序遍历查找形式
进入前序遍历查找~~~~
进入前序遍历查找~~~~
进入前序遍历查找~~~~
进入前序遍历查找~~~~
找到了，信息为no=5 name=关胜

应用中序遍历查找测试[编号：5 关胜]看看，看看是否找到并是否三次找到

System.out.println("==========================应用中序遍历查找形式~~~");
HeroNode resNode = tree.infixOrderSearch(5);
if (resNode != null) {
    System. out.printf("找到了，信息为no=%d name=%s", resNode.getNo(), resNode. getName());
} else {
    System.out. printf("没有找到no = %d的英雄",5);
}

运行输入后果如下:
==========================应用中序遍历查找形式~~~
进入中序遍历查找~~~~
进入中序遍历查找~~~~
进入中序遍历查找~~~~
找到了，信息为no=5 name=关胜

应用后序遍历查找测试[编号：5 关胜]看看，看看是否找到并是否二次找到

System.out.println("==========================应用后序遍历查找形式~~~");
HeroNode resNode = tree.postOrderSearch(5);
if (resNode != null) {
    System. out.printf("找到了，信息为no=%d name=%s", resNode.getNo(), resNode. getName());
} else {
    System.out. printf("没有找到no = %d的英雄",5);
}

运行输入后果如下:
==========================应用后序遍历查找形式~~~
进入后序遍历查找~~~~
进入后序遍历查找~~~~
找到了，信息为no=5 name=关胜

五、意识二叉树的删除节点

因为目前的二叉树：临时是没有规定的，后边深刻时再解决怎么把左节点或者右节点晋升下来的问题。

示例三:

  • 规定一：如果删除的节点是叶子节点，则删除该节点
  • 规定二：如果删除的节点是非叶子节点，则删除该子树.
  • 指标：删除叶子节点五号和子树三号.

思路剖析

  1. 如果树自身为空，只有一个root节点则等价于二叉树置空
  2. 因为咱们的二叉树是链表单向的，所以删除指标节点时不能直接判断是否删除该节点。
  3. 如果以后节点左子节点不为空，并且左子节点是须要删除的节点就将this.left = null，并完结返回
  4. 如果以后节点右子节点不为空，并且右子节点是须要删除的节点就将this.right = null，并完结返回
  5. 如果以后节点没有删除的节点，则判断左节点是否为空，进行左递归持续删除
  6. 如果左节点左递归没有删除的节点，则判断右节点是否为空，进行右递归持续删除

接下来咱们在别离在HeroNode、BinaryTree增加代码

//增加删除节点代码
class HeroNode {
    
    //省略之前序、中序、后序遍历代码
    //省略之前序、中序、后序查找代码代码
    //递归删除结点
    //1.如果删除的节点是叶子节点，则删除该节点
    //2.如果删除的节点是非叶子节点，则删除该子树
    public void delHerNode(int no){

        //思路
//        因为咱们的二叉树是链表单向的，所以删除指标节点时不能直接判断是否删除该节点。

//        1.如果以后节点左子节点不为空，并且左子节点是须要删除的节点就将this.left = null，并完结返回
          if(this.left != null && this.left.no == no){
              this.left = null;
              return;
          }
//        2.如果以后节点右子节点不为空，并且右子节点是须要删除的节点就将this.right = null，并完结返回
          if(this.right != null && this.right.no == no){
              this.right = null;
              return;
          }
//        3.如果以后节点没有删除的节点，则判断左节点是否为空，进行左递归持续删除
          if(this.left != null){
              this.left.delHerNode(no);
          }
//        4.如果左节点左递归没有删除的节点，则判断右节点是否为空，进行右递归持续删除
          if(this.right != null){
              this.right.delHerNode(no);
          }
    }
}
//增加删除节点代码
class BinaryTree{ 

    //省略之前序、中序、后序遍历代码
    //省略之前序、中序、后序查找代码代码
    public void delHerNode(int no){
        //如果树自身为空，只有一个root节点则等价于二叉树置空
        if(root !=null){
            //如果只有一个root结点，这里立刻判断root是不是就是要删除结点
            if(root.getNo() == no){
               root = null;
            }else{
                root.delHerNode(no);
            }
        }else{
            System.out.println("空树！不能删除");
        }
   }
}

应用删除节点测试[编号：5 关胜]看看，看看是否胜利

System.out.println("==============前序遍历显示删除前数据");
tree.preOrder();

System.out.println("==========================================删除叶子节点五号：关胜");
tree.delHerNode(5);

System.out.println("==============前序遍历显示删除后数据");
tree.preOrder();

运行后果如下：
==============前序遍历显示删除前数据
HeroNode [no =1, name =松江]
HeroNode [no =2, name =吴用]
HeroNode [no =3, name =卢俊义]
HeroNode [no =5, name =关胜]
HeroNode [no =4, name =林冲]
==========================================删除叶子节点五号：关胜
==============前序遍历显示删除后数据
HeroNode [no =1, name =松江]
HeroNode [no =2, name =吴用]
HeroNode [no =3, name =卢俊义]
HeroNode [no =4, name =林冲]

图解剖析删除节点

执行删除[叶子节点五号：关胜]，看看是如何进行的吧！

当执行办法时，先判断以后root 是否为空，紧接着判断以后root 节点no 是否等于须要删除的节点no，不满足条件进入delNode办法

delNode办法里，判断以后节点宋江左节点是否是[五号：关胜]，但左节点以后为[二号：吴用]，不满足于是接着判断右节点

但右节点以后为[三号：卢俊义]，不满足条件判断

于是判断以后左节点是否为空，不为空则进行左递归查问再次进入delNode办法，那么以后节点为[二号：吴用]

delNode办法里，判断以后节点吴用左节点是否是[五号：关胜]，但以后吴用节点左节点为空于是接着判断右节点

但右节点以后为空，不满足条件判断

于是判断以后左节点是否为空，不为空则进行左递归查问再次进入，然而很遗憾，吴用的右边是null，则进行判断右节点

然而吴用左边也是null，则往回溯回到宋江的左递归查问

接着判断以后宋江右节点是否为空，不为空则进行右递归查问再次进入delNode办法，那么以后节点为[三号：卢俊义]

delNode办法里，判断以后节点吴用左节点是否是[五号：关胜]，满足条件则卢俊义左节点更改为：null


评论

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理。

更多文章