树的定义及基本术语

树(Tree):n(n >= 0)个结点构成的有限集合。当 n = 0 时,称为空树;对于任意一颗非空树(n > 0),它具备以下性质:

  • 树中有一个称为根(Root)的特殊结点,用 r 表示。
  • 其余结点可以分为 m(m > 0)个互不相交的有限集 T1, T2, … , Tm,其中每个集合本身又是一棵树,称为原来树的子树(subtree)

树的定义使用了递归的思想。注意:根据定义,子树之间不能相交,一颗树中不能出现环

下面是一颗树及其子树:

树与子树

根据树的定义,可以得出一些结论:

  1. 除了根结点外,每个结点有且仅有一个父结点。(根结点没有父结点)

  2. 一颗 N 个结点的树有 N - 1 条边。(因为除了根结点外,每个结点都有且仅有一条边与其父结点相连)

树的一些基本术语:

  1. 结点的度(Degree):一个结点的子树个数
  2. 树的度:树中所有结点的度的最大值。
  3. 叶结点(Leaf)度为 0 的结点(即没有子树的结点)。
  4. 路径与路径长度:从一个结点出发,到另一个结点经过的所有边构成一条路径,路径所包含的边的个数为路径的长度
  5. 父结点(Parent)、子结点(Child)兄弟结点(Sibling)祖先结点(Ancestor)子孙结点(Descendant)
  6. 结点的层次(Level):规定根结点在 1 层,其他任一结点的层数是其父结点的层数加 1。
  7. 树的深度(Depth):树中所有结点中的最大层次就是这棵树的深度。

树的表示

数组实现

由于树中每个结点的子结点数目无法确定(可能是 0 个,也可能是 n 个),树的结构很难判别,所以用数组实现是不切实际的。

后面要说到的二叉树可以用数组实现。

链表实现

看到树的结构,理所当然地会想到用链表来实现一棵树,如下图:

树的链表实现-不同指针数

结点用结构体或对象来表示,看起来似乎实现了,但有个问题是:无法确定某个结点有几个子结点,即需要在结构体中定义多少个指针。

针对这个问题,有一个解决方法:将每个结点都设计成一样的结构,比如全都设置成 A 结点那样的结构,也就是有三个指针,用不到的指针就让它指向空,比如 B 除了有两个指针指向它的子结点外,还有一个指针指向空。

但这样有一个前提:必须事先知道这棵树的度。且由于很多指针都指向空,会造成大量空间被浪费。

儿子-兄弟表示法

这种方法可以将一颗一般的树表示成一个结构上比较一致的树。

儿子兄弟表示法中的结点结构

每个结点统一只有两个指针,一个指向它的第一个子结点,另一个指向它的兄弟结点。

下图是将一棵树用 儿子-兄弟表示法 表示的结果:

儿子兄弟表示法

将表示结果顺时针旋转 45°:

旋转45°

可以发现这也是一棵树,每个结点最多只有两个子结点,这种树叫做二叉树

不管多么复杂的树,都可以用 儿子-兄弟表示法 将其转换为一颗二叉树。所以研究二叉树是很重要的。

二叉树的定义、性质及存储

二叉树的定义

二叉树:一个有穷的结点集合。

  • 这个集合可以为
  • 若不为空,则它是由根结点和称为其左子树右子树的两个不相交的二叉树组成。

二叉树与“度为 2 的树”的区别是:二叉树的子树有左右之分

二叉树有五种基本形态:

二叉树的五种基本形态

几种特殊的二叉树

  1. 斜二叉树:

    这种二叉树的每个结点要么都只有左孩子,要么都只有右孩子,也就是往一边到。其实就相当于一个链表。

    斜二叉树
  2. 满二叉树(也叫 完美二叉树):

    如果一棵二叉树的任何结点,要么是树叶,要么左右子树都非空,那么这棵二叉树就叫做满二叉树。

    满二叉树
  3. 完全二叉树

    如果一棵二叉树最多只有最下面的两层结点度数可以小于 2,并且最下面一层的结点都集中在该层最左边的连续位置上,则此二叉树称作完全二叉树。

    完全二叉树是一种很重要的二叉树,很多数据结构和算法都建立在这种二叉树的基础上。

    完全二叉树

二叉树的几个重要性质

  1. 二叉树第 $i$ 层(根结点的层数为 1)的最大结点数为:$2^{i-1}, i \ge 1$

  2. 深度为 $k$ 的二叉树的最大结点总数为:$2^k-1, k \ge 1$

    推导:第 1 层的结点数为 $2^{1-1}=1$,第二层为 $2^{2-1}=2$,以此类推,最后将所有结点数加起来,$1+2^1+2^2+ \dots +2^{k-1}$,这是一个等比数列求和,它的结果就是 $2^k-1$。

  3. 对任何非空二叉树,若 $n_0$ 表示叶结点的个数,$n_2$ 表示度为 2 的结点的个数,那么两者满足关系 $n_0=n_2+1$。

    如下图中,叶结点有 D、J、K、H 共四个,即 $n_0=4$,而度为 2 的结点有 A、B、E 共三个,即 $n_2=3$,满足前面所述的关系。

    一颗普通的二叉树

    结论的推导:

    设 $n_1$ 表示度为 1 的结点的个数,也就是说 $n_0+n_1+n_2$ 就是总结点数。

    从下往上看,除了根结点外,其他每个结点都有一条向上的边,所以边的总数为 $n_0+n_1+n_2-1$

    再从上往下看,每个结点都有 0 条或 1 条或 2 条边,这些边的总数为 $0 \times n_0 + 1 \times n_1 + 2 \times n_2$

    列方程 $n_0+n_1+n_2-1 = 0 \times n_0 + 1 \times n_1 + 2 \times n_2$,即可推出上面的结论。

二叉树的存储

  1. 数组存储

    完全二叉树可以很方便地用数组存储。将结点按从上到下,从左到右的顺序按顺序存入数组即可:

    数组存储完全二叉树

    这样存储后,可以通过计算的方式算出某个结点的子结点、父结点:

    假设某个非根结点的序号为 $i$,结点总数为 $n$,则:

    • 其父结点的序号为 $\lfloor i \div 2 \rfloor$
    • 其左子结点的序号为 $2i$。(如果 $2i \le n$,则没有左子结点)
    • 其右子结点的序号为 $2i+1$。(如果 $2i + 1 \le n$,则没有右子结点)

    如果是一般的二叉树,可以先将其补充成一棵完全二叉树,再用数组存储:

    数组存储一般二叉树

    可以很明显地看出,这种存储方式会造成空间上的浪费。

  2. 链表存储

    链表存储显然是可行的,因为二叉树的度为 2,每个结点只需要两个指针。

    结点的定义:

    1
    2
    3
    4
    5
    6
    typedef struct TreeNode* BinTree;
    struct TreeNode {
    ElementType data; // 数据域
    BinTree left; // 指向左孩子
    BinTree right; // 指向右孩子
    }
    链表存储二叉树

二叉树的遍历

深度优先遍历(递归)

先序遍历:

1
2
3
4
5
6
7
void preOrderTraversal(BinTree bt) {
if (bt) {
visit(bt->data);
preOrderTraversal(bt->left);
preOrderTraversal(bt->right);
}
}

中序遍历和后序遍历只是 visit() 放的位置不一样。

深度优先遍历(非递归)

广度优先遍历

二叉搜索树

平衡二叉树