树

树形结构是一种层级式的数据结构，由节点和连接它们的边组成， java语言编写的程序中常常用引用来表示边。根是树中顶端的节 点：它没有父节点。节点表示保存在树中的数据对象。非平衡树是 指根左边的后代比右边多，或者相反。 区分树和图的主要特征是树中不存在环路。
树的节点 Root,parent,child,leaf,sibling 。
树的主要类型 N元树 平衡树 二叉树 二叉搜索树 AVL树 红黑树 2-3树（多叉树比二叉树有更多的关键字和子节点）。
树通常结合了有序数组和链表两种数据结构的优点，在树中查找数 据项的速度和在有序数组中查找一样快，并且插入数据项和删除数 据项的速度也和链表一样。 其中，二叉树和二叉搜索树是常用的树。二叉树指树中每个节点 多只能有两个子节点，二叉搜索树指一个节点的左子节点的关键 字值小于这个节点，右子节点的关键字的值大于或等于这个父节 点。 查找节点需要比较要找的关键字值和节点的关键字值，插入需要找 到要插入新节点的位置并改变他父节点的子字段来指向它。如果一 个节点没有子节点，删除它只要把它的父节点的子字段置为null即 可，如果一个节点有一个子节点，把它父节点的子字段置为它的子 节点就可以删除它，如果一个节点有两个子节点，删除它要用他的 后继（该节点的右子节点为根的子树中关键值小的那个节点）来 代替他。可以用数组表示树，不过基于引用的方法更常用。

二叉树的效率：
树的大部分操作都需要从上到下一层一层的查找某个节点，因此常 见树的操作（查找，插入，删除）时间复杂度大约是O(logN)，如 果树不满，分析起来很困难，不过，可以认为对给定层数的树，不 满的树的平均查找时间比满树要短，因为在它的较低的层上完成查 找的次数要比满树时少。 树对所有常用的数据存储操作都有很高的效率，遍历不如其他操作 快，但是，遍历在大型数据库中不是常用的操作。
B树是多叉树，每个节点可以有几十或上百个关键字和节点，B树中 子节点的个数总是比关键字的个数多1，为达到好的性能，B树通 常在一个节点中保存一块的数据。

实战

在控制台上输入一组数据，按照输入数据的格式来构造一棵二叉树，并打印出二叉树的高度。
输入的数据格式如下：
12
2 3
2 11
3 4
3 5
11 12
11 13
4 6
5 7
12 14
12 15
14 16
16 17
用二叉树表示如下：

Java代码实现如下：

输出结果为：

红黑树
普通的二叉搜索树可以快速的找到一个给定关键字的数据项，可以快速的插入和删除数据，如果二叉搜索树中插入的是随机数据，执行效果很好，但是如果插入的是有序的数据或逆序的数据，速度就会变得特别慢，因为插入的数值有序时，二叉树就是非平衡的了，而对于非平衡树，它的快速查找，插入，删除，指定数据项的能力就丧失了。红黑树是增加了某些特点（在红黑平衡的方法中，每个节点都有一个新的特征：它的颜色不是红的就是黑的）的二叉搜索树，它将解决这个问题。
效率：
在红黑树中的查找时间和在普通二叉树中的查找时间几乎完全一样，因为在查找的过程中并没有应用红黑树的特征，额外的开销只是每一个节点的存储空间都稍微增加了一点来存储红黑的颜色（一个boolean变量）。插入和删除的时间要增加一个常数因子，因为不得不在下行的路径上和插入点执行颜色变换和旋转。平均起来，一次插入大约需要一次旋转，但是比在普通的二叉搜索树中要慢。因为在大多数应用中，查找的次数比插入和删除的次数多，所以应用红黑树取代普通的二叉搜索树总体上不会增加太多的时间开销，红黑树的优点是对有些数据的操作不会慢到O(N)的时间复杂度。
总结：保持普通二叉树的平衡是非常重要的，这样可以使找到给定节点必需的时间尽可能短，在二叉树中加入红黑平衡对平均执行效率只有很小的负面影响，却避免了对有序的数据操作的最坏的性能。

