数据结构之树和二叉树的基本概念，二叉树遍历算法的实现

导语：

在之前的文章里，我们介绍了线性表，单链表，栈，队列等这些线性结构，我们知道线性结构中结点间具有唯一前驱，唯一后继关系，而非线性结构中结点间前驱，后继的关系并不具有唯一性，例如：在树中，结点间是有唯一的前驱，而后继并不唯一，即结点之间是一对多的关系，而在图结构中，结点前驱与后继可并不是唯一的，即结点之间是多对多的关系，直观的看，树结构是指具有分支关系的结构（其分叉，分层的特征类似于自然界中的树），树结构应用非常广泛，特别是在大量数据处理（文件系统，编译系统，目录组织等）方面显得更加突出。

常见树的图解与基本术语：

树的图解：

当n等于零，该树被称为空树。

树的相关术语：

结点：包括一个数据元素及若干个指向其他结点的分支信息。

结点的度：一个结点的子树个数，在上述图示中，子树的个数为3.

页结点：度为0的结点，即无后继的结点，也称为终端结点。 例如上述图示中的EFGHIJ即是叶结点。

分支结点：度不为0的结点，也称作非终端结点，例如：上述图示中的BCD

结点的层次：从根节点开始定义，根节点的层次为1，根的直接后继的层次为2，以此类推。例如上述图示中B的层次为2，而E为3.

结点的层序编号：将树中的结点按照从上层到下层，同层从左到右的次序排成一个线性序列，依次给他们编以连续的自然数。

树的度：树中所有结点的度的最大值。

树的高度：树中所有结点的层次的最大值。

有序树：在树T中，如果个子树之间是有先后次序的，则称为有序树。

森林：m颗互不相交的树的集合，将一颗非空树的根节点删去。树就变成一个森林，反之给森林增加一个统一的根节点，森林就变成一棵树。

孩子结点：一个结点的直接后继称为该结点的孩子结点，例如B,C,D是A的孩子，而E,F,G是B的孩子。

双亲结点：一个结点的直接前驱称为该结点的双亲结点，例如A是B,C,D的双亲，而B是E,F,G的双亲。

我们知道树的分支可以有0个或多个，在讲解普通的树之前，我们先来讲解一种特殊的“树”----“二叉树”

二叉树：

何为二叉树？

二叉树的本质也是“树”，只不过是一种特殊的树，它满足结点的度不大于2，且结点的左右不能发生颠倒，也就是说二叉树的任意结点的孩子个数只能是0/1/2，位于左边的结点我们称之为“左孩子”，位于右边的结点，我们称之为“右孩子”

二叉树的五种基本形态：

二叉树的性质：

性质1：在二叉树的第i层上至多有2^i-1个结点（i>=1）

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

性质3：对任意一颗二叉树T，若终端结点数为n0,而其度数为2的结点数为n，则n0=n2+1

满二叉树：深度为k且有(2^k)-1个结点的二叉树，在满二叉树中，每层结点都是满的，即每层结点都具有最大结点数，满二叉树如下图所示：

满二叉树的顺序表示：从二叉树的根开始，按层间从上到下，层内从左到右顺序逐层进行编号（a,b,c…）

完全二叉树：深度为k，结点数为n的二叉树，如果将其结点1-n的位置序号分别与等高的满二叉树的结点1-n的位置序号一一对应，则为完全二叉树，

如下图所示：

性质4：具有n个结点的完全二叉树的深度为「log2n」+1.

性质5：对于具有n个结点的完全二叉树，如果按照从上到下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点

<1>如i=1，则序号为i的结点是根节点，无双亲结点，如i>1,则序号为i的结点的双亲结点为「i/2」

<2>如2i>n,则序号为i的结点无左孩子，如2i<=n,则序号为i的结点的左孩子结点的序号为2i

<3>如2i+1>n,则序号为i的结点无右孩子，则序号为i的结点的右孩子结点的序号为2i+1

二叉树的存储结构：

