前言

之前给大家介绍了有关堆的实现，那么这里小编就给大家带来今天的重头戏——二叉树的实现，以及介绍。

1. 二叉树的遍历

在介绍二叉树的实现之前，小编需要给大家给大家介绍一下二叉树遍历的几种方式，对于二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

1.1二叉树的前、中、后序遍历

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：

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

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

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

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

那么按照二叉树的前、中、后序遍历规则我们的具体操作以及遍历结果又是如何呢？请大家跟着小编继续往下分析。

这里我们给出一棵二叉树：

按照前序遍历规则这里我们得到的是：1 2 3 4 5 6

中序遍历：3 2 1 5 4 6

后序遍历：3 2 5 6 4 1

这里我给大家举个前序遍历的例子以便大家理解二叉树的遍历规则：

其实际以上上遍历的规则就是：当我们每次访问一个新的节点都可以将这个节点看作一个新的树的根节点重新利用该遍历规则继续遍历，那么实际上也是在该遍历的规则下将这个树不断拆解成更小的左右子树然后继续利用遍历的规则访问节点，这也就符合了递归中不断将问题拆解成小问题的规则，所以这里我们可以使用递归的思想去实现。

这里我们的每一次递归都会访问一个新的节点，根据前序遍历规则，我们这里先访问根节点（也即是我们每次递归先访问的节点），然后再访问左树，最后访问右树，递归结束条件也就是当我们访问到了空节点。

1.2 层序遍历

除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在

层数为 1 ，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第 2 层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

也即是：

2.二叉树的实现

由于在介绍堆的时候我们已经给大家介绍了二叉树的相关概念，所以这里小编就不再多加以介绍了，对二叉树相关概念不是很明白的可以翻看小编之前对堆有关介绍的文章。

2.1 二叉树的结构

之前我们在实现堆的时候由于堆是一棵完全二叉树，所以可以很好的使用数组对其进行存储，且不会造成大幅度的空间浪费，但是利用顺序表进行普通二叉树的存储，很可能会出现下面这种情况：

所以我们这里采用链表的方式对其进行存储，那么我们需要实现的链表的结构是：

typedef int BTDataType;
typedef struct BinaryTreeNode
{
  BTDataType data;
  struct BinaryTreeNode* left;
  struct BinaryTreeNode* right;
}BTNode;

在介绍遍历之前，我先给大家讲接一下遍历的递归返回值的理解——对于遍历递归的函数返回，第一是当我们遇到空节点，这里我们以经没有往下访问的必要了，我们应该返回上一层函数（也就是我们访问这个节点的父节点位置），进行其他的操作，第二是我们的函数调用完毕，那么对这颗我们理解上的”新树“已经访问结束，就要返回上一层函数，进行相关操作。

2.2构建二叉树

由于二叉树的增删操作的意义不大，所以对于二叉树节点的控制我们一般是手动控制，那么直接看代码

BTNode* BuyNode(BTDataType x)
{
  BTNode* node = (BTNode*)malloc(sizeof(BTNode));
  if (node == NULL)
  {
  perror("malloc fail");
  return NULL;
  }
  node->data = x;
  node->left = NULL;
  node->right = NULL;
  return node;
}
BTNode* CreatTree()
{
  BTNode* node1 = BuyNode(1);
  BTNode* node2 = BuyNode(2);
  BTNode* node3 = BuyNode(3);
  BTNode* node4 = BuyNode(4);
  BTNode* node5 = BuyNode(5);
  BTNode* node6 = BuyNode(6);
  BTNode* node7 = BuyNode(7);
  node1->left = node2;
  node1->right = node4;
  node2->left = node3;
  node4->left = node5;
  node4->right = node6;
  node3->right = node7;
  return node1;
}

首先我们写一个构造节点的函数，随后我们构造七个节点，然后利用树这个结构的左右指针，构造出我们所需要的结构，这里我构造的树是

2.2 前序遍历的实现

前面小编给大家简单的说明了前序遍历的遍历规则，以及该访问过程，那么我们用代码进行具体实现的过程是

void preorder(BTNode* root)
{
  if (root == NULL)
  {
  return;
  }
  printf("%d ", root->data);
  preorder(root->left);
  preorder(root->right);
}

可能大家这里有点迷惑，这短短的几行代码是怎么做到树的前序遍历的，这里我给大家简单的画一下递归展开图，以便大家更好的理解：

首先我们还是以这个树作为例子给大家画一下递归展开图：

（图中红线表示函数的递归调用，绿线表示函数向上返回，序号表示函数的调用次序）

