共计 2707 个字符，预计需要花费 7 分钟才能阅读完成。
GitHub 源码分享
我的项目主页：https://github.com/gozhuyinglong/blog-demos
本文源码：https://github.com/gozhuyinglong/blog-demos/tree/main/java-data-structures
1. 前言
咱们后面讲到了数组和链表两种数据结构，其各自有本人的优缺点，咱们来回顾一下。
- 数组（Array）
长处：通过下标访问速度十分快。
毛病：须要检索具体某个值时，或者插入值时（会整体挪动）效率较低
- 链表（Linked List）
长处：在插入某个值时，效率比数组高
毛病：检索某个值时效率依然较低
咱们本篇讲到的树，便能进步数据的存储和读取效率。
2. 树（Tree）
树是一种非线性的数据结构，它蕴含 n(n>=1) 个节点，(n-1) 条边的有穷汇合。把它叫做“树”是因为它看起来像一个倒挂的树，也就是说它是根朝上，叶子朝下的。
3. 树结构的特点
- 树结构的每个元素称为节点（node）
- 每个节点都有零个或多个子节点
- 没有父节点的节点叫做根节点（root）
- 每一个非根结点有且只有一个父结点
- 除了根结点外，每个子结点能够分为多个不相交的子树
- 父子节点由一条有向的边（edgeo）相连结。
4. 树的罕用术语
联合上图理解树的罕用术语，加深对树的了解。
- 节点（node）
树结构中的每一个元素称为一个节点，如上图中的 ABC……M
- 根节点（root）
没有父节点的节点叫做根节点，如上图中的 A
- 父节点（parent）
一个节点的下级节点叫做它的父节点，一个节点最多只能有一个父节点，如上图中 C 是 F 的父节点
- 子节点（child）
一个节点的上级节点叫做它的子节点，一个节点的子节点能够有多个，如上图中的 IJK 是 E 的子节点
- 兄弟节点（siblings）
领有雷同父节点的节点叫做兄弟节点，如上图中的 L 和 M 是兄弟节点
- 叶子节点（leaf）
没有子节点的节点叫做叶子节点，如图中的 BFGLMIJK
- 边（dege）
父子节点间的连贯称为边，一棵树的边数为 (n-1)
- 节点的权（weight）
节点上的元素值
- 门路（path）
从 root 节点找到该节点的路线，如上图中 L 的门路为 A -D-H-L。门路的长为该门路上边的条数，L 门路的长为 3（n-1）。
- 层（layer）
间隔根节点相等的门路长度为一层，如上图中 A 为第一层；BCDE 为第二层；FGHIJK 为第三层；LM 为第四层
- 子树（child tree）
以某一节点（非 root）做为根的树称为子树，如以 E 为根的树称为 A 的子树
- 树的高度（height）
树的最大层数，上图中树的高度为 4
- 森林（words）
多棵子树形成树林
5. 代码实现
咱们将第 3 章中的树结构图通过 Java 代码进行实现。
TreeNode 类为树的一个节点，其中：
- element：存储以后节点的元素数据
- firstChild：指向以后节点的第一个子节点（如：A 的 firstChild 为 B；D 的 firstChild 为 G；G 的 firstChild 为空）
- nextSibling：指向以后节点的下一个兄弟节点（如：B 的 nextSibling 为 C；G 的 nextSibling 为 H；H 的 nextSibling 为空）
Tree 类实现了一棵树的初始化和遍历，listAll 遍历算法的外围是递归。具体内容见代码
public class TreeDemo {public static void main(String[] args) {new Tree().initTree().listAll();
}
private static class Tree {
private TreeNode root; // 树根
/**
* 初始化一棵树
*/
private Tree initTree() {TreeNode a = new TreeNode("A");
TreeNode b = new TreeNode("B");
TreeNode c = new TreeNode("C");
TreeNode d = new TreeNode("D");
TreeNode e = new TreeNode("E");
TreeNode f = new TreeNode("F");
TreeNode g = new TreeNode("G");
TreeNode h = new TreeNode("H");
TreeNode i = new TreeNode("I");
TreeNode j = new TreeNode("J");
TreeNode k = new TreeNode("K");
TreeNode l = new TreeNode("L");
TreeNode m = new TreeNode("M");
root = a;
a.firstChild = b;
b.nextSibling = c;
c.nextSibling = d;
c.firstChild = f;
d.nextSibling = e;
d.firstChild = g;
e.firstChild = i;
g.nextSibling = h;
h.firstChild = l;
i.nextSibling = j;
j.nextSibling = k;
l.nextSibling = m;
return this;
}
/**
* 遍历一棵树，从 root 开始
*/
public void listAll() {listAll(root, 0);
}
/**
* 遍历一棵树
*
* @param node 树节点
* @param depth 层级（用于辅助输入）*/
public void listAll(TreeNode node, int depth) {StringBuilder t = new StringBuilder();
for (int i = 0; i < depth; i++) {t.append("\t");
}
System.out.printf("%s%s\n", t.toString(), node.element);
// 先遍历子节点，子节点的层级须要 +1
if (node.firstChild != null) {listAll(node.firstChild, depth + 1);
}
// 后遍历兄弟节点，兄弟节点的层级不变
if (node.nextSibling != null) {listAll(node.nextSibling, depth);
}
}
}
private static class TreeNode {
private final Object element; // 以后节点数据
private TreeNode firstChild; // 以后节点的第一个子节点
private TreeNode nextSibling; // 以后节点的下一个兄弟节点
public TreeNode(Object element) {this.element = element;}
}
}输入后果：
A
B
C
F
D
G
H
L
M
E
I
J
K