树结构
树是一种嵌套型结构，用来表达上下级和归属关系
每个树节点可以拥有若干个下级节点，并且下级节点的结构和上级节点的结构完全相同，可以再拥有自己的下级
树的分类
根据树节点分支数量可分为
- 二叉树，每个节点最多只有两个子节点
- 多叉树，每个节点可以有两个以上的子节点
根据树节点上数值的有序性可分为
- 查找树，也叫搜索树，这种树规定，父节点上的值，必须大于等于左孩子，小于等于右孩子
- 无序树，节点上的值无大小顺序要求
根据树节点的对称性可分为
- 平衡树，任意节点的所有子树高度，最多相差1
- 非平衡树，子树高度无要求
根据树的整体结构特征，还有这样一些特殊的树
- 完美树，树的每一层，节点都铺满，没有任何空位
- 完全树，比完全树要求稍微低一点，除了树的最后一层，其它层节点全部铺满，并且所有节点从左往右排列
- 满树，树的所有节点，要么没有子节点，要么子节点铺满
树的代码实现
树的代码实现比较简单，每个节点包含一个链表，用链表来存储子节点就行了
import java.util.LinkedList; import java.util.List; import java.util.Objects; @SuppressWarnings("all") public class TreeNode<T> { //树深度 public Integer depth = 0; //数值 public T data = null; //添加transient关键字，是告诉JSON等序列化功能，在序列化时忽略此字段 //父节点包含子节点，字节点也包含父节点，对象之间相互循环引用，会导致序列化时产生死循环 //可以通过transient来忽略parentNode字段，通过parentId来查找 public transient TreeNode parent; public final LinkedList<TreeNode> children = new LinkedList(); //添加子节点 public void add(TreeNode child) { child.parent = this; child.depth = depth + 1; children.addLast(child); } //移除子节点 public void remove(TreeNode child) { child.parent = null; child.depth = null; children.remove(child); } //添加子节点 public void add(T data) { TreeNode child = new TreeNode(); child.data = data; child.parent = this; child.depth = depth + 1; children.addLast(child); } //移除子节点 public void remove(T data) { List<TreeNode> deleteNodes = new LinkedList(); for (TreeNode child : children) if (Objects.equals(child.data, data)) { child.parent = null; child.depth = null; deleteNodes.add(child); } children.removeAll(deleteNodes); } //打印当前子树 @Override public String toString() { String childDescription = ""; if (!children.isEmpty()) { childDescription = childDescription + "（"; for (TreeNode child : children) childDescription = childDescription + child.data; childDescription = childDescription + "）"; } return data + childDescription; } public static void main(String[] args) { TreeNode<String> tree = new TreeNode(); tree.data = "S"; tree.add("A"); tree.add("B"); tree.add("C"); tree.add("D"); tree.add("C"); tree.add("C"); tree.add("C"); tree.remove("C"); TreeNode<String> child = new TreeNode(); child.data = "C"; tree.add(child); System.out.println(tree); } }
树是一种非常实用和强大的数据结构，本章讲的只是最基本的存储功能
后面会讲解更专业的特殊树结构，还有树的遍历排序查找等算法