从这里我们可以看出我们先从根节点进访问，然后通过函数的递归调用，不断进行打印节点值，先访问左子树，再访问右子树的操作，我们这里把新访问的节点理解为新访问树的根，这里我们进行的就是先打印根的值，然后再访问左子树，再访问右子树。不断的进行此类操作就实现了前序遍历。

2.3 中序遍历的实现

中序遍历和前序遍历的思路一致，只是我们进行的操作是先访问左子树，在打印访问节点的函数值，最后再执行访问右子树。

代码如下：

void Inorder(BTNode* root)
{
  if (root == NULL)
  {
  return;
  }
  Inorder(root->left);
  printf("%d ", root->data);
  Inorder(root->right);
}

递归展开图如下：

（图中红线表示函数的递归调用，绿线表示函数向上返回，序号表示函数调用次序）

这里我们可以看到展开之后每次都是先访问左节点之后，再对内容进行打印，也就是我们从左子树返回到上一层也就是该父节点位置（可以理解为分解出来的新树的根），然后进行打印操作，访问右子树后，把访问的节点理解为我们新树的根，然后对该树的左子树进行操作，直到左子树被访问完了后，打印这个节点（也就是我们新访问的右子树的那个节点）。这样不断递归就可以达到我们中序遍历的效果。

2.4 后序遍历的实现

后序遍历的规则是，先访问左节点，再访问右节点，最后访问根节点，这里我们代码实现如下

void PostOrder(BTNode* root)
{
  if (root == NULL)
  {
  return;
  }
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ", root->data);
}

递归展开图如下：

根据递归展开图，我们可以看到我们这里是左右子树都访问到空节点，然后开始打印，那么函数的返回过程也就是我们打印的过程，而这个过程也是从左子树开始，然后右子树，所以就可以的得到这里的访问顺序是左子树，右子树，根。

2.5 计算树的节点个数

这里我们先看代码：

int TreeSize(BTNode* root)
{
  if (root == NULL)
  {
    return 0;
  }
  return TreeSize(root->left) + TreeSize(root->right) + 1;
}

这里我们的采用的是的思想是分治思想，而分治思想就是把一个大问题分解为类似的小问题，而这我们往往是采用递归的方式的实现的，那么这里的的思路是，一个树的节点等于它的左子树的节点个数加上它的右子树节点个数，再加上该本身，而对于其左子树和右子树，我们可以看作是一棵新的树，该值也等于该左子树的节点树加上该右子树节点数加上本身，我们不断套用这个思想就可以解决此类方法。那么这里我给大家演示一下。

这里的我画的只是一个函数递归的返回过程，这里只有遇到空节点才会返回，由于我们这里是的返回是带值的，所以这里会得到我们下一层的返回值也即是该左右孩子中的某个值。对于递归展开图这里我就不给大家画了，大家可以自己尝试一下，慢慢自己去理解递归的神奇。

2.6 计算树的深度

对于计算树的深度我们还是采用的是分治的思想，那么我们该如何让思考呢，首先我们把关注点放在根，左子树，右子树上，那么的到一棵树的深度和左子树，右子树和根有什么关系呢？其实不难发现一棵树的高度等于左子树和右子树中最深的子树加上根节点的高度。

具体代码如下：

int TreeHeight(BTNode* root)
{
  if (root == NULL)
  {
  return 0;
  }
  int left = TreeHeight(root->left);//得到左子树深度
  int right = TreeHeight(root->right);//得到右子树深度
  return left > right ? left + 1 : right + 1;//对比左右子树深度，深度较深的+1
}

这里的模拟图如下：

这里我也只是给大家画了一个返回图，大家可以自行带入函数中画出函数展开图，去理解。

对于此处大家可能还有另外一种写法：

int TreeHeight(BTNode* root)
{
  if (root == NULL)
  {
  return 0;
  }
  return TreeHeight(root->left) > TreeHeight(root->right) ? TreeHeight(root->left)+ 1 :   
    TreeHeight(root->right)+ 1;//对比左右子树深度，深度较深的+1
}

这里的逻辑虽然是正确的，但是我们却在重复的进行我们已经进行了的递归操作，首先我们要遍历左右子树，比较左右子树哪棵树的深度较深，首先我们需要重新递归遍历得到较深的树的高度值，那么从某种意义上来讲我们是重复遍历了我们已经遍历的树了。所以在遍历树之后我们需要用一个变量记住左右子树的深度，那么就避免了重复访问的问题。

数据结构之二叉树的实现（一）

前言