上一篇：java中的数据结构——链表

读完本文你将了解到：

数据结构，指的是数据的存储形式，常见的有线性结构（数组、链表，队列、栈），还有非线性结构（树、图等）。

今天我们来学习下数据结构中的 树。

什么是树

线性结构中，一个节点至多只有一个头节点，至多只有一个尾节点，彼此连接起来是一条完整的线。

比如链表和数组：

而树，非线性结构的典型例子，不再是一对一，而变成了一对多（而图则可以是 多对多），如下图所示：

可以看到:

• 图中的结构就像一棵倒过来的树，最顶部的节点就是“根节点 (root 节点)”
• 每棵树至多只有一个根节点
• 根节点生出多个孩子节点，每个孩子节点只有一个父节点，每个孩子节点又生出多个孩子
• 父亲节点 (parent) 和孩子节点 (child) 是相对的
• 没有孩子节点的节点成为叶子节点 (leaf)

树的相关术语

根节点、父亲节点、孩子节点、叶子节点如上所述。

节点的度

一个节点直接含有的子树个数，叫做节点的度。比如上图中的 3 的度是 2，10 的度是 1。

树的度

一棵树中 最大节点的度，即哪个节点的子节点最多，它的度就是 树的度。上图中树的度为 2 。

节点的层次

从根节点开始算起，根节点算第一层，往后底层。比如上图中，3 的层次是 2，4 的层次是 4。

树的高度

树的高度是从叶子节点开始，自底向上增加。

树的深度

与高度相反，树的深度从根节点开始，自顶向下增加。

整个树的高度、深度是一样的，但是中间节点的高度 和 深度是不同的，比如上图中的 6 ，高度是 2 ，深度是 3。

树的两种实现

从上述概念可以得知，树是一个递归的概念，从根节点开始，每个节点至多只有一个父节点，有多个子节点，每个子节点又是一棵树，以此递归。

树有两种实现方式：

• 数组
• 链表

数组表示：

我们可以利用每个节点至多只有一个父节点这个特点，使用 父节点表示法 来实现一个节点：

public class TreeNode {

    private Object mData;   //存储的数据
    private int mParent;   //父亲节点的下标

    public TreeNode(Object data, int parent) {
        mData = data;
        mParent = parent;
    }

    public Object getData() {
        return mData;
    }

    public void setData(Object data) {
        mData = data;
    }

    public int getParent() {
        return mParent;
    }

    public void setParent(int parent) {
        mParent = parent;
    }
}

上述代码中，使用 角标 来指明父亲节点的位置，使用这个节点组成的数组就可以表示一棵树。

public static void main(String[] args){
    TreeNode[] arrayTree = new TreeNode[10];
}

用数组实现的树表示下面的树，（其中一种 ）结果就是这样的：

数组实现的树节点使用角标表示父亲的索引，下面用链表表示一个节点和一棵树：

链表表示的节点：

public class LinkedTreeNode {

    private Object mData;   //存储的数据
    private LinkedTreeNode mParent;   //父亲节点的下标
    private List<LinkedTreeNode> mChildNodeList;    //孩子节点的引用

    public LinkedTreeNode(Object data, LinkedTreeNode parent) {
        mData = data;
        mParent = parent;
    }

    public Object getData() {
        return mData;
    }

    public void setData(Object data) {
        mData = data;
    }

    public Object getParent() {
        return mParent;
    }

    public void setParent(LinkedTreeNode parent) {
        mParent = parent;
    }

    public List<LinkedTreeNode> getChild() {
        return mChildNodeList;
    }

    public void setChild(List<LinkedTreeNode> childList) {
        mChildNodeList = childList;
    }

}

使用引用，而不是索引表示父亲与孩子节点。

使用一个 List, 元素是 LinkedTreeNode，就可以表示一棵链表树：

public static void main(String[] args){
    LinkedList<LinkedTreeNode> linkedTree = new LinkedList<>();
}

