一、广义表

广义表是线性表的进一步推广，它是由n（n≥0）个数据元素组成的有序序列。线性表中的数据元素只能是单个元素，它是不可分割的，而广义表中的数据元素既可以是单个元素，也可以是一个广义表，广义表通过圆括号“()”括起来，通过逗号“,”隔开表中的数据元素，广义表是可以递归的，一个广义表也可以是其自身的子表，广义表中的第一个元素称为广义表的表头，而剩余数据元素组成的表称为广义表的表尾。

例如B=(a,b,c)，A=(B,d,e），即A=((a,b,c),d,e），广义表A的表头是(a,b,c)，表尾是(d,e)；

例如C=(a,b,c,d,e,f,g)，该广义表的表头是(a)，表尾是(b,c,d,e,f,g)；

例如D=((a,b),((c,d,e),(f,g,h)))，该广义表的表头是(a,b)，表尾是((c,d,e),(f,g,h))。

二、树和森林

（一）树的概念

树是一种非线性结构，它是树形结构，含有n个有限元素的数据元素集合（其中n≥0，n=0时为空树），线性结构中的数据元素之间是“一对一”的关系，而树形结构中的数据元素之间是“一对多”的关系。

树（n>0）满足两个条件，一个树有且只有一个根结点，其中根结点没有前驱结点，除了根结点其他所有结点都只有一个前驱结点；剩下的结点为m(m≥0)个互不相交的非空集合，其中每个集合又可以称为一棵树，即根的子树。

树中两个结点之间的路径由两个结点间所经过的序列构成，路径长度是路径上所经过的边的个数，而树的路径长度是指根结点到每个结点的路径长的总和。

另外，由m（m≥0）棵互不相交的树的集合称为森林。

（二）结点

叶子结点、孩子结点、双亲结点、兄弟结点：

1、叶子结点也称为终端结点，它是没有子结点的结点（度为0），例如上图中，D、E、F、G都是叶子结点；

2、一个结点的后继结点称为该结点的孩子结点，例如上图中，A的孩子结点是B、C；

3、一个结点称为其后继结点的双亲结点，例如上图中，B、C的双亲结点是A，D、E的双亲结点是B；

4、在同一双亲结点下的孩子结点互为兄弟结点，例如上图中，B、C互为兄弟结点，它们有共同的双亲A，另外D、E互为兄弟结点，它们有共同的双亲B。

（三）树的性质

1、树中结点的子结点（孩子）个数称为该结点的度，而树中结点的最大度数称为树的度，例如上图这个树中，结点B有两个子结点D和E，所以结点B的度为2，结点D的度为0，树的度为2。

✨树中结点的个数等于所有结点的度数之和加1。

例如，上图的结点的个数为N=（2+2+2）+1=7。

✨另外，树中结点的个数也等于总分支数加1，其中总分支数=1n1+2n2+3n3+…+mnm（度为m的结点引出m条分支）。

例如，上图树中，总分支数为6，故结点个数为6+1=7。

2、树中结点的最大层数为树的高度（深度），结点的深度是由树的根结点开始由上至下，而结点的高度是由树的叶子结点开始由下至上的。

✨度为m的树中第i层上（i≥1），至多有mi-1个结点。

例如，上图中树的度为2，m=2，第3层上（i=3）上至多有mi-1=22=4个结点。

三、二叉树

（一）二叉树的概念

二叉树是一种逻辑结构，它是一种特殊的树，与普通的树相比，普通树中结点的后继结点可以是任意多个，而二叉树中结点的后继结点最多只能有两个，另外有两种特殊的二叉树，满二叉树和完全二叉树，满二叉树是完全二叉树的特例，可以说若一棵树是满二叉树，则它必是完全二叉树，但不能说一个完全二叉树必是满二叉树。

完全二叉树中，叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。

二叉树也是含有n个有限元素的数据元素集合（其中n≥0，n=0时为空二叉树），由一个根结点以及两个不相交的非空树，分别称为左子树和右子树组成，二叉树是一个特殊的有序树（其中结点的各子树从左到右有序），其中左右子树的次序不能任意交换，同样，左子树和右子树也是二叉树。

另外，完全二叉树的另一种定义是，若对深度为h，结点数为n个的二叉树进行编号后，各结点的编号与深度为h的满二叉树中相同位置结点上对应的编号均相同时，则这种二叉树为完全二叉树。

满二叉树：

完全二叉树：

若对一个二叉树进行编号（由编号为1的根结点开始），按照二叉树的层次数，从上到下，从左到右的顺序依次对树中每一个结点进行编号，我们可以得到性质如下：

✨当一个结点的双亲结点的编号为i时（i>1），若它是该双亲的左孩子结点，则编号为2i，若是右孩子结点，则编号为2i+1，即当i为偶数时，结点i的双亲编号为i/2，该结点是双亲的左孩子结点，当i为奇数时，结点i的双亲编号为（i-1）/2，该结点是双亲的右孩子结点。

✨当2i≤n时（n为最后一个结点的编号），结点i的左孩子编号为2i，否则无左孩子；当2i+1≤n时，结点i的右孩子编号为2i+1，否则无右孩子。

例如，B是D、E的双亲结点，即它是D、E的双亲，结点D的编号为4，为偶数，说明它是双亲B的左孩子结点，结点E的编号为5，为奇数，它是双亲B的右孩子结点：

（二）二叉树的性质

✨二叉树中，设度为0、1和2的结点个数分别为n0、n1和n2，即结点总数N=n0+n1+n2。

✨二叉树中，叶子结点数等于度为2的结点数加1，设度为0、2的结点的个数为n0、n2，即n0=n2+1。

例如，下图完全二叉树中，可以验证一下，度为2的结点个数为4，所以度为0的结点（叶子结点）个数为n0=4+1=5。

✨二叉树中，分支总数=N-1=n1+2n2。

例如，下图完全二叉树中，分支总数等于9-1=8，或者等于度为1的结点个数加上两倍度为2的结点个数，即n1+2n2=0+2×4=8。

✨二叉树中，第i层上至多有2i-1（i≥1）个结点，这种即为满二叉树的情况。

例如，在一棵二叉树中，第四层至多有24-1=23=8个结点。

✨高度为h的二叉树至多有2h-1个结点，另外高度为h的m叉树中，至多有（mh-1）/（m-1）个结点。

例如下图是一个二叉树，其高度（深度）为4，h=4，即至多有24-1=15个结点，这个二叉树并不是一个满二叉树，而是一个完全二叉树。

✨对于n个结点，可以组成N种不同的二叉树，如下：

例如，由3个结点A、B、C构成的二叉树，可以有

如下：

（三）满二叉树的性质

✨一棵有n个结点的满二叉树，含有（n+1）/2个叶子结点，含有（n-1）/2个分支结点，其高度为h=log2(n+1)。

推导过程：由于是满二叉树，所以度为1的结点为0，即n1=0，由于二叉树的性质n0=n2+1以及n=n0+n1+n2，可得n=2n0-1，所以叶子结点n0=（n+1）/2；

由于分支总数=n-1=n1+2n2，且n0=n2+1、n1=0，所以分支总数=2n2=n0-1=（n-1）/2；

高度为h的满二叉树的结点数为1+2+4+……+2h-1=2h-1（首项为1，公比为2的等比数列），即n=Sn=[a1(1-qn)]/1-q=2h-1，从中解出h，高度为h=log2(n+1)。

（四）完全二叉树的性质

✨由于完全二叉树的结点排法，可知叶子结点尽可能地往左边排，故度为1的结点个数只有一个或零个。

例如，已知一棵完全二叉树的第6层有8个叶子结点，求该完全二叉树的最多和最少结点数。由于第6层有叶子结点，所以完全二叉树的高度可能为6或7，当为6时，完全二叉树拥有最少结点数，由于前5层都为满二叉树，即1+2+4+8+16+8=31+8+39；当为7时，前6层都为满二叉树，其中有8个结点没有左右结点，即1+2+4+8+16+32+(32-8)×2=63+48=111，故该完全二叉树的最多和最少结点数分别为39和111。

✨一棵含有n个结点的完全二叉树中，叶子结点个数等于n/2【n为偶数】或（n+1）/2【n为奇数】。

例如，已知一棵完全二叉树有1001个结点，所以其叶子结点个数就等于（1001+1）/2=501个。

例如，已知一棵完全二叉树具有124个叶子结点，求其最多和最少结点数。当结点数n为偶数时，结点数最大，124=n/2，解得n=248，n为奇数时，结点数最小，124=（n+1）/2，解得n=247，故最多和最少结点数为248和247。

另一种解法是，根据n0=n2+1可知，n0=124，n2=123，由于N=n0+n1+n2，且该树为完全二叉树，根据完全二叉树的性质，度为1的结点个数只有一个或零个，即N=124+1+123=248和N=124+0+123=247，所以最多和最少结点数为248和247。

✨在完全二叉树中，编号为i（i≥1）的结点所在的层次为⌊log2i⌋+1。

✨对于一棵含有n个结点的二叉树，当它为完全二叉树时，具有最小高度，最小高度为h=⌈log2(n+1)⌉或⌊log2n⌋+1（其中 ⌈ ⌉表示向上取整，取比自己大的最小整数，⌊ ⌋表示向下取整，取比自己小的最大整数）；当它为一棵单支树时具有最大高度，即为一个线性表。

例如，设一颗二叉树的结点个数为50，求其最小高度，我们知道当这棵树为完全二叉树时高度最小，n=50，即h=⌊log250⌋+1 =5+1=6，所以其最小高度为6。

例如，求一棵具有1025个结点的二叉树的高度，首先我们知道当二叉树为单支树时此时具有最大高度，即每层只有一个结点，最大高度为1025；另外，当二叉树为完全二叉树时高度最小，此时即最小高度为⌊log21025⌋+1=10+1=11，故该二叉树的高度为11~1025。

✨高度为h的完全二叉树最少有2h-1个结点，最多有2h-1个结点。

四、平衡二叉树

平衡二叉树的特点是其中任一结点的左右子树的深度之差都不超过1，如下是一个平衡二叉树和非平衡二叉树：

非平衡二叉树：

五、二叉树的存储结构

二叉树的存储结构分为顺序存储结构和链式存储结构。

（一）二叉树的顺序存储结构

1、二叉树的顺序存储结构通过使用一组地址连续的存储单元数组进行存储，其中根结点的编号设定为1，若结点的编号为i，则对应存储的一维数组下标为i-1，如下图：

若从数组下标array[0]开始存储二叉树，则上面的性质无法适用，即无法通过所给编号位置来计算出其孩子结点在数组中的位置，例如，结点C的编号i为3，2i=6≤7，该结点的左孩子编号为2i=6，即结点F，说明左孩子存在，但是在数组中结点F的存放位置array[5]并不是与编号相同。

2、但是顺序存储结构存在浪费情况，就是在最坏情况下，一个高度（深度）为h的单支二叉树需要占据2h-1个数组存储单元，虽然它只有h个结点，如下：

（二）二叉树的链式存储结构

二叉树的链式存储结构通过链表实现，一个二叉树链表结点由数据域和指针域组成，除了data数据域用于存放结点的信息外，每个结点含有两个指针，左指针域lchild和右指针域rchild，分别指向该结点的左孩子结点和右孩子结点，它们用于存放该结点左/右子树的地址，当左/右子树不存在，其指针域为空（“^”），如下图：

链式存储结构实现代码如下：

typedef struct BNode {
  int data;  //数据域
  struct BNode *lchild,*rchild;  //左孩子、右孩子指针
} BTree;

例如，下面这个树的链式表示如下：

我们可以得到一个结论：

✨在由n个结点组成的二叉链表中，含有n+1个空指针域，含有n-1个非空指针域。

例如，上图二叉树中，含有8个结点，它含有8+1=9个空指针域，含有8-1=7个非空指针域。

六、二叉树的遍历

二叉树的遍历是按某种规定的顺序来对访问树中的所有结点，且每个结点仅被访问一次，由于二叉树由根结点（D）、左子树（L）和右子树（R）组成，以下是二叉树的先、中、后以及层次遍历。

二叉树的先、中、后序遍历都可以通过递归算法实现，递归结束的条件是T==NULL，即当二叉树为空时，遍历结束。

（一）二叉树的先序遍历（DLR）

二叉树的先序遍历中，首先是根结点，遍历完根结点的左子树，然后再遍历完根结点的右子树，依次下去至所有结点都遍历到，例如上图二叉树，其先序遍历就是abefcgh。

（二）二叉树的中序遍历（LDR）

二叉树的中序遍历中，首先是遍历完根结点的左子树，然后是根结点，最后遍历完根结点的右子树，依次下去至所有结点都遍历到，例如上图二叉树，其中序遍历就是ebfagch。

例如，一个二叉树中，根据中序遍历可知，中序遍历序列的最后一个结点一定是从根结点开始沿着右子树走到最底的结点，若它为叶子结点，则先序遍历序列和中序遍历序列的最后一个结点都为该结点【如上图二叉树】；若不为叶子结点，它还有一个左子结点，则该左子结点是前序遍历序列的最后一个结点，如下树：

它的先序遍历序列为：ABDECF，中序遍历序列为：DBEAFC，由于中序遍历序列的最后一个结点一定是从根结点开始沿着右子树走到最底的结点，所以中序遍历序列的最后一个结点为C，且结点C并不是叶子结点，它还有一个左子结点F，所以该结点F为先序遍历序列的最后一个结点。

（三）二叉树的后序遍历（LRD）

二叉树的后序遍历中，首先是遍历完根结点的左子树，然后遍历完根结点的右子树，最后是根结点，依次下去至所有结点都遍历到，也就是从二叉树的底层往上层依次遍历，例如上图二叉树，其后序遍历就是efbghca。

在二叉树的前序遍历、中序遍历和后序遍历序列中，所有叶子结点的先后顺序是相同的。

若一棵二叉树为空树或只有根结点，则其先序遍历序列和后序遍历序列相同；若二叉树为单右支二叉树或孤立结点，则其先序遍历序列和中序遍历序列相同。

若一棵非空的二叉树只有一个叶子结点，或二叉树的高度等于结点个数，则其先序遍历序列和后序遍历序列相反。

（四）二叉树的层次遍历

层次遍历中，层次优先，当对一层的结点都遍历完后，遍历下一层，按照次序对每个结点的左、右孩子进行遍历，例如上图二叉树，其层次遍历就是abcefgh。

层次遍历二叉树中可以通过链式队列实现，首先二叉树的根结点入队，然后进入循环，循环条件为队列是否为空，若不为空，则当前队头结点出队，此时该结点被访问到，并将该结点的左、右孩子结点插入到队列的队尾。

七、二叉树的实现代码（链式存储）

（一）二叉树的定义

通过链式存储结构实现代码如下，其中包含数据域和两个指针：

#incldue<stdio.h>
/*二叉树的定义*/
typedef struct BNode {
  int data;  //数据域
  struct BNode *lchild,*rchild;  //左孩子、右孩子指针
} *BTree;

（二）二叉树的建立

创建一个二叉树，按二叉树的顺序（二叉树带空指针的顺序，空指针也算进去），即根结点、左子树、右子树的顺序依次输入结点的值【使用的顺序是先序序列】，若其中有空结点，用0表示，其中使用到递归的方法建立左右孩子结点，实现代码如下：

#include <malloc.h>
/*二叉树的建立*/
BTree CreateTree() {
  BTree T;
  char ch;
  scanf("%c",&ch);
  getchar();  //getchar()用于接收每次输入字符结点后的回车符，从而以便输入下一个字符结点
  if(ch=='0') //当为0时，将结点置空
  T=NULL;
  else {
  T=(BTree)malloc(sizeof(BTree)); //分配一个新的结点
  T->data=ch;
  printf("请输入%c结点的左孩子结点：",T->data);
  T->lchild=CreateTree();  //通过递归建立左孩子结点
  printf("请输入%c结点的右孩子结点：",T->data);
  T->rchild=CreateTree();  //通过递归建立右孩子结点
  }
  return T;
}

（三）广义表输出二叉树

通过广义表来显示建立的二叉树，一个非空的二叉树T，当对于左孩子结点或右孩子结点时，此时输出一个左括号“(”，递归处理左子树，输出一个“,”用于隔开结点，然后递归处理右子树，输出一个右括号“)”，从而完成一个根结点以下的两个左/右结点处理。

/*广义表输出二叉树*/
void ShowTree(BTree T) {
  if(T!=NULL) {
  //当二叉树不为空时
  printf("%c",T->data); //输入出该结点的数据域
  if(T->lchild!=NULL) {  //若该结点的左子树不为空
    printf("(");  //输出一个左括号
    ShowTree(T->lchild);  //通过递归继续输出结点的左子树结点下的各结点
    if(T->rchild!=NULL) { //若该结点右子树不为空
    printf(",");  //输出一个逗号
    ShowTree(T->rchild);  //通过递归继续输出结点的右子树结点下的各结点
    }
    printf(")");  //输出一个右括号
  } else {  //若左子树为空，右子树不为空
    if(T->rchild!=NULL) {
    printf("(");  //输出一个左括号
    ShowTree(T->lchild);  //通过递归继续输出结点的左子树结点下的各结点
    if(T->rchild!=NULL) {  //若该结点的右子树不为空  
      printf(",");  //输出一个逗号
      ShowTree(T->rchild);  //通过递归继续输出结点的右子树结点下的各结点
    }
    printf(")");  //输出一个右括号
    }
  }
  }
}

例如，一个二叉树如下图，通过链式存储结构实现建立二叉树并输出。

代码如下：

#include <stdio.h>
#include <malloc.h>
/*1、二叉树的定义*/
typedef struct BNode {
  int data;  //数据域
  struct BNode *lchild,*rchild;  //左孩子、右孩子指针
} *BTree;
/*2、二叉树的建立*/
BTree CreateTree() {
  BTree T;
  char ch;
  scanf("%c",&ch);
  getchar();  //getchar()用于接收每次输入字符结点后的回车符，从而以便输入下一个字符结点
  if(ch=='0') //当为0时，将结点置空
  T=NULL;
  else {
  T=(BTree)malloc(sizeof(BTree)); //分配一个新的结点
  T->data=ch;
  printf("请输入%c结点的左孩子结点：",T->data);
  T->lchild=CreateTree();  //通过递归建立左孩子结点
  printf("请输入%c结点的右孩子结点：",T->data);
  T->rchild=CreateTree();  //通过递归建立右孩子结点
  }
  return T;
}
/*3、广义表输出二叉树*/
void ShowTree(BTree T) {
  if(T!=NULL) {
  //当二叉树不为空时
  printf("%c",T->data); //输入出该结点的数据域
  if(T->lchild!=NULL) {  //若该结点的左子树不为空
    printf("(");  //输出一个左括号
    ShowTree(T->lchild);  //通过递归继续输出结点的左子树结点下的各结点
    if(T->rchild!=NULL) { //若该结点右子树不为空
    printf(",");  //输出一个逗号
    ShowTree(T->rchild);  //通过递归继续输出结点的右子树结点下的各结点
    }
    printf(")");  //输出一个右括号
  } else {  //若左子树为空，右子树不为空
    if(T->rchild!=NULL) {
    printf("(");  //输出一个左括号
    ShowTree(T->lchild);  //通过递归继续输出结点的左子树结点下的各结点
    if(T->rchild!=NULL) {  //若该结点的右子树不为空  
      printf(",");  //输出一个逗号
      ShowTree(T->rchild);  //通过递归继续输出结点的右子树结点下的各结点
    }
    printf(")");  //输出一个右括号
    }
  }
  }
}
/*主函数*/
int main() {
  BTree T;
  T=NULL;
  printf("请输入二叉树的根结点：");
  T=CreateTree();  //建立二叉树
  printf("建立的二叉树如下：\n");
  ShowTree(T);  //通过广义表显示二叉树
}

依次输入各个结点的左右孩子结点，若结点不存在则输入0，例如树中结点d的左孩子结点不存在，结点f、g、h、i、j的左右孩子都不存在。

运行结果如下，结果通过广义表的定义显示：

（四）二叉树的先、中、后遍历

例如对下图这个二叉树，进行先、中、后遍历：

1、先序遍历二叉树：

/*先序遍历二叉树*/
bool ProTree(BTree T) {
  if(T==NULL)
  return false;   //递归结束
  else {
  printf("%c ",T->data);  //输出当前结点的数据域
  ProTree(T->lchild);  //递归继续遍历该结点的左子树
  ProTree(T->rchild);  //递归继续遍历该结点的右子树
  return true;
  }
}

运行结果如下：

2、中序遍历二叉树：

/*中序遍历二叉树*/
bool InTree(BTree T) {
  if(T==NULL)
  return false;   //递归结束
  else {
  InTree(T->lchild);  //递归继续遍历该结点的左子树
  printf("%c ",T->data);  //输出当前结点的数据域
  InTree(T->rchild);  //递归继续遍历该结点的右子树
  return true;
  }
}

运行结果如下：

3、后序遍历二叉树：

/*后序遍历二叉树*/
bool PostTree(BTree T) {
  if(T==NULL)
  return false;    //递归结束
  else {
  PostTree(T->lchild);  //递归继续遍历该结点的左子树
  PostTree(T->rchild);  //递归继续遍历该结点的右子树
  printf("%c ",T->data);  //输出当前结点的数据域
  return true;
  }
}

运行结果如下：

（五）二叉树的层次遍历

层次遍历二叉树：

/*7、层次遍历二叉树*/
void LevelTree(BTree T) {
  BTree q[MAXSIZE];  //MAXSIZE的值可自行定义
  int front=0,rear=0;  //初始化队头指针和队尾指针为0
  if(T!=NULL) {   //当二叉树不为空
  q[rear++]=T;      //根结点入队
  while(front!=rear) {    //当队列不为空时
    BTree head=q[front++];
    printf("%c ",head->data); //访问队头结点的数据域
    if(head->lchild)    //若当前结点的左孩子存在，将队头结点的左孩子入队
    q[rear++]=head->lchild;
    if(head->rchild)    //若当前结点的右孩子存在，将队头结点的右孩子入队
    q[rear++]=head->rchild;
  }
  }
}

也是上图中的二叉树，进行层次遍历，运行结果如下：

（六）二叉树的深度

二叉树的深度也是求最大深度，也是采用递归思想，分别递归计算左、右子树的深度，然后从左、右子树的深度中返回最大值，即为二叉树的深度，实现代码如下：

/*二叉树的深度*/
int DepthTree(BTree T) {
  int ldepth=0,rdepth=0;  //分别代表左、右子树的深度，初始值都为0
  if(T==NULL)
  return 0;
  else {
  ldepth=DepthTree(T->lchild);  //递归继续统计结点的左子树深度
  rdepth=DepthTree(T->rchild);  //递归继续统计结点的右子树深度
  if(ldepth>rdepth)  //求最大深度
    return ldepth+1;
  else
    return rdepth+1;
  }
}

对于上图中的二叉树，运行结果如下：

（七）二叉树的叶子结点数

求一个二叉树的叶子结点数，也是递归方法实现，我们知道若一个结点的左、右孩子都为空，则这说明这是一个叶子结点，通过递归，最后return返回叶子结点数，实现代码如下：

/*二叉树的叶子结点数*/
int LeavesNum(BTree T) {
  if(T!=NULL) { //当根结点不为空
  if(T->lchild==NULL&&T->rchild==NULL)  //若一个结点的左、右孩子都为空，即这是一个叶子结点 
    return 1;
  }
  return (LeavesNum(T->lchild)+LeavesNum(T->rchild));
}

对于上图中的二叉树，运行结果如下：

（八）二叉树的结点总数

也是递归，当二叉树不为空时，二叉树的结点总数等于左子树结点个数+右子树结点个数，然后加1（二叉树的根结点），实现代码如下：

/*求二叉树的结点总数*/
int SumLeaves(BTree T) {
  if(T!=NULL)
  return (SumLeaves(T->lchild)+SumLeaves(T->rchild)+1);
}

对于上图中的二叉树，运行结果如下：