1.1 数组储存方式的分析
优点: 通过下标的访问，速度快，还可以使用二分法提高检索的速度
缺点: 如果要检索某个值，或者插入值。整个数组就会进行移动，从而造成较低的效率。同时如果需要扩容的话，从底层而言，每一次数组的扩容就要重新进行创建一个新的数组(参考ArrayList，底层维护了一个object类型的数组，所以它的添加操作效率不是很高)
1.2 链表存储方式的分析
优点: 在一定程度上对于数组做出优化（可以参考数据结构小白之链表）,在进行插入和删除的时候只需要移动一个节点即可
缺点: 在检索具体的值时，效率依然比较低，比如在检索具体的值，需要从头节点进行遍历
1.3 树存储方式的分析
可以提高数据存储和读取的效率，比如利用二叉排序树，既可以保证数据的检索速度，也可以保证数据的插入，删除和修改的速度
2.1 二叉树的特征
* 每一个节点最多只能有两个子节点(左子节点和右子节点)
* 如果二叉树的所有叶子节点都在最后一层，节点总数为 2*n-1(n为层数)，称为满二叉树
* 如果二叉树的深度为k，除了第k层外，其他(1 到 k-1层节点都达到了最大值，且第k层所有的节点都连续集中在最左边，这样的树就是完全二叉树)
2.2 二叉树的遍历(核心在于递归)
二叉树的遍历分为前序，中序和后序遍历
前序遍历: 按照 根节点->左子节点->右子节点的顺序进行遍历
中序遍历: 按照 左子节点->根节点->右子节点的顺序进行遍历
后序遍历: 按照 左子节点->右子节点->根节点的顺序进行遍历
举个栗子
(1) 先去准备pojo(相应的树节点)
package tree_op;
import org.omg.CORBA.NO_IMPLEMENT;
//创建树的节点
public 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 + '\'' +
']';
}
（2）开始进行前序遍历（根->左->右）
//编写前序遍历的方法 根->左->右
public void preOrder() {
//输出父节点
System.out.println(this);
//递归向左
if (this.left != null) {
this.left.preOrder();
}
//递归向右子树遍历
if (this.right != null) {
this.right.preOrder();
}
}（3）开始进行中序遍历（左->根->右）
//编写中序遍历的方法 左->根->右
public void infixOrder() {
//递归向左
if (this.left != null) {
this.left.infixOrder();
}
//输出父节点
System.out.println(this);
//递归向右
if (this.right != null) {
this.right.infixOrder();
}
}(4) 开始进行后序遍历(左->右->根)
//编写后序遍历的方法 左->右->根
public void postOrder() {
//遍历向左
if (this.left != null) {
this.left.postOrder();
}
//遍历向右
if (this.right != null) {
this.right.postOrder();
}
//中
System.out.println(this);
}注: 二叉树的三种遍历操作逻辑上而言非常简单,就是按照遍历顺序给出相应的代码即可，代码的重复度也很高（如果愿意的话可以把对左子树 根 右子树的操作抽离出来，然后在这使用的就是三个方法的排列...）
//对于左节点的操作(1)
if(this.left != null) {
this.left.postOrder();
}
//对于右节点的操作（2）
if(this.right != null) {
this.right.postOrder();
}
//对于根的操作（3）
System.out.println(this);
前序遍历 3-1-2
中序遍历 1-3-2
后序遍历 1-2-32.3 二叉树的查找(核心在于递归)
（1） 开始进行前序查找
//编写前序查找方法
//比较->左递归->右递归
//如果找到了就返回该node，如果没有找到返回null
public HeroNode preOrderSearch(int no) {
HeroNode resNode = null;
//比较当前节点是不是
if (this.no == no) {
return this;
}
//判断当前节点的左节点是否为空，如果不为空则进行左递归
if (this.left != null) {
resNode = this.left.preOrderSearch(no);
}
if (resNode != null) {
return resNode;
}
//如果resNode为空，则判断右子节点情况
if (this.right != null) {
resNode = this.right.preOrderSearch(no);
}
return resNode;
}
(2) 开始进行中序查找
//编写中序查找算法
//左递归->比较->右递归
public HeroNode infixOrderSearch(int no) {
HeroNode resNode = null;
//开始进左递归查找
if (this.left != null) {
resNode = this.left.infixOrderSearch(no);
}
if (resNode != null) {
return resNode;
}
//如果找到，则返回,如果没有找到，就和当前节点比较
if (this.no == no) {
return this;
}
//否则进行继续向右进行中序查找
if (this.right != null) {
resNode = this.right.infixOrderSearch(no);
}
return resNode;
}
(3)开始进行后序查找
//后序遍历查找
//左递归->右递归->中
public HeroNode postOrderSearch(int no){
//左递归
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;
}
//中
if(this.no==no){
return this;
}
return resNode;
}
注: 二叉树的查找算法也是几个小方法的重复使用，依旧按照前序，中序，后序的不同，控制方法的调用时机
//根节点操作 1
if (this.no == no) {
return this;
}
//左子节点操作 2
if (this.left != null) {
resNode = this.left.preOrderSearch(no);
}
//右子节点操作 3
//如果resNode为空，则判断右子节点情况
if (this.right != null) {
resNode = this.right.preOrderSearch(no);
}
//判断resNode是否为null 4
if (resNode != null) {
return resNode;
}
//直接返回resNode (用于最后一轮判断) 5
return resNode;
则 对于查找操作而言
1.前序查找: 1 2 4 3 5
2.中序查找: 2 4 1 3 5
3.后序查找 2 4 3 1 5
注: 这里仅仅给出了关于遍历和查找的核心代码，欢迎大家来我的github取完整代码:
https://github.com/Lzin/tree_structure/tree/master/src/tree_op
测试结果:
D:\lock\java\jdk\bin\java.exe -javaagent:D:\JetBrains\apps\IDEA-U\ch-0\183.5429.30\lib\idea_rt.jar=4988:D:\JetBrains\apps\IDEA-U\ch-0\183.5429.30\bin -Dfile.encoding=UTF-8 -classpath D:\lock\java\jdk\jre\lib\charsets.jar;D:\lock\java\jdk\jre\lib\deploy.jar;D:\lock\java\jdk\jre\lib\ext\access-bridge-64.jar;D:\lock\java\jdk\jre\lib\ext\cldrdata.jar;D:\lock\java\jdk\jre\lib\ext\dnsns.jar;D:\lock\java\jdk\jre\lib\ext\jaccess.jar;D:\lock\java\jdk\jre\lib\ext\jfxrt.jar;D:\lock\java\jdk\jre\lib\ext\localedata.jar;D:\lock\java\jdk\jre\lib\ext\nashorn.jar;D:\lock\java\jdk\jre\lib\ext\sunec.jar;D:\lock\java\jdk\jre\lib\ext\sunjce_provider.jar;D:\lock\java\jdk\jre\lib\ext\sunmscapi.jar;D:\lock\java\jdk\jre\lib\ext\sunpkcs11.jar;D:\lock\java\jdk\jre\lib\ext\zipfs.jar;D:\lock\java\jdk\jre\lib\javaws.jar;D:\lock\java\jdk\jre\lib\jce.jar;D:\lock\java\jdk\jre\lib\jfr.jar;D:\lock\java\jdk\jre\lib\jfxswt.jar;D:\lock\java\jdk\jre\lib\jsse.jar;D:\lock\java\jdk\jre\lib\management-agent.jar;D:\lock\java\jdk\jre\lib\plugin.jar;D:\lock\java\jdk\jre\lib\resources.jar;D:\lock\java\jdk\jre\lib\rt.jar;D:\java_algorithm\structure_code\tree_structure\out\production\tree_structure tree_op.BinaryTreeDemo
前序遍历:
HeroNode[no=1, name='p1']
HeroNode[no=2, name='p2']
HeroNode[no=3, name='p3']
HeroNode[no=5, name='p5']
HeroNode[no=4, name='p4']
========================
中序遍历:
HeroNode[no=2, name='p2']
HeroNode[no=1, name='p1']
HeroNode[no=5, name='p5']
HeroNode[no=3, name='p3']
HeroNode[no=4, name='p4']
========================
后序遍历:
HeroNode[no=2, name='p2']
HeroNode[no=5, name='p5']
HeroNode[no=4, name='p4']
HeroNode[no=3, name='p3']
HeroNode[no=1, name='p1']
========================
前序查找
查询到该节点的编号为5 该节点的名称为p5
========================
中序查找
查询到该节点的编号为4 该节点的名称为p4
========================
后序查找
未找到该结点
Process finished with exit code 0