什么是树

这都不用解释了吧，树是很常见的数据结构，其定义也是递归定义的，不再赘述。

树的表现形式

树除了其树状结构的表示（这里指的是常规的表示，如下图(d)）之外还有另外三种：

嵌套集合：即是一些集合的集体，集合只有嵌套关系，其中的任意两个集合都不相交。如下图(a)；
广义表：根作为由子树森林组成的表的名字写在标的左边。如下图(c)；
凹入表示法：类似书的编目，或者如本博客的目录。如下图(b)；

树的一些概念

树很常用，但是树的有些概念不是太常用，这里就总结了一些不常用或者容易模糊的概念（是我自己记不住，如果你很清楚的话，请直接跳过）。

结点的度：结点拥有的子树数
叶子结点/终端结点：度为零的结点
非终端结点/分支结点/内部结点：度不为零的结点
树的度：树内各结点的度的最大值
孩子（Child）、双亲（Parent）、兄弟（Sibling）：略
祖先：从根到该结点所经分支上的所有结点
子孙：以某结点为根的子树中的任一节点
层次（Level）：从根开始，根为第一层，根的孩子为第二层。若某节点在第l层，则其子树的根就在第l+1层
堂兄弟：其双亲在同一层的结点互为堂兄弟
深度（Depth）/高度：树中结点的最大层次
有序树/无序树：如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。
森林（Forest）：m (m>=0)棵互不相交的树的集合

树和森林的递归定义：就逻辑结构而言，任何一棵树是一个二元组Tree = (root, F)，其中：root是数据元素，称作树的根结点；F是m(m >= 0)棵树的森林，F=(T1, T2, ... ,Tm)，其中Ti=(ri, Fi)称作根root的第i棵子树；当m!=0时，在树根和其子树森林之间存在下列关系： RF = { < root, ri > | i = 1, 2, ... , m, m>0 } 这个定义将有助于得到森林和树与二叉树之间转换的递归定义。

二叉树

二叉树是最常用的树，定义略。

满二叉树和完全二叉树

满二叉树：顾名思义，略。
完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。（不同书籍对于这个概念会有不同的解释，可能会有差别）特点：
1. 叶子结点至可能出现在层次最大的两层上
2. 对任一结点，若其右分支下的子孙的最大层次为l，则其左分支下的子孙的最大层次必为l或l+1

二叉树的性质

这些也都是很容易得到的结论，不证明只给性质描述：

在二叉树的第i层上至多有2^(i-1)个结点（i>=1）
深度为k的二叉树至多有2^k - 1个结点（k>=1）
任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2 + 1（这个得好好想想，根据结点的度和结点的链接数，好好画画推推就明白了）
具有n个结点的完全二叉树的深度为⌊log2(n)⌋+1
如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第⌊log2(n)⌋+1层，每层从左至右），则对任一结点i（1<=i<=n），有：
如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲PARENT(i)是结点⌊i/2⌋
如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子LCHILD(i)是结点2i
如果2i+1>n，则结点i无右孩子；否则其右孩子RCHILD(i)是结点2i+1

二叉树的存储结构

两种存储结构都是非常常见的存储方式：

顺序存储结构：数组存，仅适用于完全二叉树
链式存储结构：链表存

遍历二叉树

遍历二叉树有多种方式，为了方便定义了三种遍历方式，三种遍历的顺序都是相当于根结点来说的：

先序遍历
中序遍历
后序遍历

代码就不用给了吧，这应该都会吧。 遍历的操作实质是对非线性的数据结构树，进行线性化操作。

线索二叉树

前一节写道：遍历其实是将二叉树线性化，遍历得到的序列，对于某一结点的前驱结点信息和后继结点信息都没法保存；为了保存这些信息自然会想到一种方式：

在每个结点上增加两个指针域来分别指示结点的前驱结点信息和后继结点信息

但是这种方式会造成存储密度大大降低，而在n个结点的二叉链表中必定存在着n+1个空链域（可以这么理解：n个结点的所有链域数为2n，被占用的个数为n-1，则空链域数为n+1；还可以按照二叉树调整过程中的旋转来理解，先把树按照全部是左子结点排列，显然空链域为n+1，然后旋转调整为当前树形，显然，旋转不会改变空链域的个数），由此设想用这些空链域来存放结点的前驱和后继信息：

作如下规定：若结点有左子树，则其lchild域指示其左孩子，否则令lchild域指示其前驱；若结点有右子树，则其 rchild域指示其右孩子，否则令rchild域指示其后继。为了避免与原树结构混淆，还得增加两个标志域：LTag和RTag。当两个标志域分别为0时，分别表示它们对应的lchild和rchild分别表示对应的左孩子和右孩子；当两个标志域分别为1时，分别表示它们对应的lchild和rchild分别表示对应的前驱信息和后继信息。

以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱和后继的指针，叫做线索；加上线索的二叉树称之为线索二叉树（Threaded Binary Tree）。对二叉树以某种次序遍历使得其变为线索二叉树的过程叫做线索化。

