深入浅出：二叉树详解（含C代码）

【导读】：树是数据结构中的重中之重，尤其以各类二叉树为学习的难点。在面试环节中，二叉树也是必考的模块。本文主要讲二叉树操作的相关知识，梳理面试常考的内容。请大家跟随小编一起来复习吧。

本文针对面试中常见的二叉树操作做个总结：

1. 前序遍历，中序遍历，后序遍历；
2. 层次遍历；
3. 求树的结点数；
4. 求树的叶子数；
5. 求树的深度；
6. 求二叉树第k层的结点个数；
7. 判断两棵二叉树是否结构相同；
8. 求二叉树的镜像；
9. 求两个结点的最低公共祖先结点；
10. 求任意两结点距离；
11. 找出二叉树中某个结点的所有祖先结点；
12. 不使用递归和栈遍历二叉树；
13. 二叉树前序中序推后序；
14. 判断二叉树是不是完全二叉树；
15. 判断是否是二叉查找树的后序遍历结果；
16. 给定一个二叉查找树中的结点，找出在中序遍历下它的后继和前驱；
17. 二分查找树转化为排序的循环双链表；
18. 有序链表转化为平衡的二分查找树；
19. 判断是否是二叉查找树。

1 前序遍历，中序遍历，后序遍历；

1.1 前序遍历

对于当前结点，先输出该结点，然后输出它的左孩子，最后输出它的右孩子。以上图为例，递归的过程如下：

1. 输出 1，接着左孩子；
2. 输出 2，接着左孩子；
3. 输出 4，左孩子为空，再接着右孩子；
4. 输出 6，左孩子为空，再接着右孩子；
5. 输出 7，左右孩子都为空，此时 2 的左子树全部输出，2 的右子树为空，此时 1 的左子树全部输出，接着 1 的右子树；
6. 输出 3，接着左孩子；
7. 输出 5，左右孩子为空，此时 3 的左子树全部输出，3 的右子树为空，至此 1 的右子树全部输出，结束。

而非递归版本只是利用 stack 模拟上述过程而已，递归的过程也就是出入栈的过程。

/* 前序遍历递归版 */
void PreOrderRec(Node * node)
{
    if (node == nullptr)
        return;
    cout << node->data << " ";   // 先输出当前结点   
    PreOrderRec(node->left);     // 然后输出左孩子
    PreOrderRec(node->right);    // 最后输出右孩子
}

/* 前序遍历非递归版 */
void PreOrderNonRec(Node * node)
{
    if (node == nullptr)
        return;

    stack S;
    cout << node->data << " ";
    S.push(node);
    node = node->left;

    while (!S.empty() || node)
    {
        while (node)
        {
            cout << node->data << " "; // 先输出当前结点  
            S.push(node);
            node = node->left;         // 然后输出左孩子
        }                              // while 结束意味着左孩子已经全部输出

        node = S.top()->right;         // 最后输出右孩子
        S.pop();
    }
}


1.2 中序遍历

对于当前结点，先输出它的左孩子，然后输出该结点，最后输出它的右孩子。以（1.1）图为例：

1. 1-->2-->4，4 的左孩子为空，输出 4，接着右孩子；
2. 6 的左孩子为空，输出 6，接着右孩子；
3. 7 的左孩子为空，输出 7，右孩子也为空，此时 2 的左子树全部输出，输出 2，2 的右孩子为空，此时 1 的左子树全部输出，输出 1，接着 1 的右孩子；
4. 3-->5，5 左孩子为空，输出 5，右孩子也为空，此时 3 的左子树全部输出，而 3 的右孩子为空，至此 1 的右子树全部输出，结束。

/* 中序遍历递归版 */
void InOrderRec(Node * node)
{
    if (node == nullptr)
        return;

    InOrderRec(node->left);     // 先输出左孩子
    cout << node->data << " ";  // 然后输出当前结点
    InOrderRec(node->right);    // 最后输出右孩子
}

/* 前序遍历非递归版 */
void InOrderNonRec(Node * node)
{
    if (node == nullptr)
        return;

    stack S;
    S.push(node);
    node = node->left;

    while (!S.empty() || node)
    {
        while (node)
        {
            S.push(node);
            node = node->left;
        }                             // while 结束意味着左孩子为空

        cout << S.top()->data << " "; // 左孩子已经全部输出，接着输出当前结点
        node = S.top()->right;        // 左孩子全部输出，当前结点也输出后，最后输出右孩子
        S.pop();
    }
}


1.3 后序遍历

对于当前结点，先输出它的左孩子，然后输出它的右孩子，最后输出该结点。依旧以（1.1）图为例：

1. 1->2->4->6->7，7 无左孩子，也无右孩子，输出 7，此时 6 无左孩子，而 6 的右子树也全部输出，输出 6，此时 4 无左子树，而 4 的右子树已全部输出，接着输出 4，此时 2 的左子树全部输出，且 2 无右子树，输出 2，此时 1 的左子树全部输出，接着转向右子树；
2. 3->5，5 无左孩子，也无右孩子，输出 5，此时 3 的左子树全部输出，且 3 无右孩子，输出 3，此时 1 的右子树全部输出，输出 1，结束。

非递归版本中，对于一个结点，如果我们要输出它，只有它既没有左孩子也没有右孩子或者它有孩子但是它的孩子已经被输出（由此设置 pre 变量）。若非上述两种情况，则将该结点的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候,先依次遍历左子树和右子树。

/* 后序遍历递归版 */
void PostOrderRec(Node * node)
{
    if (node == nullptr)
        return;

    PostOrderRec(node->left);   // 先输出左孩子
    PostOrderRec(node->right);  // 然后输出右孩子
    cout << node->data << " ";  // 最后输出当前结点
}

/* 后序遍历非递归版 */
void PostOrderNonRec(Node * node)
{
    if (node == nullptr)
        return;

    Node * pre = nullptr;
    stack S;
    S.push(node);

    while (!S.empty())
    {
        node = S.top();

        if ((!node->left