树是一种非线性数据结构，其中数据对象按层次关系组织。在这种意义上，结构是非线性的，与简单数组和链表实现不同，而树中的数据不是线性组织的。每个数据元素被存储在称为节点的结构中。 （倒置）树的最顶层或起始节点称为根节点。所有节点都与边缘链接，并形成从根节点开始的分层子树。在数据线性不足以表示的情况下，树形数据结构很有用，例如创建一个族树。 Java在Java Collection Framework中提供了两个内置的TreeSet和TreeMap类，以满足程序员通过上述形式描述数据元素的需要。
树数据结构
Java树类是特定种类的树数据结构的实际实现。因此，在使用之前，我们必须对其组织有一些了解。
根据定义，树T是一组非空的元素，其中这些元素中的一个被称为根和剩余元素（其中可能存在或可能不存在于具有空集合Set Theory的空树情况）被进一步划分为T的子树。
例如，思考以下族树中的层次关系。
图1：一棵族树
Tim的后裔节点以分层的方式安排。 （倒置）树顶部的Tim表示根节点。Tim的子节点是Bobby, Ron, 和 Amy。Bobby没有子节点，Ron有一个，Amy有两个。它们以相同的分层方式列出。每个节点之间的链接称为边。这个链接表示一个节点与另一个节点之间的关系，如Amy的子节点，Bobby的兄弟姐妹，Tim的后裔节点等等。有时，树的结尾节点称为叶。
现在，根据组织结构，树可以在很多方面实现。在其许多形式中，二叉树是特别重要的，因为它实现起来简单有效。二叉树的约束是允许最多两个子节点从父节点引出;他们分别被称为左节点和右节点。从左子节点延伸的树称为左子树，从右子节点延伸的树称为右子树。这对于任何类型的二叉树是常见的，因为二叉树还具有各种实现方案。这些方案中的每一个都有一些明确的创建和维护规范，其直接影响数据元素的访问机制，通常以大O符号表示。
例如，如果在特定类型的二叉树中搜索数据元素需要O（n2）次，并且在最坏的情况下需要另外一种类型的二叉树实现，则O（log2 n）次，则第二个实现是比第一个更有效率。
图2：二叉树实现
一些常见的二叉树类型被称为完整二叉树，完全二叉树，二叉搜索树（BST），高度平衡树（AVL），红黑树等。
红黑树
在各种类型的二叉树中，我们对红黑树感兴趣，因为Java树API实现是这种数据结构的一个实例。 Java API设计人员有理由剔除这种二叉树方案。 原因是它是许多平衡搜索树方案之一，即使在最坏的情况下也能保证O（log2 n）次的基本动态集合操作完成。
红黑树方案的属性如下：
红黑树为每个节点保留一个额外的信息，以表示其颜色，红色或黑色。
根节点总是黑色的。
每片叶子都是黑色的
红色节点的子节点都必须是黑色的。
对于每个节点，从节点到后续的所有简单路径都包含相同数量的黑色节点。
因此，实现必须确定这些属性在任何时间的情况下都保持，特别是在节点的“插入”和“删除”期间。 而且，为了保持动态的完整性，子树以错综复杂的逻辑左右旋转。 如果您想深入了解算法，并了解其在低级别中的工作原理，请阅读Cormen，Leiserson，Rivest和Stein的“算法简介”。
Java树API
幸运的是，使用Java API库时，我们不必处理红黑树的低级复杂实现逻辑。 相反，我们可以专注于解决现有问题，而不是从头开始实施该方案。 只需导入相关的软件包，并创建一个可用的现有树类的实例。 这就是我们需要做的。
如前所述，Java集合框架中有两种树型实现。 一个是TreeSet，另一个是TreeMap。 它们在java.util包中定义如下：
public class TreeSet
extends AbstractSet
implements NavigableSet, Cloneable, Serializable
public class TreeMap
extends AbstractMap
implements NavigableMap, Cloneable, Serializable
两种树类的令人兴奋的特征是，一个作为一个集合，另一个作为映射。 Set和Map分别是抽象类AbstractSet和AbstractMap实现的接口。
集合表示不同元素的集合 - 元素e1不能等于e1.equal（e2）同一集合的另一个元素e2。 此外，集合中只能有一个空元素。 它对元素的集合施加的属性是基于数学集抽象模型。
Map属性强制元素的集合必须有一个键值对。 每个键只映射到一个值; 这意味着它不允许有重复的键。 然而，具有不同键的值可能被重复。
树类TreeSet和TreeMap遵循从各自接口派生的具体规范，除了以二叉树形式组织其内部数据结构外。
TreeSet的一个快速示例
我们知道，Set实现的属性确保在将数据元素存储在树中时树不应包含任何重复项。 与其他集合实现相反，TreeSet保证根据元素的自然排序，存储的数据元素将默认排序。 让我们借助一个简单的例子来了解它的用法。
package org.mano.example;
import java.util.Arrays;
import java.util.SortedSet;
import java.util.TreeSet;
public class TreeSetDemo {
public static void main(String[] args) {
Integer[] nums={2,4,1,6,3,7,9,5};
SortedSettree=new TreeSet<>(Arrays.asList(nums));
// Print first and last element
System.out.println(tree.first());
System.out.println(tree.last());
printAll(tree);
// False. Set does not allow duplicates,
// so this will not be added.
System.out.println(tree.add(1));
// But, this will be added because 11 is not a duplicate
System.out.println(tree.add(11));
printAll(tree);
printAll(tree.headSet(7));
}
public static void printAll(SortedSettree){
for(int s: tree){
System.out.println(s);
}
System.out.println();
}
}
TreeMap的一个快速示例
一个关键的值对类很像另一个Map实现，称为HashMap。 除了将其数据元素存储在红黑树结构之外，TreeMap还保存了存储的密钥的顺序。 因此，当我们迭代键时，我们发现自然是有序的。 让我们借助一个简单的例子来看看。
package org.mano.example;
import java.util.Map;
import java.util.TreeMap;
public class TreeMapDemo {
public static void main(String[] args){
TreeMap treeMap=new TreeMap<>();
treeMap.put("Paradise Lost", 23.56);
treeMap.put("Golden Treasury", 12.47);
treeMap.put("Moon and the Sixpence", 65.28);
treeMap.put("Holinshed", 7.68);
treeMap.put("Ancient Mariner", 45.36);
printAll(treeMap);
// Keys cannot be duplicates. This will not be stored.
treeMap.put("Paradise Lost", 23.56);
printAll(treeMap);
// Values may be duplicates. This will be stored.
treeMap.put("Paradise Regained", 23.56);
printAll(treeMap);
}
public static void printAll(TreeMap treeMap){
for(Map.Entry et:treeMap.entrySet()){
System.out.println(et.getKey()+": "+et.getValue());
}
System.out.println();
}
}
结论
TreeSet和TreeMap类是Java API库中二进制树数据结构中最明显的实现。 对于高级用户，数据组织规则在其用途上没有任何差异。 但是，由于维持平衡树结构规范的许多规则，树结构比其非树或线性对象（如HashSet和HashMap）要复杂得多，效率低下。 因此，除非有特定需要，否则其对应类会比树更频繁地被使用。
