树型结构是一类重要的是非线性数据结构。其中以树和二叉树最为常用，树是以分支关系定义的层次结构。树结构在客观世界中广泛存在，比如人类社会的族谱可以用树来形象地表示。计算机领域，在编译程序中，可以用树来表示源程序的语法结构。在数据库系统中，树型结构也是数据的组织形式之一。

一、树的定义和基本术语

树是 n(n>=0) 个结点的有限集。在任意一棵非空树中：

  • 有且仅有一个特定的结点，称为根
  • 当 n>1 时，其余结点可分为 m(m>0) 个互不相交的有限集 T1,T2,…,Tm，其中每一个集合本身又是一棵树，并且称为根的子树

树可以有多种定义方式，定义树的一种自然方式是通过递归定义（还包括嵌套结合、广义表、凹入表示法）。一棵树是一些节点的集合。

树的结点包含一个数据元素及若干个指向其子树的分支。

结点拥有的子树数量称为度（Degree），度为 0 的结点称为叶子（Leaf）或终端结点。度不为 0 的结点称为非终端结点或分支结点。树的度是树内各个结点的度的最大值。

结点的子树的根称为该结点的孩子（Child），相应的，该结点称为孩子的双亲（Parent）。同一个双亲的孩子之间互称兄弟（Sibling）。结点的祖先是从根到该结点所经分支上的所有结点。反之，以某结点为根的子树中的任一结点都成为该结点的子孙。

结点的层次（Level）从根开始定义起，根为第一层，根的孩子为第二层。其双亲结点在同一层的结点们互称为堂兄弟。树中结点的最大层次称为树的深度（Depth）或高度。

如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。在有序树中最左边的子树个根称为第一个孩子，最右边的孩子称为最后一个孩子。

森林是 m(m>=0) 棵互不相交的树的集合。对树中的每个节点而言，其子树的集合即为森林。

二、二叉树

1、二叉树的定义

二叉树（Binary Tree）是另一种树型结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于 2 的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒。

2、二叉树的性质

二叉树的一个重要的性质是一棵平均二叉树的深度要比节点个数 N 小得多，这个性质有时很重要，平均深度为 O(sqrt(N)) 。对于特殊类型的二叉树，如二叉查找树，深度的平均值为 O(log N)，但最大深度可以达到 N-1

性质一：在二叉树的第 i 层上至多有 2i-1 个结点 (i>=1)

性质二：深度为 k 的二叉树至多有2k-1 个结点 (k>=1)

性质三：对任意一棵二叉树 T，如果其终端节点数为 n0，度为 2 的节点数为 n2，则 n0=n2+1

设二叉树中度为 1 的节点为 n1，则总结点数 n=n0+n1+n2；除了根节点外每一个节点都有一个来自父节点的边与其相连，所以设总边数为 B，n=B+1，B=n1+2n2；则 n=n1+2n2+1；最后计算出 n0=n2+1

性质四：具有 n 个结点的完全二叉树的深度为 ⌊log2n⌋ + 1

  • 满二叉树：一棵深度为 k 且有 2k-1 个结点的二叉树，这种树的特点是每一层上的结点数都是最大结点数
  • 完全二叉树：对满二叉树的节点进行连续编号，约定编号从根节点起，自上而下，自左至右。引出完全二叉树的定义：深度为 k 的，有 n 个节点的二叉树，当且仅当其每一个节点都与深度为 k 的满二叉树中编号从 1 至 n 的节点一一对应，称为完全二叉树，这种树的特点是：
    • 叶子节点只可能在层次最大的两层出现
    • 对任一节点，若其右分支下的子孙的最大层次为 d，则其左分支下的子孙的最大层次为 d 或者 d+1。也就是说，不可能出现某一结点有右孩子但是没有左孩子的情况

性质五：如果对一棵有 n 个结点的完全二叉树的结点按层序编号，则对任一结点 i(1<=i<=n)，有

  • 如果 i=1，则结点 i 是二叉树的根，无双亲；如果 i>1，则其双亲是结点 ⌊i/2⌋
  • 如果 2i>n，则结点 i 无左孩子（结点 i 为叶子结点）；否则其左孩子是结点 2i
  • 如果 2i+1>n，则结点 i 无右孩子；否则其右孩子是结点 2i+1

3、二叉树的存储结构

3.1 顺序存储结构

按照顺序存储结构的定义，用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为 i 的结点元素存储在一维数组下标为 i-1 的分量中。例如下面节点存储数字的二叉树示例：

  • 完全二叉树：{1, 2, 3, 4, 5, 6, 7, 8, 9}
  • 一般二叉树：{1, 2, 3, 4, 5, 0, 0, 0, 0, 6, 7}

这种存储结构仅适用于完全二叉树。因为在最坏的情况下，一个深度为 k 且只有 k 个结点的单支树（树中不存在度为 2 的结点）却需要长度为 2k-1 的一维数组。

