1.为什么需要树这种数据结构：
1）数组存储方式的分析：
优点：通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。
缺点：如果要检索具体某个值，或者，或者插入值（按一定顺序）会整体移动，效率较低。
如ArrayList数组扩容：每次在底层都需要创建新数组，再将原来的数据拷贝到数组中，并插入新的数据。
2）链式存储方式的分析
优点：在一定程度上对数组存储方式有优化（比如：插入一个数值节点，只需要将插入节点，链接道链表中即可，删除效率也很好）。
缺点：在进行检索时，效率仍然较低，比如（检索某个值，需要从你个头节点开始遍历）。
3）树存储方式的分析
能提高数据存储，读取的效率，比如利用二叉排序树，既可以保证数据的检索速度，同时也可以保证数据的插入、删除、修改的速度。
2.二叉树
树的常用术语：
1）节点；2）根节点；3）父节点；4）子节点；5）叶子节点（没有子节点的节点）；6）节点的权（节点值）；7）路径（从根节点找到该节点的路线）；8）层；9）子树；10）树的高度（最大层数）；11）森林（多棵子树构成森林）。
二叉树的概念
1）树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树。
2）二叉树的子节点分为左节点和右节点。
3）如果该二叉树的所有叶子节点都在最后一层，并且节点总数=2^n-1，n为层数，则我们称为满二叉树。
4）如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树。
区别：
完全二叉树：设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边。
满二叉树：深度为k且有2^k-1个结点的二叉树称为满二叉树。
二叉树的遍历：
前序遍历：先输出父节点，再遍历左子树和右子树；
中序遍历：先遍历左子树，再输出父节点，再遍历右子树；
后序遍历：先遍历左子树，再遍历右子树，最后输出父节点。
小结：看输出父节点的顺序，就确定是前序、中序还是后序。
遍历步骤：
1.创建一颗二叉树；
2.前序遍历：先输出当前节点（初始的时候是根节点），然后如果左子节点不为空，则递归继续前序遍历；如果右子节点不为空，则递归继续前序遍历。
3.中序遍历：如果当前节点的左子节点不为空，则递归继续中序遍历，然后输出当前节点；如果右子节点不为空，则递归继续中序遍历。
4.后序遍历：如果当前节点的左子节点不为空，则递归继续后序遍历；如果右子节点不为空，则递归继续后序遍历；然后输出当前节点。
public class BinaryTreeDemo { public static void main(String[] args) { // 先需要创建一颗二叉树 BinaryTree binaryTree = 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); binaryTree.setRoot(root); System.out.println("前序遍历结果："); binaryTree.preOrder(); System.out.println("-----------------------"); System.out.println("中序遍历结果："); binaryTree.infixOrder(); System.out.println("-----------------------"); System.out.println("后序遍历结果："); binaryTree.postOrder(); } } // 定义一个二叉树 class BinaryTree{ private HeroNode root; public void setRoot(HeroNode root) { this.root = root; } // 前序遍历 public void preOrder(){ if(this.root != null){ this.root.preOrder(); }else{ System.out.println("当前二叉树为空，无法遍历"); } } // 中序遍历 public void infixOrder(){ if(this.root != null){ this.root.infixOrder(); }else{ System.out.println("当前二叉树为空，无法遍历"); } } // 后序遍历 public void postOrder(){ if(this.root != null){ this.root.postOrder(); }else{ System.out.println("当前二叉树为空，无法遍历"); } } } // 先创建HeroNode节点 class HeroNode{ private int no; // 编号 private String name; // 姓名 private HeroNode left; // 默认null private HeroNode right; // 构造方法 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(){ // 先输出当前节点 // this指代当前调用这个方法的对象，即一个节点（初始为根节点） 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); // 先输出父节点 } }
二叉树的查找
使用前序、中序、后序的方式来查询指定的节点。
前序查找思路：
1.先判断当前节点的值是否等于要查找的；
2.如果是相等的，则返回当前节点；
3.如果是不等的，则判断当前节点的左子节点是否为空，如果不为空，则递归前序查找；如果左递归前序查找，找到节点则返回，否则继续判断，当前节点的右子节点是否为空，如果不空，则继续向右递归前序查找。
中序后序查找思路类似，顺序不同，此处不赘述。
// 前序遍历查找 public HeroNode preOrderSearch(int no){ // 与当前值进行比较 if(this.no == no) return this; // 递归停止条件 HeroNode resultNode = null; // 保留结果,初始化为空 // 判左空，向左递归 if(this.left != null){ resultNode = this.left.preOrderSearch(no); } // 左边找不到的前提下，才遍历右边 if(resultNode != null){ // 在左边找到了 return resultNode; } // 左边没找到，遍历右边 if(this.right != null){ resultNode = this.right.preOrderSearch(no); } // 否则查找不到 return resultNode; } // 中序遍历查找 public HeroNode infixOrderSearch(int no){ HeroNode resultNode = null; // 保留结果,初始化为空 // 判左空，向左递归 if(this.left != null){ resultNode = this.left.preOrderSearch(no); } // 左边找不到的前提下，才遍历右边 if(resultNode != null){ // 在左边找到了 return resultNode; // 如果找到，则返回 } // 如果没找到，就和当前节点做比较，如果是则返回当前节点 if(this.no ==no){ return this; } // 否则，向右递归 if(this.right != null){ resultNode = this.right.preOrderSearch(no); } return resultNode; } // 后序遍历查找 public HeroNode postOrderSearch(int no){ HeroNode resultNode = null; if(this.left != null){ resultNode = this.left.postOrderSearch(no); } if(resultNode != null){ return resultNode; } if(this.right != null){ resultNode = this.right.postOrderSearch(no); } if(resultNode != null){ return resultNode; } // 如果左右子树都没找到，就判断当前节点 if(this.no == no){ return this; } return resultNode; }
二叉树删除节点
简单要求：
1）如果删除的节点是叶子节点，则删除该节点；
2）如果删除的节点是非叶子节点，则删除该子树；
完成删除节点的操作步骤：
首先考虑如果树是空树root，如果只有夜歌root节点，则等价将二叉树置空。
1.因为我们的二叉树是单向的，所以我们是判断当前节点的子节点是否需要删除节点，而不能判断当前这个节点是不是需要删除节点。
2.如果当前节点的左子树不为空，并且左子节点就是要删除节点，就将this.left=null；并且就返回（结束递归）;
3.如果当前节点的右子树不为空，并且右子节点就是要删除节点，就将this.right=null;并且就返回（结束递归）;
4.如果第2步和第3步没有删除节点，那么我们就需要向左子树（先判空）进行递归删除；
5.如果第4步没有删除节点，那么我们就需要向右子树（先判空）进行递归删除；
public void delNode(int no){
// 判断当前结点的左子节点不为空，并且左子节点就是要删除节点
if(this.left != null && this.left.no == no){
this.left = null;
return;
}
// 如果执行到这一步，就证明左子树没有
if (this.right != null && this.right.no == no){
this.right = null;
return;
}
// 左右都没找到，那么就往子树递归
if(this.left != null) this.left.delNode(no);// 此处不要写return，避免没有删除的情况返回了
if(this.right != null) this.delNode(no);
}public void delNode(int no){
// 首先判断root是否为空
if(root != null){
// 如果只有一个root节点，判断root是不是要删除节点
if(root.getNo() == no){
root = null;
return;
}else{
root.delNode(no);
}
}else System.out.println("该树为空，无法删除");
}顺序存储二叉树
概念：从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组。
简单要求：
1）将二叉树的节点，以数组的方式来存放；
2）要求在遍历数组arr时，仍然可以以前序遍历、中序遍历和后序遍历的方式完成节点的遍历。
顺序存储二叉树的特点：
1）顺序二叉树通常只考虑完全二叉树；
2）第n个元素的左子节点为2*n+1；
3）第n个元素的左子节点为2*n+2；
4）第n个元素的父节点为（n-1）/2；
5）n：表示二叉树中的第几个元素（按0开始编号，即下标）
需求：提供一个数组{1,2,3,4,5,6,7}，要求以二叉树前序遍历的方式进行遍历。
前序遍历的结果应当为1,2,4,5,3,6,7。
public static void main(String[] args) {
int[] arr = {1,2,3,4,5,6,7};
traverse(arr,0);
}
public static void traverse(int[] arr,int index){
// if(index >= arr.length) return; // 递归停止条件
// 不大于
System.out.printf("% d",arr[index]); // 前序先输出 1 2 4 5 3 6 7
if(2 * index + 1 < arr.length) { // 然后向左递归 // 递归停止条件
traverse(arr, 2 * index + 1);
}
if(2 * index + 2 < arr.length){ // 最后向右递归
traverse(arr, 2 * index + 2);
}
}
八大排序算法中的堆排序，就会使用到顺序存储二叉树。
线索化二叉树
将数组{1,3,6,8,10,14}构建成一棵二叉树。
问题分析：
1）当我们对上面的二叉树进行中序遍历时，数列为{8,3,10,1,6,14}；
2）但是6，8，10，14这几个左右指针，并没有完全地利用上；
3）如果我们希望充分地利用各个节点的左右指针，让各个节点可以指向自己的前后节点，使用线索化二叉树。
线索化二叉树基本介绍：
1）n个节点的二叉链表中含有n+1【公式2n-(n-1)=n+1】个空指针域。利用二叉链表中的空指针域，存放指向该节点在某种遍历次序下的前驱和后继节点的指针（这种附加的指针称为“线索”）。
2）这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树，根据线索性质的不同，线索二叉树可分委前序线索二叉树、中序线索二叉树和后序线索二叉树三种。
3）一个节点的前一个节点，称为前驱节点；
2）一个节点的后一个节点，称为后继节点。