后面咱们学了不同的数据结构，明天学习的是一种特地的数据结构：树
首先咱们思考一下：什么是树呢？为什么咱们须要学习这种数据结构呢？
一、为什么须要树这种数据结构
咱们比照之前学习的数据结构，剖析看看之前的数据结构有什么特点又有什么缺点
一、数组存储形式的剖析
长处:通过下标形式拜访元素，速度快。对于有序数组，能够应用二分查找进步检索速度。
毛病:如果要操作具体插入值，那么会整体挪动(按肯定程序)，效率较低
如果我以后有数组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 信息
//创立英雄节点HeroNodeclass 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=关胜五、意识二叉树的删除节点
因为目前的二叉树：临时是没有规定的，后边深刻时再解决怎么把左节点或者右节点晋升下来的问题。
示例三:
- 规定一：如果
删除的节点是叶子节点，则删除该节点 - 规定二：如果
删除的节点是非叶子节点，则删除该子树. - 指标：
删除叶子节点五号和子树三号.
思路剖析
- 如果树自身为空，只有一个root节点则等价于二叉树置空
- 因为咱们的二叉树是链表单向的，所以删除指标节点时不能直接判断是否删除该节点。
- 如果以后节点左子节点不为空，并且左子节点是须要删除的节点就将this.left = null，并完结返回
- 如果以后节点右子节点不为空，并且右子节点是须要删除的节点就将this.right = null，并完结返回
- 如果以后节点没有删除的节点，则判断左节点是否为空，进行左递归持续删除
- 如果左节点左递归没有删除的节点，则判断右节点是否为空，进行右递归持续删除
接下来咱们在别离在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