1、定义
树是由n（n>=1）个结点、n-1条边组成的具有层次关系且不存在环的非线性的有穷集合。
1.1、结点
树中的元素 = 值 + 所有子结点的列表。
1.2、边
用于父结点连接并指向子结点。
1.3、父子结点
在树的上下级层次关系中，上级结点为父结点，该父结点的下级结点为其子结点。
1.4、兄弟结点
同一个父结点的子结点互为兄弟结点。
1.5、根结点(树根)
在树中没有父结点的结点。
1.6、叶子结点(终端结点)
在树中没有子结点的结点。
1.7、子树
除了根结点外的若干子结构树。
1.8、空树
没有结点的树。
1.9、结点的度
一个结点含有的子结点的个数。
1.10、结点的层次
从根结点开始为第1层，根结点的子结点为第2层，以此类推。
1.11、树的度
树中结点的度的最大值。
1.12、树的高度(树的深度)
树中结点的层次的最大值。
树.png
2、为什么需要树结构？
数组与线性表查找元素都需要从头到尾一条路搜索，而树结构查找元素从头到尾有若干条路搜索，类似于书的目录，在同一维度不同度量的场景下提高了查找效率。
3、类型
3.1、二叉树——Binary Tree
每个结点最多有2个子结点(左子结点、右子结点)的树。
如果存储在数组中，则通常情况下，根结点索引为0；父结点索引为i，其左子结点索引为2i+1，其右子结点索引为2i+2。
二叉树.png
3.1.1、满二叉树——Full Binary Tree
除叶子结点外所有结点都有2个子结点的树。
顺序存储时内存利用率高：
根结点索引为1；父结点索引为i，其左子结点索引为2i，其右子结点索引为2i+1；层次最高的向右排列的叶子结点存储在索引为0的位置。
满二叉树.png
3.1.2、完全二叉树——Complete Binary Tree
树的最后1层最右边缺少1个靠右排列的叶子结点的满二叉树。
顺序存储时内存利用率高：
根结点索引为1；父结点索引为i，其左子结点索引为2i，其右子结点索引为2i+1；仅浪费数组索引为0的内存空间。
完全二叉树.png
3.1.3、堆——Heap
一种按照顺序存储的特殊的完全二叉树，且树中任意结点的值总是不大于或不小于其父结点的值。
跟结点值最大的堆称为最大堆或大根堆；根结点值最小的堆称为最小堆或小根堆。
堆.png
3.1.4、二叉搜索树(或二叉查找树或二叉排序树)——Binary Search Tree
任意结点的值大于左子树中任意结点的值且小于右子树中任意结点的值。
适用于文件或数据系统的高效排序与检索操作。
二叉搜索树.png
3.1.5、AVL树——AVL Tree
自平衡的二叉搜索树。
AVL树.png
3.1.6、红黑树——Red Black Tree
树中的每个结点都有红黑颜色标记的非平衡二叉搜索树。
树中的任意结点不是红色就是黑色；根结点与叶子结点(空值结点)是黑色；红色结点的子结点都是黑色；从任意结点到其每个叶子结点的所有路径都包含相同数目的黑色结点。
红黑树.png
3.2、多叉树(或N叉树)——N-ary Tree
树中结点存在2个以上子结点的树。
3.2.1、平衡树——Balance Tree
树中任意结点的左右子树的高度差都小于等于1。
平衡树.png
3.2.2、B树(或B-树)——B Tree
一种平衡的多叉搜索树。根结点至少有2个子结点；非根结点可以包含多个数据域；所有叶子结点位于同一层。
每个结点都存储记录，查找的元素距离根结点越近查询越快，适用于实现数据库和文件的索引。
B树.png
3.2.3、B+树——B+ Tree
B树的变种。仅叶子结点存储记录，且叶子结点按照存储值的大小通过链表从左到右连接，遍历叶子结点即可遍历整个树的记录；非叶子结点存储多个索引。查找元素必须要经过叶子结点，但是压缩了树的高度，查询效率更高。
B+树.png
3.2.4、哈希树——Hash Tree
高度为10的树，将从2开始的连续10个质数2，3，5，7，11，13，17，19，23，29分别作为树的根结点到第十层结点中每层结点的除数，余数的个数即下一层次的结点个数。
例如：在哈希树中查找任意关键字n。第一层有1个结点，判断n与结点是否相等，若不相等则把n的哈希码除以质数2，余数有0和1两种，则第二层有2个结点，判断n与结点是否相等，若不相等则把n的哈希码除以质数3，余数有0、1、2，则第三层有3个结点，依次类推。直到查找到关键字n或者结点为空。
哈希树查找关键字的时间复杂度是O(10)=O(1)，效率很高，但是哈希树中不能存放重复数据，也不能对数据进行排序，不适用于数据库普通索引等场景。
哈希树.png
3.2.5、字典树(或单词查找树)——Trie Tree
哈希树的变种。
树的根结点为空值；除根结点外每个结点都只表示1个字符；每个结点的所有子结点表示的字符互不相同。
适用于字符串快速检索(每层结点的连接)；字符串按照字典序排序(前序遍历的结果)；求解字符串最长公共前缀。
适用于搜索引擎、字典等根据公共前缀查找元素的算法。
字典树.png
4、基本操作
4.1、遍历
树的遍历.png
4.1.1、前序遍历
按照父结点、左子结点、右子结点的顺序递归遍历树中的所有结点。
遍历顺序：ABDECFG
4.1.2、中序遍历
按照左子结点、父结点、右子结点的顺序递归遍历树中的所有结点。
遍历顺序：DBEAFCG
4.1.3、后序遍历
按照左子结点、右子结点、父结点的顺序递归遍历树中的所有结点。
遍历顺序：DEBFGCA
4.1.4、层序遍历
从根结点开始逐层(结点的层次)从左到右访问结点。
遍历顺序：ABCDEFG
4.2、查找结点
利用二叉树的性质查找结点。
例如：二叉搜索树，结点个数是N，高度是H，查找元素时最多需要H个步骤，因为N与H是对数相关的，时间复杂度是O(logn)。
4.3、添加结点
利用二叉树的性质添加结点，添加结点后不能改变原树的性质。
例如：二叉排序树，添加时需要先查找添加的位置，时间复杂度同样是O(logn)。
4.4、删除结点
利用二叉树的性质删除结点，删除结点后不能改变原树的性质。
例如：二叉查找树，删除时需要先查找删除的位置，时间复杂度同样是O(logn)。
二叉查找树的删除分为3种情况：
4.4.1、删除的结点是叶子结点
将该结点的父结点对应的指针指向null。
4.4.2、删除的结点有1个子结点
将该结点的父结点对应的指针指向该结点的子结点。
4.4.3、删除的结点有2个子结点
4.4.3.1、将该结点替换为其左子树中最大的结点
4.4.3.2、将该结点替换为其右子树中最小的结点
5、存储方式
5.1、顺序存储，
利用数组实现。适用于存储满二叉树、完全二叉树。存储空间利用率高。
5.2、链式存储
利用链表实现。适用于直观表现二叉树的结构，存储更加灵活。
6、Java代码实现二叉树(二叉搜索树)
package com.zy.demo.util;
import java.util.Arrays;
import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;
/**
* 树
* @author zhangyang7
*/
public class TreeUtil<E> {
/* 二叉树(二叉搜索树)-----start */
//根结点
private TreeNode<E> root;
//树的结点个数
private int size;
/**
* 无参构造函数
*/
public TreeUtil(){
}
/**
* 指定根结点数据的构造函数
* @param e 根结点数据
*/
public TreeUtil(E e){
this.root = new TreeNode<>(e,null,null);
this.size++;
}
/**
* 获取树的结点个数
* @return 树的结点个数
*/
public int size(){
return this.size;
}
/**
* 按照层序打印树
* @return 打印结果
*/
@Override
public String toString() {
if(this.size == 0){
return "";
}
return Arrays.toString(layerOrderTraversal());
}
/**
* 前序遍历
* 时间复杂度：O(n) --全结点访问
* 空间复杂度：O(n) --新建队列存储遍历结果
* @return 遍历结果
*/
public Queue<Object> preOrderTraversal(){
//空树返回null
if(this.size == 0){
return null;
}
//队列存储结果
Queue<Object> queue = new ArrayBlockingQueue<>(this.size);
//前序遍历子树
preOrderQry(queue,this.root);
return queue;
}
/**
* 前序遍历递归查找
* @param queue 队列
* @param treeNode 当前结点
*/
private void preOrderQry(Queue<Object> queue,TreeNode<E> treeNode){
if(treeNode != null){
//前序遍历的顺序：父结点——>左子结点——>右子结点
queue.offer(treeNode.e);
preOrderQry(queue,treeNode.left);
preOrderQry(queue,treeNode.right);
}
}
/**
* 中序遍历
* 时间复杂度：O(n) --全结点访问
* 空间复杂度：O(n) --新建队列存储遍历结果
* @return 遍历结果
*/
public Queue<Object> inOrderTraversal(){
if(this.size == 0){
return null;
}
Queue<Object> queue = new ArrayBlockingQueue<>(this.size);
inOrderQry(queue,this.root);
return queue;
}
/**
* 中序遍历递归查找
* @param queue 队列
* @param treeNode 父结点
*/
private void inOrderQry(Queue<Object> queue,TreeNode<E> treeNode){
if(treeNode != null){
//中序遍历顺序：左子结点——>父结点——>右子结点
inOrderQry(queue,treeNode.left);
queue.offer(treeNode.e);
inOrderQry(queue,treeNode.right);
}
}
/**
* 后序遍历
* 时间复杂度：O(n) --全结点访问
* 空间复杂度：O(n) --新建队列存储遍历结果
* @return 遍历结果
*/
public Queue<Object> postOrderTraversal(){
if(this.size == 0){
return null;
}
Queue<Object> queue = new ArrayBlockingQueue<>(this.size);
postOrderQry(queue,this.root);
return queue;
}
/**
* 后序遍历递归查找
* @param queue 队列
* @param treeNode 父结点
*/
private void postOrderQry(Queue<Object> queue,TreeNode<E> treeNode){
if(treeNode != null){
//后序遍历顺序：左子结点——>右子结点——>父结点
postOrderQry(queue,treeNode.left);
postOrderQry(queue,treeNode.right);
queue.offer(treeNode.e);
}
}
/**
* 层序遍历
* 时间复杂度：O(n) --全结点访问
* 空间复杂度：O(n)+O(n)=O(n) --新建队列用于层序访问，新建数组用于存储结果。
* @return 遍历结果
*/
public Object[] layerOrderTraversal(){
//空树校验
if(this.size == 0){
return null;
}
//新建数组用于存储结果
Object[] objects = new Object[this.size];
//数组索引变量
int index = 0;
//新建队列用于层序遍历
Queue<TreeNode<E>> queue = new ArrayBlockingQueue<>(this.size);
//先输出根结点
queue.offer(this.root);
//根结点值添加到数组中。
objects[index++] = this.root.e;
//当前结点
TreeNode<E> treeNode;
//队列不为空，则继续递归
while(!queue.isEmpty()){
//取出先进的树结点
treeNode = queue.poll();
if(treeNode != null){
if(treeNode.left != null){
//输出当前结点的左子结点
queue.offer(treeNode.left);
objects[index++] = treeNode.left.e;
}
if(treeNode.right != null){
//输出当前结点的右子结点
queue.offer(treeNode.right);
objects[index++] = treeNode.right.e;
}
}
}
return objects;
}
/**
* 二叉搜索树添加结点。
* @param e 添加结点数据
* @return 添加成功则返回true；否则返回false。
*/
public boolean add(E e){
//空树则添加根结点
if(this.size == 0){
this.root = new TreeNode<>(e,null,null);
this.size++;
return true;
}
//空结点校验
if(e == null){
return false;
}
//递归添加
return add(e,this.root);
}
/**
* 二叉搜索树递归添加节点(去重)
* 时间复杂度：O(logn) --树的每一层判断1次。结点的层次与结点的个数对数相关。
* 空间复杂度：O(1) --使用有限的内存资源
* @param e 节点值
* @param treeNode 父结点
* @return 插入成功则返回true；否则返回false。
*/
private boolean add(E e,TreeNode<E> treeNode){
if(treeNode != null){
//暂定根据数据的哈希码来判断大小
//如果新结点值大于当前结点值
if(e.hashCode() > treeNode.e.hashCode()){
//当前结点的右子结点为空
if(treeNode.right == null){
//新结点添加到当前结点的右子结点
treeNode.right = new TreeNode<>(e,null,null);
this.size++;
return true;
}else{
//递归添加
add(e,treeNode.right);
}
}
//如果新结点值小于当前结点值
if(e.hashCode() < treeNode.e.hashCode()){
//当前结点的左子结点为空
if(treeNode.left == null){
//新结点添加到当前结点的左子结点
treeNode.left = new TreeNode<>(e,null,null);
this.size++;
return true;
}else{
//递归添加
add(e,treeNode.left);
}
}
}
return false;
}
/**
* 二叉搜索树查找指定结点是否存在
* @param e 指定结点值
* @return 存在则返回true；否则返回false。
*/
@SuppressWarnings("CatchMayIgnoreException")
public boolean search(E e){
//空树校验
if(this.size == 0){
return false;
}
//指定结点校验
if(e == null){
return false;
}
try {
//递归查找
search(e,this.root);
}catch (Exception ex){
if("true".equals(ex.getMessage())){
return true;
}
}
return false;
}
/**
* 递归查找指定节点值
* 时间复杂度：O(logn) --树的每一层判断1次。结点的层次与结点的个数对数相关。
* 空间复杂度：O(1) --使用有限的内存资源。
* @param e 指定结点
* @param treeNode 当前结点
*/
private void search(E e,TreeNode<E> treeNode) throws Exception {
if(treeNode != null){
int eVal = e.hashCode();
int thisVal = treeNode.e.hashCode();
if(eVal < thisVal){
//指定结点小于当前结点，则递归其左子树
search(e,treeNode.left);
}else if(eVal > thisVal){
//指定结点小于当前结点，则递归其右子树
search(e,treeNode.right);
}else{
//指定结点存在，抛出异常退出递归循环
throw new Exception("true");
}
}
}
/**
* 二叉搜索树删除指定结点。
* @param e 指定结点值
* @return 删除成功返回true；否则返回false。
*/
@SuppressWarnings("CatchMayIgnoreException")
public boolean remove(E e){
//空树校验
if(this.size == 0){
return false;
}
//指定结点校验
if(e == null){
return false;
}
try {
//递归删除
remove(e,this.root,"root",this.root);
}catch (Exception ex){
if("true".equals(ex.getMessage())){
return true;
}
}
return false;
}
/**
* 递归删除
* 时间复杂度：O(logn) --树的每一层判断1次。结点的层次与结点的个数对数相关。
* 空间复杂度：O(n) --新建队列用于存储树的遍历结果。
* @param e 要删除的结点
* @param parent 当前结点的父结点
* @param location 父结点与子结点的关系。规定："left"指子结点是父结点的左子结点；"right"指子结点是父结点的右子结点；"root"指父结点是根结点。
* @param treeNode 当前结点
* @throws Exception 结束递归循环的异常
*/
@SuppressWarnings("unchecked")
private void remove(E e,TreeNode<E> parent,String location,TreeNode<E> treeNode) throws Exception {
if(treeNode != null){
//暂定根据数据的哈希码来判断大小
int eVal = e.hashCode();
int thisVal = treeNode.e.hashCode();
if(eVal < thisVal){
//指定结点小于当前结点，则递归其左子树
remove(e,treeNode,"left",treeNode.left);
}else if(eVal > thisVal){
//指定结点小于当前结点，则递归其右子树
remove(e,treeNode,"right",treeNode.right);
}else{
//找到要删除的结点，分为三种情况：
//1、要删除的结点是叶子结点，将该结点的父结点对应的指针指向null。
if(treeNode.left == null && treeNode.right == null){
if("left".equals(location)){
parent.left = null;
}
if("right".equals(location)){
parent.right = null;
}
if("root".equals(location)){
this.root = null;
}
}
//2、要删除的结点有1个子结点，将该结点的父结点对应的指针指向该结点的子结点。
//(1)左子结点不为空，右子结点为空
if(treeNode.left != null && treeNode.right == null){
if("left".equals(location)){
parent.left = treeNode.left;
}
if("right".equals(location)){
parent.right = treeNode.left;
}
if("root".equals(location)){
this.root = treeNode.left;
}
}
//(2)左子结点为空，右子结点不为空
if(treeNode.left == null && treeNode.right != null){
if("left".equals(location)){
parent.left = treeNode.right;
}
if("right".equals(location)){
parent.right = treeNode.right;
}
if("root".equals(location)){
this.root = treeNode.right;
}
}
//3、要删除的结点有2个子结点，两种替换删除方案任选其一。
if(treeNode.left != null && treeNode.right != null){
//新建队列用于获取最值
Queue<Object> queue = new ArrayBlockingQueue<>(this.size);
//临时变量
Object obj = null;
//(1)替换删除法：用左子树的最大值结点替换要删除的结点，再删除左子树的最大值结点。
//中序遍历左子树
inOrderQry(queue,treeNode.left);
//队列最后1个元素即左子树的最大值
while (!queue.isEmpty()){
obj = queue.poll();
}
//替换
treeNode.e = (E)obj;
//删除
remove((E)obj,treeNode,"left",treeNode.left);
//(2)替换删除法：用右子树的最小值结点替换要删除的结点，再删除右子树的最小值结点。
//中序遍历右子树
inOrderQry(queue,treeNode.right);
//队列第一个元素即右子树的最小值
if(!queue.isEmpty()){
obj = queue.peek();
}
//替换
treeNode.e = (E)obj;
//删除
remove((E)obj,treeNode,"right",treeNode.right);
}
//删除结点后重新计算树的结点个数
this.size--;
//抛出异常退出递归循环
throw new Exception("true");
}
}
}
/**
* 树的结点内部类
* @param <E> 数据域
*/
private static class TreeNode<E>{
//当前结点的父结点
TreeNode<E> parent;
//当前结点的数据域
E e;
//当前结点的左子结点
TreeNode<E> left;
//当前结点的右子结点
TreeNode<E> right;`
//不指定父结点的构造函数
TreeNode(E e,TreeNode<E> left,TreeNode<E> right){
this.e = e;
this.left = left;
this.right =right;
}
//指定父结点的构造函数
TreeNode(TreeNode<E> parent,E e,TreeNode<E> left,TreeNode<E> right){
this.parent = parent;
this.e = e;
this.left = left;
this.right = right;
}
}
/* 二叉树(二叉搜索树)-----end */
}
