Java数据结构与算法之“树”
目录
一、什么是树
编辑
二、树的相关组成
1. 常用名词
2.需要了解的名词
三、树的分类
（一）初级树
1.普通树
2.二叉树
（二）中级树
1.哈夫曼树HuffmanTree
2.二叉搜索树BST
3.平衡二叉树AVL
（三）高级树
1.B树
2.Trie树
3.Merkle树
四、树的实例：二叉排序树
1.bst的代码实现
2.针对各类树不同应用场景的总结
3.下期预告
一、什么是树
一提到树，我们往往可以联系到生活中的树，在头脑中想象有有一颗参天大树，有根有叶有分支，树从底部的根向上蔓延分叉，在枝干上长出叶，结构分明。
但是在数据结构中我们接触到的树，往往会是一颗倒着的树：根在顶部，分支向下蔓延。
树是一种树形结构，也是数形结合的数学思维在计算机领域的一种实际应用。
我们不妨去类比公司组织架构、家谱等等。
学过前端相关知识的可以去参考dom（document object model）树，它就是通过解析将html文档解析为树形数据结构
html（根节点）
/ \
head body
| / \
title h1 div
\
p（两个子节点）为方便理解我将树与dom的结构一一对应列成了表格方便大家更深入的去理解。
| 树结构术语 | DOM中的对应物 | 示例 |
|---|---|---|
| 根节点 | <html> 标签 | 整个文档的起点 |
| 父节点 | 包含其他元素的元素 | <div> 包含 <p> |
| 子节点 | 被包含的元素 | <p> 是 <div> 的子节点 |
| 兄弟节点 | 同一层级的元素 | 两个并列的 <li> |
| 叶子节点 | 没有子元素的节点 | 文本节点或空标签 <img> |
二、树的相关组成
1. 常用名词
（1）节点
树中的每个元素称为节点。
每个节点包含一个值或数据，以及指向其子节点的链接。
位于树顶部的是根节点，如图A
（2）子树
由某个节点及其所有后代节点组成的树。
每个节点都可以看作是一个子树的根节点。
图中B、CEF、D构成了三棵子树
（3）空树
树是由n(n>=0)个结点组成的有限集合，其中当n=0时，它是一颗空树，空树是树的特例。
（4）叶子节点
没有子节点的节点。
也可以说是子树个数为0的节点。
叶子节点是树的末端节点。
如图BEFD
2.需要了解的名词
（1）节点的度
该节点所含子树的个数
同时也可以理解为：节点度是指和该节点相关联的边的条数，又称关联度。
（2）树的度
（节点的度）max
（3）节点的深度
根节点到当前节点所在唯一路径上的节点总数、
根节点的深度通常为1
（4）节点的高度
当前节点到最远叶子节点所在路径上的节点总数
（5）树的高度
（节点的高度）max
（6）树的深度
（节点的深度）max
个人感觉深度往往比高度更加常用。
总结一下：
- 根节点（Root）：树的起点。
- 父节点（Parent）、子节点（Child）、叶子节点（Leaf）：层级关系。
- 高度（Height） 和 深度（Depth）：描述节点的相对位置。
- 度（Degree）：一个节点的子节点数量。
三、树的分类
个人根据树的复杂程度，按照学习难度分成了初级、中级、高级三种分类。
（一）初级树
1.普通树
任意节点可以有多个子节点且没有特殊约束。
2.二叉树
每个节点最多有两个子节点，这是二叉树最基本的结构。
（1）满二叉树
所有非叶子节点都有两个子节点，可以理解为所有层都填满节点。
（2）完全二叉树
除了最后一层可以不满但叶子节点必须靠左。
（二）中级树
1.哈夫曼树HuffmanTree
更多的用在数据的压缩上，如文件压缩，基于字符的频率或权重变长编码实现更有效的存储。详细的建树过程我会单独放在一篇教程中。
2.二叉搜索树BST
BST:Binary Search Tree
左子树的值<根节点的值<右子树的值
3.平衡二叉树AVL
一种自平衡的二叉搜索树
AVL 是大学教授 G.M. Adelson-Velsky 和 E.M. Landis 名称的缩写，他们提出的平衡二叉树的概念，为了纪念他们，将 平衡二叉树 称为 AVL树。
如果二叉排序树的子树间的高度相差太大，就会让二叉排序树操作的时间复杂度升级为O(n)，为了避免这一情况，为最坏的情况做准备，就出现了平衡二叉树，使树的高度尽可能的小，其本质还是一棵二叉搜索树。
可以概括为：
- 左子树和右子树的高度之差的绝对值小于等于1
- 左子树和右子树也是平衡二叉树
4.红黑树
（三）高级树
这里暂时先不进行过多的介绍，了解即可。
1.B树
2.Trie树
3.Merkle树
用一个表格进行大致的总结：
| 类型 | 节点限制 | 核心特征 | 时间复杂度 | |
| 二叉树 | 最多2个子节点 | 递归结构基础 | 遍历O(n) | |
| 二叉搜索树 | 左<根<右 | 中序遍历有序 | 查找O(h) h为树高 | |
| AVL树 | 平衡因子≤1 | 严格平衡 | 插入/删除O(log n) | |
| 红黑树 | 五大颜色规则 | 近似平衡 | 插入/删除O(log n) | |
| B树 | m阶树节点最多m-1个键 | 多路平衡 | 查询O(log_m n) | |
| 哈夫曼树 | 带权路径最短 | 贪心算法构建 | 构建O(n log n) | |
| 堆 | 完全二叉树+堆序性质 | 根节点极值 | 取极值O(1) |
四、树的实例：二叉排序树
1.bst的代码实现
import java.util.Stack;
public class TwoTree {
public TreeNode root;
//建树
public void buildTree(TreeNode node){
if(root == null){
root = node;
}else {
TreeNode cur = root;
while(true){
if(cur.data > node.data){
//排序树
//比当前节点小，放左边，怎么放？
if(cur.left == null){
//左边空，放左边
cur.left = node;
break;
}
cur = cur.left;//迭代
}else {
//比当前节点大，放右边
if(cur.right == null){
cur.right = node;
break;
}
cur = cur.right;//cur下移
}
}
}
}
//二叉树的遍历：三序遍历---前序、中序、后序
//测试用中序最方便，打印出来时升序，前后序没有规律，使用非递归方式
public void inorder(TreeNode node){
if(root==null){
return;
}else {
TreeNode cur = root;//当前节点为根节点(cur类比指针)
Stack<TreeNode> stack = new Stack<>();
while (cur!=null || !stack.isEmpty()){
//外部循环的作用：
while(cur!=null){
//压栈
stack.push(cur);
cur = cur.left;
}//若为空则出栈
TreeNode popNode = stack.pop();
System.out.println(popNode.data);
//检查出栈节点的右子树是否为空
cur = popNode.right;//非常巧妙避免了重复判断
//设置当前节点为出栈节点的右子节点
}
}
}
}
class TreeNode{
public TreeNode left;
public TreeNode right;
public int data;
public TreeNode(){
//空参
}
public TreeNode(int data){
this.data = data;
}
}
2.针对各类树不同应用场景的总结
| 树的类型 | 应用场景 |
| 二叉搜索树（BST） | 需要快速查找的数据结构，如字典查找 |
| AVL 树 | 读多写少的数据库索引 |
| 红黑树 | STL map、set、Java TreeMap |
| 哈夫曼树 | 数据压缩（如 ZIP、JPEG） |
| B-Tree | 关系型数据库索引（如 MySQL） |
| B+ Tree | 高效范围查询（如 InnoDB 引擎） |
| Trie 树 | 搜索引擎自动补全、拼写检查 |
| Merkle 树 | 区块链数据校验 |
3.下期预告
预告：下一篇内容含有对本篇bst代码（建树、排序打印）的详细分析与一道完全二叉树实战算法个人版题解的介绍 ，内容丰富，欢迎提前关注！！