这样只需知道 根节点就可以遍历整个树。知道某个节点也可以获取它的父亲和孩子。

树的几种常见分类及使用场景

树，为了更好的查找性能而生。

常见的树有以下几种分类：

• 二叉树
• 平衡二叉树
• B 树
• B+ 树
• 哈夫曼树
• 堆
• 红黑树

接下来陆续介绍完回来补使用场景。

本文将详细介绍树这种数据结构的基本概念，以及通用的树的Java实现方式，为后面各种树的深入学习打好基础。

树结构和线性结构的最大的不同是，树中的节点具有明显的层级关系，并且一个节点可以对应多个节点。

1 树的概述

1.1 定义

树结构和线性结构的最大的不同是，树中的节点具有明显的层级关系，并且一个节点可以对应多个节点。树的定义如下：

树（Tree）是n（n≥0）个节点的有限集。n=0时称为空树。在任意一棵非空树中：

1. 有且仅有一个特定的称为根（Root）的节点r；
2. 当n＞1时，其余节点可分为m（m＞0）个互不相交的不为空的有限集T1、T2、……、Tm，其中每一个集本身又是一棵树，并且称为根的子树（SubTree）。

从上面树的定义可以看出使用了递归的思想，也就是在树的定义之中还用到了树的概念，根的子树节点，同时作为子树的根节点。递归思想和栈数据结构有关，可以看这篇文章：数据结构—栈(Stack)的原理以及Java实现以及后缀表达式的运算。

如上图，该树具有唯一根节点r，它的子树是以a、b、c为根节点的三棵树。而子树a下面还有一颗子树d。

从递归中我们发现，一棵树是N个节点和N−1条边的集合，其中的一个节点叫做根。存在N−1条边的结论是由下面的事实得出的，每条边都将某个节点连接到它的父亲，而除去根节点外每一个节点都有一个父亲。

1.2 节点

在上图中，节点r是根。节点a有一个父亲并且儿子d、e。每一个节点可以有任意多个儿子，也可能是零个儿子。没有儿子的节点称为树叶（leaf）；上图中的树叶是e、f、g、h、i、j和k。

具有相同父亲的节点称为兄弟（sibling），比如a、b和c节点都是兄弟节点；用类似的方法可以定义祖父（grandfather）和孙子（grandchild)。

森林：两颗或两颗以上互不相交的树的集合。

1.3 深度和高度

节点的层次（Level）从根开始定义起，这里规定，根为第一层，根的孩子为第二层。若某节点在第i层，则其子树就在第i+1层。树中节点的最大层次称为树的深度（Depth)或高度，上图中，树的深度为4。

本文约定：从上往下数就是深度，从下往上数就是高度。另外由于不同的参考书对于根节点深度和高度的定义不一样，而节点的深度和高度会受到根节点的深度0还是1的影响，本文取根节点深度为1。一棵树的深度等于它的最深的树叶的深度；该深度总是等于这棵树的高度。

上图中，根节点r的深度为1，高度为4。子节点b的深度为2，高度为2。

1.4 节点的度

树的节点包含一个数据元素及若干指向其子树的分支。节点拥有的直接子节点数称为该节点的度（De-gree）。

度为0的节点称为叶节点（Leaf)或终端节点；度不为0的节点称为非终端节点或分支节点。

除根节点之外，分支节点也称为内部节点。树的度是树内各节点的度的最大值。上图中，因为这棵树节点的度的最大值是节点r和d的度，为3，所以树的度也为3。

1.5 有序性

无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树；有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树。

2 树的通用实现

树也可以采用顺序存储结构和链式存储结构实现。下面有三种通用的树实现的方法。后面介绍特殊的树时，比如二叉树、红黑树等它们还有自己的特殊实现方式。

2.1 父节点表示法

采用顺序存储结构来实现树，底层采用数组来存储节点。由于子节点具有唯一的父节点，因此，可以采用父节点表示法表示出一棵树的结构。