3.2 链式存储结构

二叉树的链式存储结构中，结点至少应包括 3 个域：数据域和左、右指针域。有时为了便于找到结点的双亲，则还可以在结点结构中增加一个指向其双亲结点的指针域。这两种结点结构所得二叉树的存储结构分别称之为二叉链表和三叉链表。

根据二叉树的性质得出，在含有 n 个结点的二叉链表中有 n+1 个空链域（有 2n 个链域），可以利用这些空链域存储其他有用的信息，从而得到另一种存储结构——线索链表。

4、遍历二叉树

二叉树由根节点、左子树、右子树组成，假设以L、D、R分别表示遍历左子树，遍历根节点，遍历右子树，则在限定顺序的情况下，有三种情况：

  • 先序（根）遍历 DLR
  • 中序（根）遍历 LDR
  • 后序（根）遍历 LRD

二叉树的先序遍历对节点的处理工作是在它的所有儿子节点被处理之前进行的，二叉树的后序遍历对节点的处理工作是在它的所有儿子节点被处理之后进行的。二叉树有中序遍历，而树没有中序遍历，因为二叉树的孩子节点数量是固定的，即只有两个。

二叉树示例图如下：

上面的二叉树三种遍历顺序如下：

  • 先序遍历，12, 10, 5, 15, 13, 20
  • 中序遍历，5, 10, 12, 13, 15, 20
  • 后序遍历，5, 10, 13, 20, 15, 12

三种遍历方法都可以以递归算法编写出程序，递归算法简单易懂结构清晰，但因为要不断分配栈空间，所以在内存空间上有所浪费。

4.1 中序遍历中的前驱节点和后继节点

在二叉树中，前驱节点和后继节点的概念与中序遍历紧密相关。具体来说，它们分别是某个节点在中序遍历序列中前面和后面的节点。

后继节点

某节点的后继节点是中序遍历中紧接在该节点之后的那个节点。换句话说，它是二叉搜索树中比该节点稍大的那个节点。

寻找后继节点的规则：

  • 如果节点有右子树：后继节点是右子树中的最左节点。比如在一棵二叉搜索树中，如果你在某个节点上向右走，那么后继节点就是右子树中最左边的那个节点。
  • 如果节点没有右子树：从该节点往上找，直到找到一个节点，该节点是其父节点的左子树，这个父节点就是后继节点。

上图的示例中：

  • 节点 10 的后继节点是 12，因为 12 是比 10 大的最小节点。
  • 节点 12 的后继节点是 13，因为 13 是 12 的右子树中的最左节点。
  • 节点 15 的后继节点是 20，因为 20 是 15 的右子树中的最左节点。
前驱节点

某节点的前驱节点是中序遍历中紧接在该节点之前的那个节点。换句话说，它是二叉搜索树中比该节点稍小的那个节点。

寻找前驱节点的规则：

  • 如果节点有左子树：前驱节点是左子树中的最右节点。类似地，如果你在某个节点上向左走，那么前驱节点就是左子树中最右边的那个节点。
  • 如果节点没有左子树：从该节点往上找，直到找到一个节点，该节点是其父节点的右子树，这个父节点就是前驱节点。

上图的示例中：

  • 节点 10 的前驱节点是 5，因为 5 是 10 的左子树中的最右节点（也是唯一节点）。
  • 节点 12 的前驱节点是 10，因为 10 是比 12 小的最大节点。
  • 节点 15 的前驱节点是 13，因为 13 是 15 的左子树中的最右节点。

4.2

。。。递归程序待复制。。。

依照递归算法执行过程中递归工作栈的状态变化情况可直接写出相应的非递归算法。

从中序遍历递归算法执行过程中递归工作栈的状态可见：

  • 工作记录中包含两项，其一是递归调用的语句编号；其二是指向根节点的指针，则当栈顶记录中的指针非空时，应遍历左子树，即指向左子树根的指针进栈
  • 若栈顶记录中的指针为空，则应退至上一层，若从左子树返回，则应访问当前层即栈顶记录中指针所指的根节点；若是从右子树返回，则表明当前层的遍历结束，应继续退栈。
  • 从另一角度看，这意味着遍历右子树时不在需要保存当前层的根指针，可直接修改栈顶记录中的指针即可。

5、线索二叉树

遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列，得到二叉树中结点的先序序列或中序序列或后序序列。这实际上是对一个非线性结构进行线性化操作，使每个结点（除第一个和最后一个外）在这些线性序列中有且仅有一个直接前驱和直接后继。

但是在以二叉链表作为数据结构时，只能找到结点的左、右孩子信息，而不能直接得到结点在任一序列中的前驱和后继信息，这种信息只有在遍历的动态过程中才能得到。

相关链接

OB tags

#数据结构 #二叉树