一、二叉树的三种遍历

1.1前序遍历

对于二叉树的链式结构，常用的三种遍历方式是

1、前序遍历(PreOrder)--访问根节点的操作发生在遍历其左右子树之前。

2、中序遍历(InOrder)--访问根节点的操作发生在遍历其左右子树之间。

3、后序遍历(PostOrder)--访问根节点的操作发生在遍历其左右子树之后。

前序遍历，简单来说就是以根-->左子树-->右子树的形式访问遍历。也就是说：在访问任何一个节点时，都是根的优先级最高，优先访问根，然后是左子树，右子树。以递归的形式访问遍历。

注意：

可能我说的还是优点抽象，以图为例：

比如这样一个二叉树，在进行前序遍历的时候，可能有读者误解为这样遍历：

先访问1，然后访问它的左子树2，然后再访问1的右子树4，然后再访问3，以此类推。这里特别提醒，这样是错误的，原因有二：

1、虽然好像这样满足我说的前序遍历--根-->左子树-->右子树，但是这是不符合递归的核心思想的，虽然2作为1的左子树，但是同时它还是3的根，以根-->左子树-->右子树访问，根的优先级最高的话，应是先访问本身作为根的2的左子树3，然后3又作为根去访问它的左子树，直到遇到NULL返回。

2、还有一个致命的问题，就是访问完4之后如何找到2的左子树3呢？因此这样是不合理的。

对于上面这个二叉树，正确的遍历应该是：

通过这个相对潦草的图解，我们可以发现这样访问：

无论从整体还是局部上满足根-->左子树-->右子树的访问。

我们要写它的递归的话，满足这样一个规律：当从根访问到左子树，左子树本身又作为它的左右子树的根，它再访问它的左子树，当访问到NULL，就去访问右子树，而右子树本身也是作为它的左右子树的根，去访问它的左子树，以此类推，而这，就是前序遍历递归的本质，中序遍历和后序遍历与之类似。

代码实现：

我先把构造上面的树的代码放在下面，以便使用：

typedef int BTDataType;
typedef struct BTNode
{
  BTDataType data;
  struct BTNode* left;
  struct BTNode* right;
}BTNode;
BTNode* CreateBinaryTree()
{
  BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));
  assert(n1);
  BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));
  assert(n2);
  BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
  assert(n3);
  BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));
  assert(n4);
  BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
  assert(n5);
  BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));
  assert(n6);
  n1->data = 1;
  n2->data = 2;
  n3->data = 3;
  n4->data = 4;
  n5->data = 5;
  n6->data = 6;
  n1->left = n2;
  n1->right = n4;
  n2->left = n3;
  n2->right = NULL;
  n4->left = n5;
  n4->right = n6;
  n3->left = NULL;
  n3->right = NULL;
  n5->left = NULL;
  n5->right = NULL;
  n6->left = NULL;
  n6->right = NULL;
  return n1;
}

前序遍历代码：

void PreOrder(BTNode* root)//前序遍历
{
  if (root == NULL)
  {
  printf("NULL ");
  return;
  }
  printf("%d ", root->data);
  PreOrder(root->left);
  PreOrder(root->right);
}
int main()
{
  BTNode* root= CreateBinaryTree();
  PreOrder(root);//前序遍历
    printf("\n");
    return 0;
}

遍历运行的结果也是和我们所推测的一样。同时也可以看到，这个递归写起来也是比较简单的。

1.2中序遍历

中序遍历，就是以左子树-->根-->右子树的形式访问遍历。也就是说：在访问任何一个节点时，都是左子树的优先级最高，优先访问左子树，然后是根，右子树。以递归的形式访问遍历。

相信读者通过我对前序遍历介绍已经可以自己轻松写出中序遍历了，所以对于中序遍历和后序遍历，博主也是简单介绍，不多赘述了。

void InOrder(BTNode* root)//中序遍历
{
  if (root == NULL)
  {
  printf("NULL ");
  return;
  }
  InOrder(root->left);
  printf("%d ", root->data);
  InOrder(root->right);
}
int main()
{
  BTNode* root= CreateBinaryTree();
  InOrder(root);
  printf("\n");
  return 0;
}