节点由数据域和父节点的索引位置组成，根节点的父节点索引为-1。

上图的树，使用最简单的父节点表示法可以表示为：

树节点的设计可以是：

/**
 * 树节点的设计
 *
 * @param <E> E类型
 */
private static class TreeNode<E> {
    //数据域
    E e;
    //父节点的索引
    int parent;

    public TreeNode(E e, int parent) {
        this.e = e;
        this.parent = parent;
    }
}

这样的存储结构，我们可以根据结点的parent索引很容易找到它的双亲结点，所用的时间复杂度为O(1)，直到parent为-1时，表示找到了树结点的根。但是如果要知道孩子节点是什么，那就需要遍历整个数组才行。

2.2 父子节点链表示法

为了能够直观的找到一个节点的孩子节点。在原节点中添加一个子节点链表，原节点保存子节点链表的头索引，同时节点保存着父节点的索引。这需要一种新的孩子节点。

树节点和子节点的设计可以为：

/**
 * 树节点的设计
 *
 * @param <E> E类型
 */
private static class TreeNode<E> {
    //数据域
    E e;
    //父节点的索引
    int parent;

    //第一个子节点的引用
    TreeNodeChild<E> firstChild;

    public TreeNode(E e, int parent, TreeNodeChild<E> firstChild) {
        this.e = e;
        this.parent = parent;
        this.firstChild = firstChild;
    }
}

/**
 * 子节点链表结构
 *
 * @param <E>
 */
private static class TreeNodeChild<E> {
    //子节点的索引
    int index;
    //下一个子节点的索引
    TreeNodeChild<E> next;

    public TreeNodeChild(int index, TreeNodeChild<E> next) {
        this.index = index;
        this.next = next;
    }
}

2.3 父子兄弟表示法

对于上面的父节点表示法和父子节点表示法，不能很方便的得知节点的兄弟节点。

实际上，我们观察树形结构后发现，任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个索引，分别指向该结点的第一个孩子和此结点的右兄弟。只需要两个引用就能很方便的表示出节点的唯一对应关系。

为了突破节点数量限制，我们可以使用链表。为了找到父节点，我们还可以添加父节点索引。

节点可以统一设计为如下，不需要额外的节点结构：

/**
 * 树节点的设计
 *
 * @param <E> E类型
 */
private static class TreeNode<E> {
    //数据域
    E e;
    //父节点的引用(可选)
    TreeNode<E> parent;

    //第一个子节点的引用
    TreeNode<E> firstChild;

    //右兄弟节点的引用
    TreeNode<E> rightBrother;
}

使用示意图来直观的展示这种表示法的效果：

图中只标出了子节点和兄弟节点的引用链，红色为子节点引用，黑色为右兄弟节点的引用。我们看到，只需要这两个引用关系就能表示出一颗完整的树。并且需要查找某个节点的子节点或者父节点或者兄弟节点时，不需要完整遍历整颗树。

上面的表示方法，每个节点最多包括两个引用节点（不计算父节点引用），实际上这样的表示方法，把复杂的多子节点的树，表示成了一颗简单的二叉树：

这种表示法将是以后最常用的方法，二叉树将是我们在以后用到的最多的树种之一。

3 总结

本文作为树这种数据结构的入门文章，详细讲解了树以及各种专业术语的定义和解释，然后讲解了树的通用实现，讲了父节点表示法、父子节点链表示法、父子兄弟表示法。实际上后面的特性化的数据结构比如二叉树、AVL树、红黑树，均有自己的表示方法。但是上面这几种方法作为树的通用实现，还是可以了解一下的。

最后提到了二叉树，二叉树将是我们在以后用到的最多的树种之一，内容非常繁多，在此不做介绍，本文作为树的入门文章，在后续的文章中，将慢慢介绍二叉树等特性化的树。

相关文章：

1. 《大话数据结构》
2. 《算法图解》
3. 《算法》

如果有什么不懂或者需要交流，可以留言。另外希望点赞、收藏、关注，我将不间断更新各种Java学习博客！