线索树建立的目的就是为了不让树在遍历的时候回溯，所以在线索树上进行遍历只需要找到序列中的第一个结点，即可依次找到结点后继直至其后继为空为止。由此很容易看到：

前序线索树：根结点是最先遍历的，非终端结点肯定都是在最前面，这时后继线索只会在子树上建立，线索不会断
中序线索树：根结点在中间遍历，把树线性化的话，非终端结点是间隔排开的，总有叶子结点指向它们，线索不会断
后序线索树：根结点在最后遍历，可见，所有的非终端结点会排在树的线性化序列的后面，中间某一个非终端结点如果同时有左孩子和右孩子的话，就会没有空链域来存储线索信息，所以就需要额外添加一个链域来存储线索信息，因此后序线索树需要带标志域的三叉链表作存储结构。

这一部分的理解也是非常简单的，只需要自己动手画画图就很快理解了。

从原理上看也是非常简单的，不过，为了方便起见，仿照线性表的存储结构，在二叉树的线索链表上也添加一个头结点，并令其lchild域的指针指向二叉树的根结点，其rchild域的指针指向中序遍历时访问的最后一个结点；并且令二叉树中序序列中的第一个结点的lchild域指针和最后一个结点的rchild域的指针均指向头结点。这好比为二叉树建立了一个双向线索链表。下面给上代码：

//二叉树的二叉线索存储表示
typedef enum PointerTag  { Link, Thread };    //Link == 0：指针，Thread == 1：线索
typedef struct BithrNode  {
  TElemType    data;
  struct BiThrNode    *lchild, *rchild;    //左右孩子指针
  PointerTag    LTag, RTag;    //左右标志
}  BiThrNode, *BiThrTree;
//中序遍历建立中序线索化链表
Status InOrderThreading( BiThrTree &Thrt, BiThrTree T) {
  //中序遍历二叉树T，并将其中序线索化，Thrt指向头结点
  if( !(Thrt = (BiThrTree)malloc(sizeof(BiThrNode))))    exit(OVERFLOW);
  Thrt->LTag = Link;
  Thrt->RTag = Thread;    //建立头结点
  Thrt->rchild = Thrt;    //右指针回指
  if( !T )    Thrt->lchild = Thrt;
  else {
      Thrt->lchild = T;
      pre = Thrt;
      InThreading(T);    //中序遍历进行中序线索化
      pre->rchild = Thrt;
      pre->RTag = Thread;    //最后一个结点线索化
      Thrt->rchild = pre;
  }
  return OK;
}
void InThreading(BiThrTree p) {
  if( p ) {
      InThreading(p->lchild);    //左子树线索化
      if( !p->lchild ) {
          p->LTag = Thread;
          p->lchild = pre;
      }    //前驱线索
      if( !pre->rchild ) {
          pre->RTag = Thread;
          pre->rchild = p;
      }    //后继线索
      pre = p;
      InThreading( p->rchild );    //右子树线索化
  }
}
//二叉线索树遍历
Status InOrderTraverse_Thr(BiThrTree T, Status (*Visit)(TElemType e) ) {
  //T指向头结点，头结点的左链lchild指向根结点
  //中序遍历二叉线索树T的非递归算法，对每个数据元素调用函数Visit
  p = T->lchild;    //p指向根结点
  while ( p!= T ) {    //空树或遍历结束时， p==T
      while( p->LTag == Link )    p = p->lchild;
      if( !Visit(p->data) )    return ERROR;    //访问其左子树为空的结点
      while ( p->RTag == Thread && p->rchild != T) {
          p = p->rchild;
          Visit( p->data );    //访问后继结点
      }
      p = p->rchild;
  }
  return OK;
}

代码很容易看懂，我就不解释了。

树和森林

这一节没有什么可写的，主要还都是对二叉树的操作，只不过概念不一样而已。

树的存储结构

一些存储结构：

双亲表示法：不保存结点的子结点信息，只保存结点的双亲结点信息
孩子表示法：不保存结点的双亲结点信息，只保存结点的孩子结点信息
孩子兄弟表示法：又称二叉树表示法，或二叉链表表示法。

上面三种表示方法都是很常见的表示方法，前两种不常用，第三种最常用。

森林、树与二叉树

一棵树对应的二叉树（用左子结点表示孩子结点链，用右子结点表示兄弟结点链）的右子树必是空的。则森林对应的二叉树则右子树不必为空。

树和森林的遍历

两种方式，都是从字面就能理解的：

先根序：对应先序遍历
后根序：对应中序遍历

根据森林和树的对应关系以及它们对应的二叉树的表示，可有两种对应的遍历方式：

先序遍历森林
中序遍历森林

这种对应关系也是很容易就能想到的，不明白在纸上画画就明白了。造成这种现象的原因实在树或森林转换成二叉树时，树或森林的子结点都变成了左子树，而兄弟结点变成了右子树。

总结自：《数据结构（C语言版）》清华大学出版社严蔚敏、吴伟民编著