也是和推断的相吻合的。

1.3后序遍历

后序遍历，就是以左子树-->右子树-->根的形式访问遍历。也就是说：在访问任何一个节点时，都是左子树的优先级最高，优先访问左子树，然后是右子树，根。以递归的形式访问遍历。

代码：

void PostOrder(BTNode* root)//后序遍历
{
  if (root == NULL)
  {
  printf("NULL ");
  return;
  }
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ", root->data);
}
int main()
{
  BTNode* root= CreateBinaryTree();
  PostOrder(root);//后序遍历
  printf("\n");
  return 0;
}

验证：

1.4遍历推倒遍历

在一些习题里，我们经常会遇到题目给出前序遍历和中序遍历来求后序遍历，或者由中序遍历和后序遍历来求前序遍历。初学者可能比较头疼，尽管我们由它的访问原则很容易就得出根，但是接下来就无从下手了。

今天博主就分享比较简单的方式去拆解，相信看完后再麻烦的遍历都难不倒你！

首先声明：仅有两种方式可以唯一确定二叉树。

1、已知前序遍历和中序遍历；

2、已知中序遍历和后序遍历.

对于第三种已知前序遍历和后序遍历是无法唯一确定二叉树的。

例题：已知某二叉树的中序遍历序列为J G D H K B A E L I M C F,后序遍历序列为 J G K H D B L M I E F C A,则其前序遍历为：?

其实这种题谨记一点：我们在遍历二叉树的时候使用了什么规则，就按这个规则去拆解。

通过后序遍历，我们确定最后一个节点一定是根，通过中序遍历，我们确定了根的左子树有哪些元素，根的右子树有哪些元素。然后对左子树进行这样的分析，对右子树也是如此。

左子树元素有：J G D H K B(中序遍历)

                        J G K H D B(后序遍历)

我们再次确认B是根，B的左子树为：J G D H K (中序遍历)

                                                          J G K H D (后序遍历)

B的右子树为NULL，再次分析根为D，D的左子树为：J G(中序遍历) J G(后序遍历)

                                                            D的右子树为： H K(中序遍历) K H(后序遍历)

至此，左子树可以画出来了：

右子树元素有：E L I M C F(中序遍历)

                        L M I E F C(后序遍历)

现在确定C是根，C的左子树为：E L I M (中序遍历)

                                                    L M I E (后序遍历)

C的右子树为F，再次分析根为E，E的左子树为：NULL

                                                     E的右子树为：L I M(中序遍历)  L M I(后序遍历)

现在，右子树可以画出来了：

合并一下：整体的树：

前序遍历：A B D G J H K C E I L M F.

最后;为什么前序和后序无法唯一确定呢？很简单，因为前序遍历第一个是根，后序遍历最后一个也是根，那么，哪一个是根呢？

二、二叉树的一般接口

2.1二叉树的层序遍历

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

像这样，就是层序遍历。这个接口在于计算节点的个数，我们如何通过一层一层的遍历实现统计节点的个数呢？

很明显，层序遍历与上文的前中后序遍历有着殊途同归的意味，我们也是通过递归来实现的。我们把这个问题缩小到一个根和它的左右子树这样一个范围内会有助于我们思考：

如果根不是空，那么算上根的个数之后我们就要去计算它的左右子树的个数，而左右子树又是作为它的左右子树的根，类似于套娃。

打个比方：这个问题就类似于，老师让班长去统计人数，然后班长又去让各科课代表去统计人数，各科课代表呢，又让小组长去统计人数，无限细分，当就剩一个人的时候，就返回。

int TreeSize(BTNode* root)
{
  return root == NULL ? 0 :
  TreeSize(root->left) + TreeSize(root->right) + 1;//加一是要算上根的个数
}
int main()
{
  BTNode* root= CreateBinaryTree();
  int size = TreeSize(root);
  printf("%d ", size);
  printf("\n");
  return 0;
}

以递归的方式来写是很简单的。我们可以画图来印证一下：