同之前的线性结构一样，二叉树同样也有两种存储结构：顺序存储和链式存储。

顺序存储：

对于完全二叉树来说，可以将其数据元素逐层存放到一组连续的存储单元中：

显然，这种存储方式对于完全二叉树来说是非常方便的，因为对于完全二叉树来说，采用顺序存储结构既不浪费空间，又可以根据公式计算出每一个结点的左右孩子的位置。

但是，对于一般的二叉树，必须用“虚结点”将其补成一颗“完全二叉树”来存储，这就会造成空间浪费，有一种极端的情况就是（如下图所示），从图中我们不难看出，对于深度为K的二叉树，在最坏的情况下（每个结点只有左孩子或者只有右孩子）需要占据(2^k)-1个存储单元，而实际该二叉树只有k个结点，这样便会使得空间大大浪费。

链式存储：

对任意的二叉树来说，每个结点只有一个双亲结点（根结点除外）,最多只有两个孩子，可以设计每个结点至少包括三个域：数据域，左孩子域和右孩子域。

二叉链表如下所示：

^表示空，也就是该结点没有左孩子或者右孩子

若一个二叉树有n个结点，，则它的二叉链表中必含有2n个指针域，其中必有n+1个空的链域。

有时，为了便于找到双亲结点，可以增加一个parent域，以指向该结点的双亲结点，采用这种结点的结构的存放方式为二叉树的三叉链表存储结构。

如下图所示：

二叉树的遍历：

二叉树的遍历是指按照一定的规律对二叉树中的每个结点进行访问且仅访问一次，其中的访问可指计算二叉树中结点的信息，打印该结点的信息，也包括对结点进行任何其他操作。

二叉树需要遍历的原因：

二叉树为非线性结构，通过遍历可以将二叉树中的结点访问一次且仅一次，从而得到访问结点的顺序序列。

也就是将二叉树中结点按照一定规律线性化的操作，目的在于将非线性化结构变成线性化的访问序列。

遍历什么？

我们知道二叉树总共有三个部分组成：根节点，左子树，右子树，那么只要我们想办法遍历了这三个部分就相当于将二叉树都进行了遍历。

通常我们使用L表示遍历左子树，使用D表示访问根节点，使用R表示遍历右子树

那么对于这三部分的遍历将有6中不同的顺序：

DLR/DRL/LDR/LRD/RDL/RLD

那如果我们规定按先左后右的顺序，上述的六种此时仅剩下3种，DLR/LDR/LRD。我们对这三种顺序按照访问根节点的先后顺序不同，将DLR[先序遍历]/LDR[中序遍历]/LRD[后序遍历]

注意：先序遍历，中序遍历，后序遍历，是递归定义的，不仅在整个二叉树要使用该规律，还要在二叉树的各个子树上也使用该规律，遍历的操作是一个递归过程。

遍历的操作过程：

先序遍历：

访问根节点->按先序遍历左子树->按先序遍历右子树

举例：

中序遍历：

按中序遍历左子树->访问根节点->按中序遍历右子树

举例：

后序遍历：

按后序遍历左子树->按后序遍历右子树->访问根节点

举例：

层序遍历：

从根节点出发，依次访问左右子树结点，再从左右子树出发，依次访问它们的子树结点，直到节点访问完毕 。

举例：

使用二叉树表示算数表达式：

无论那种遍历方式，它的遍历过程都是从上到下，一层一层进行。

最早提出遍历问题是对存储在计算机中的表达式求值

举例：

而这里的先序遍历的串行即为前缀表达式，中序遍历的串行即为中缀表达式，后序遍历的串行即为后缀表达式。

其中，中缀表达式是算数表达式的通常形式，只是没括号，前缀表达式称为逆波兰表达式，算数表达式的后缀表达式称为逆波兰式，在计算机中，使用后缀表达式易于求职值。

遍历算法的实现：

以二叉链表作为存储结构为例！

定义二叉链表结点的结构：

