在计算机科学中,树(英语:tree)是一种抽象数据类型(ADT)或是实现这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:

  • 每个节点都只有有限个子节点或无子节点;
  • 没有父节点的节点称为根节点;
  • 每一个非根节点有且只有一个父节点;
  • 除了根节点外,每个子节点可以分为多个不相交的子树;
  • 树里面没有环路(cycle)

线性结构中结点具有唯一前趋和唯一后继的关系,而非线性结构中结点之间的关系不再具有这种唯一性。其中,树形结构中结点间的关系是前趋唯一而后继不唯一,即元素之间是一对多的关系;

树(Tree)是n(n≥0)个结点的有限集合。当n=0时,称这棵树为空树;当n>0时,该集合满足以下条件:

(1)有且只有一个特殊的结点称为树的根(root),根结点没有直接前趋结点,但有零个或多个直接后继结点(这里的前趋、后继暂时沿用线性表中的概念,在树中,前趋、后继其实是另外的术语)。
(2)除根结点之外的其余n-1个结点被分成m(m>0)个互不相交的集合T1, T2, …, Tm,其中每一个集合Ti(1≤i≤m)本身又是一棵树。树T1, T2, …, Tm称为根结点的子树。

可以看出,在树的定义中用了递归概念,即用树来定义树。因此,树形结构的算法也常常使用递归方法。

相关术语:

  • 结点:包含一个数据元素及若干指向其他结点的分支信息的数据结构。
  • 结点的度:结点所拥有的子树的个数称为该结点的度。
  • 叶子结点:度为0的结点称为叶子结点,或者称为终端结点。
  • 树的深度(高度):树中所有结点的层次的最大数称为树的深度。

有几个相似的概念(来自极客时间的数据结构与算法之美)

节点的高度 = 节点到叶子节点的最长路径(边数)
节点的深度 = 根节点到这个节点所经历的边的个数
节点的层数 = 节点的深度 + 1
树的高度 = 根节点的高度


                          高度     深度     层

            6         =>   3        0       1
          /   \
        4       8     =>   2        1       2
       / \     /  \
      3   5   7    9  =>   1        2       3
     / \          / 
    1   2        8    =>   0        3       4 

在计算机科学中,二叉树(英语:Binary tree)是每个节点最多只有两个分支(即不存在分支度大于2的节点)的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序,不能随意颠倒。

二叉树中,有两种比较特殊的树,分别是满二叉树和完全二叉树。满二叉树又是完全二叉树的一种特殊情况。

满二叉树,除最后一层结点均无任何子节点外,每一层的所有结点都有两个子结点的树。

在一颗二叉树中,若除最后一层外的其余层都是满的,并且最后一层要么是满的,要么在右边缺少连续若干节点,则此二叉树为完全二叉树(Complete Binary Tree)。具有n个节点的完全二叉树的深度 log_2n+1。深度为k的完全二叉树,至少有2 ^ k + 1 个节点,至多有2 ^ k - 1 个节点。

二叉查找树(英语:Binary Search Tree),也称为二叉搜索树、有序二叉树(ordered binary tree)或排序二叉树(sorted binary tree),是指一棵空树或者具有下列性质的二叉树:

  • 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
  • 若任意节点的右子树不空,则右子树上所有节点的值均大于或等于它的根节点的值;
  • 任意节点的左、右子树也分别为二叉查找树;

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为O(log n)。二叉查找树是基础性数据结构,用于构建更为抽象的数据结构,如集合、多重集、关联数组等。

Reference