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

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

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

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

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

一、数组存储形式的剖析

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

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

如果我以后有数组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