一、链式存储：

在之前的博客中，我们说过，二叉树的存储结构一般可以简单地分为顺序存储结构与链式存储结构，今天我们将要进行研究的，就是其实中的链式存储结构。

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。

链式存储结构又可以分为二叉链与三叉链：

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
    struct BinTreeNode* left; // 指向当前节点左孩子
    struct BinTreeNode* right; // 指向当前节点右孩子
    BTDataType data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode
{
    struct BinTreeNode* parent; // 指向当前节点的双亲
    struct BinTreeNode* left; // 指向当前节点左孩子
    struct BinTreeNode* right; // 指向当前节点右孩子
    BTDataType data; // 当前节点值域
}；

我们今天要研究的，是其中的二叉链部分，而三叉链的部分将来在研究红黑树时详细学习。普通二叉树的增删查改复杂且没有意义，所以我们并不打算学习它的增删查改，主要是学习它的结构。

二、链式结构的遍历：

学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历（Traversal）是指：按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。同时，遍历也是二叉树上最重要的运算之一，是二叉树上进行其它运算的基础。

1.前序、中序与后序遍历：

按照规则，二叉树的遍历有：前序、中序与后序的递归结构遍历，其规则如下：

前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。

中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之间。

后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

// 二叉树前序遍历
void PreOrder(BTNode* root);
// 二叉树中序遍历
void InOrder(BTNode* root);
// 二叉树后序遍历
void PostOrder(BTNode* root);

由于被访问的结点必是某子树的根，所以 N(Node）、L(Left subtree）和 R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR 和 LRN 分别又称为先根遍历、中根遍历和后根遍历。

1.1 概念选择题

利用已知限有条件构建二叉树

1.某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。该完全二叉树的前序序列为（ ）

A. ABDHECFG

B. ABCDEFGH

C. HDBEAFCG

D. HDEBFGCA

分析

所以选择 A 选项

2.二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK; 中序遍历：HFIEJKG; 则二叉树根结点为（ ）

A. E

B. F

C. G

D. H

• 分析
  根据这棵树的先序遍厉、中序遍厉可以重建这棵树。但其实这里并不需要重建，因为先序遍厉是从根开始的。

所以选择 A 选项

3.设—课二叉树的中序遍历序列: badce，后序遍历序列: bdeca, 则二叉树前序遍历序列为（ ）

A. adbce

B. decab

C. debac

D. abcde

分析

根据这棵树的后序遍厉、中序遍厉可以重建这棵树。

所以选择 D 选项

某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF，

4.某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF，则按层次输出 (同一层从左到右) 的序列为（ ）

A. FEDCBA

B. CBAFED

C. DEFCBA

D. ABCDEF

• 分析

显然这道题作为选择题来说一眼就能知道答案：根据它的后序遍厉知道根是 F

所以选择 A 选项

总结:想要构建或还原一棵树，需要知道1.前序遍历序列+中序遍历序列 2.中序遍历序列+后序遍历序列 //前序+后序是无法还原的，因为不能判断左右子树的顺序

2.层序遍历：

除了最常用的先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为 1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第 2 层上的节点，接着是第三层的节点，以此类推。而这种自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

3.DFS(深度)与BFS(广度)

深度和广度，其实指的是：

1.深度优先遍厉：二叉树的前序遍历、中序遍历、后序遍历->一般用递归

注意 有些说法只认同前序遍历,看具体如何定义

2. 广度优先遍厉：二叉树的层序遍历->一般用队列

eg.扫雷 DFS->八路遍历 , BFS->一圈一圈往外出

三、各接口功能实现：

1.创建二叉树结构：

首先创建一个二叉树节点的结构体类型，然后通过根节点对这个二叉树进行操作

typedef char BDataType;
typedef struct BinaryTreeNode
{
  struct BinaryTreeNode* left; // 指向当前节点左孩子
  struct BinaryTreeNode* right; // 指向当前节点右孩子
  BDataType data; // 当前节点值域
}BNode;

2.创建二叉树节点：

节点的创建只需要动态开辟一个空间，用于存放我们节点的值，再将左右指针置空，并返回创建好的节点的地址

BNode* BuyNode(BDataType x)
{
  BNode* node = (BNode*)malloc(sizeof(BNode));
  if (node == NULL)
  {
    printf("malloc Error!\n");
    return;
  }
  node->data = x;
  node->left = NULL;
  node->right = NULL;
  return node;
}

3.前序遍历：

执行操作前需进行非空判断，防止对空指针进行操作。

对于前序遍历的操作原理，我们可以结合这张示意图来理解：

这个接口的实现方式（访问顺序）为：先访问根节点，即当前节点的值，接着递归访问左子树，最后递归访问右子树。使用递归实现整个二叉树的遍历，而不使用循环语句。

void PrevOrder(BNode* root)
{
  if (root == NULL)
  {
    printf("PrevOrder Error!\n");
    return;
  }
  printf("%c ", root->data); // 访问当前节点的值
  PrevOrder(root->left); // 先递归访问当前节点的左子树
  PrevOrder(root->right); // 再递归访问当中前节点的右子树
}

4.中序遍历：

执行操作前需进行非空判断，防止对空指针进行操作。

同样我们结合操作原理示意图来理解：

这个接口的实现方式（访问顺序）为：先递归访问左树，再访问节点自身，最后递归访问右树。中序遍历同样使用递归实现整个二叉树的遍历，而不使用循环语句。

void InOrder(BNode* root)
{
  if (root == NULL)
  {
    printf("InOrder Error!\n");
    return;
  }
  InOrder(root->left); // 递归访问当前节点的左树
  printf("%c ", root->data); // 访问当前节点的值
  InOrder(root->right); // 最后递归访问当前节点的右树
}

5.后序遍历：

执行操作前需进行非空判断，防止对空指针进行操作。

后序遍历操作原理示意图：

void PostOrder(BNode* root)
{
  if (root == NULL)
  {
    printf("PostQrder Error!\n");
    return;
  }
  PostOrder(root->left); // 先递归访问左子树
  PostOrder(root->right); // 再递归访问右子树
  printf("%c ", root->data); // 最后访问当前节点的值
}