typedef struct Tree {
  char data;//数据域
  struct Tree* Lchild;//左孩子域
  struct Tree* Rchild;//右孩子域
}*BitTree;//BitTree为结构体指针变量

举例;

其中Lchild和Rchild为树指针之类，它们均指向的是一个结点，该结点又包括数据域，左孩子域和右孩子域。

二叉树的创建：

通过递归的思想创建二叉树：

BitTree createTree() {
  BitTree T;
  char data;
  char temp;
  scanf_s("%c", &data);//输入结点数据
  temp = getchar();
  if (data == '.')//表示该结点的左孩子或右孩子不存在即为NULL
  {
    return NULL;
  }
  else {
    T = (BitTree)malloc(sizeof(Tree));//分配结点空间
    T->data = data;//将当前数据放入数据域
    printf("请输入%c的左子树：",data);
    T->Lchild = createTree();//递归创建左子树
    printf("请输入%c的右子树：", data);
    T->Rchild = createTree();//递归创建右子树
    return T;
  }
}

分步讲解：

temp = getchar();

此行代码是用于处理字符和字符串输入时的问题，具体点就是，我们在输入下一个字符的时候需要换行，如果我们没有getchar()，那么系统就会自动将我们的"\n"符号当做输入的下一个字符，也就是说，它的作用为吞噬放在缓冲区的“enter”字符。

第一次递归过程如下：

第二次进行递归：

接着输入数据，也就是B的左子树结点的数据，假设我们此时输入的为"."也就是空的意思，此时执行return NULL；也就代表着创建B的左子树的这次递归已经完成了

但是程序并没有结束，我们前两次在进行递归的时候程序运行到，T->Lchild = createTree();又返回到函数开头了啊，下面的那几条语句都没有执行，那就接着执行啊，开始退层，当前data的数据即为B。

执行下面的语句创建B的右子树，非NULL，进行递归创建，NULL则开始退层，也就是执行没有执行完的语句，一次退一层。

二叉树的几种遍历依然是采用递归的思想，这里就不进行赘述了，需要注意的点，我会在文章最后的完整代码中注释出来

完整代码如下：

#include<stdio.h>
#include<stdlib.h>
typedef struct Tree {
  char data;
  struct Tree* Lchild;
  struct Tree* Rchild;
}*BitTree;
BitTree createTree() {
  BitTree T;
  char data;
  char temp;
  scanf_s("%c", &data);
  temp = getchar();
  if (data == '.')
  {
    return NULL;
  }
  else {
    T = (BitTree)malloc(sizeof(Tree));
    T->data = data;
    printf("请输入%c的左子树：",data);
    T->Lchild = createTree();
    printf("请输入%c的右子树：", data);
    T->Rchild = createTree();
    return T;
  }
}
void Preorder(BitTree T) {//先序遍历
  if (T == NULL) {
    return;
  }
  printf("%c", T->data);//根节点遍历----这里将遍历改为了输出具体数据
  Preorder(T->Lchild);//左子树遍历
  Preorder(T->Rchild);//右子树遍历
}
void Inorder(BitTree T) {//中序遍历
  if (T == NULL) {
    return;
  }
  Preorder(T->Lchild);//左子树遍历
  printf("%c", T->data);//数据输出
  Preorder(T->Rchild);//右子树遍历
}
void Postorder(BitTree T) {//后序遍历
  if (T == NULL) {
    return;
  }
  Preorder(T->Lchild);//左子树遍历
  Preorder(T->Rchild);//右子树遍历
  printf("%c", T->data);//结点数据输出
}
int main() {
  BitTree S;
  printf("请输入根节点的数据：");
  S=createTree();//S接受创建好的二叉树便于接下来的遍历
  printf("先序遍历输出如下：");
  Preorder(S);
  printf("中序遍历输出如下：");
  Inorder(S);
  printf("后序遍历输出如下：");
  Postorder(S);
  return 0;
}

输出：

其对应的二叉树如下图所示：