Java 基础复习数据结构-树的概述

1. 树的概念

如果线性表、栈、队列是线性结构（一维结构）的话，那么树就代表着一种非线性的、
复杂的二维结构，何为线性结构、何为二维结构？就是 1 对 1 的一条直线，每个元素
都是这条线上的节点、节点之间只知道 1VS1 的、前后关系。而二维结构就是一个面，
1 对 N 的一个面，这个面上的每一个元素都对应着多个此面上其他的元素。树就是指
N 个有父子关系的节点的有限集合。树仅仅只能有一个根节点。除了根节点，其他没有
子节点的节点叫做叶子节点。树的遍历是最考究程序员算法的，因为后面的算法很多
用到了一些概念，那先将树的有关概念解释一下。

节点的度：节点拥有的子树的个数
树的度：树中所有节点的度的最大值
节点的层次：从根节点开始算起，根的层次为 1，其余节点层次为父节点层次
+1。
树的深度：树中节点的最大层次值称为树的深度。

2. 树的基本操作：

树的操作有以下：为指定节点增加子节点、判断树是否为空、返回树的根节点、返回指
定节点的父节点、返回指定节点的所有子节点集合、返回指定节点的第 i 个子节点、返
回树的深度、返回指定节点的深度、返回指定节点的索引位置。

3. 树的使用场景

树形结构使用场景非常之多，抛开编程语言不说，就看身边的例子。大家 windows
的资源管理器、开发 web 系统的树形菜单、负载均衡的内核算法可以使用哈夫曼树来
辅助实现、将要排序的数据用排序二叉树存储，查找的效率很快。

4. 树的记父节点实现

书上管其叫做父节点表示法，这个名称我觉得很容易让人产生不解，所以笔者管它
叫做记父节点实现更好一些。它的算法的原理就是利用一个节点对象，该节点对象不
仅记录了该节点的数据，还记录了此节点的父节点的位置。那么我们访问这个节点的
时候，实际上父节点也能间接的获取到了。其实我们在做很多数据库设计的时候，遇
到一个树形菜单基本上都是采用这种记父方式来实现的。其实很多的看似二维的结构，
数据库记录，都可以提取出相应的一种图形化的模型。就像 UML 的类图关系就完全
可以转化成关系型结构化数据库表模型，而数据库表结构也能提取出相应的领域模
型一样。