【数据结构】——二叉树的递归实现，看完不再害怕递归

** 创作不易，感谢三连加支持？！**

一 递归理解

递归无非就是相信它，只有你相信它，你才能写好递归！为什么？请往下看

在进入二叉树的实现之前，我们得先理解一遍递归，可能很多人对于递归感到恐惧或者害怕，有时候还不敢面对，其实大可不必， 递归其实分为两个东西：

1.递归结束的条件

2.递归的子问题

1.递归的结束条件：一遍以题目的题意为主，只要理解题意就会知道结束条件是什么，比如求二叉树的结点个数，那他的结束条件就是没有结点的时候，没有结点，那就返回0就行了

2.递归子问题：在使用递归的过程中可能一个问题可以被分成很多个相同的问题，这些相同的问题也就是子问题，拿上面求二叉树的结点个数这个题目来说，我们要求的就是以根为结点这个树的所有结点个数，那么我们可以分成求根节点左子树和右子树的结点个数，然后左子树和右子树又可以和上面一样继续分开

弄清楚上面这个以后，我们在写递归的时候，可以先想想递归的结束条件是什么，然后先结束条件写上，然后再根据子问题一个一个分解，这个递归过程就完成了。

其实我们大部分对于上面两个点都理解，只不过我们写的时候就是写不出来，这种情况是不是很多人有呢？ 往下看，相信看完，你的疑惑会少很多！

那我们还是拿上面的例子来说明吧

求二叉树的结点个数（递归实现）

int BinaryTreeSize(BTNode* root)
{
    if (root == NULL)//判断条件
        return 0;
    return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;//递归
}

上面代码的结束条件很好理解，那么就是后面的递归过程不好理解

** 这里的+1是我们递归思想为左子树的结点个数＋右子树的结点个数＋自己 ，可能还是有点抽象**

那么我们不妨 先假设如果只有一个根结点，左右子树都为空，那么返回的就是他自己，也就是1

如果还是比较混乱，那就看看下面的图

如果理解了里面的细节，那么我们就看看如果攻破递归 ！！

首先判断条件我们肯定第一步直接写，那么我们的下一步就是把每一个递归看作一个黑盒，这个黑盒怎么运作的我们不管（这个是在你理解了递归的细节之后），相信它，它一定可以帮你完成任务，你相信它，它也相信你，比如上面的代码我们可以改成这样

int BinaryTreeSize(BTNode* root)
{
    if (root == NULL)
        return 0;
    int left = BinaryTreeSize(root->_left);//相信它，把它当作一个黑盒，它肯定能帮助你完成你想做的事情
    int right = BinaryTreeSize(root->_right);//和上面一样
    return left + right + 1;//最后把结果返回
}

** 这里的黑盒就是我们的递归函数，写完判断条件，那么后面我们希望求出左子树的结点个数和右子树的结点个数，那么我们直接把认为交给这两个黑盒（函数），他们可以帮我们算出来。剩下的我们只需要去把他们的返回值接收就行了，**然后把所有的结果一次性返回就ok了，相信看到这里，你应该有点感觉了

那我们趁热打铁，直接来看二叉树的实现

二 二叉树的实现

1.二叉树的创建和销毁

typedef char BTDataType;//一样的先定义一个树的结构体
typedef struct BinaryTreeNode
{
    BTDataType _data;
    struct BinaryTreeNode* _left;
    struct BinaryTreeNode* _right;
}BTNode;

//然后对它进行初始化
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;
}

创建二叉树可以用递归创建，也可以自己一个结点一个结点的创建
递归创建得先给你一个序列才能创建
这里我们用一个前序递归来创建二叉树

比如通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树

这里的’#’号代表空

1.既然是递归那么我们的想法就是先写出结束条件，那是不是当我们遇到空的时候就不用递归下去了，也就是遇到’#‘号我们直接返回就行了

2.第二就是我们是前序遍历，所以我们需要先把根结点弄出来

3.第三步递归去把左右子树全部创建，这里我们就需要用两个黑盒去实现

BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)//pi是数组下表
{
    if (*pi >= n || a[*pi] == '#')
    {
        (*pi)++;//遇到空了，下表也要往后面走
        return NULL;
    }
    BTNode* cur = BuyNode(a[*pi]);//不是空，那么我们创建根结点结点
    (*pi)++;//继续往后面走
    cur->_left = BinaryTreeCreate(a, n, pi);//黑盒去创建左子树
    cur->_right = BinaryTreeCreate(a, n, pi);//黑盒去创建右子树
    //完成任务直接返回根结点
    return cur;
}

** 那这样我们的二叉树就被创建出来了，其实也不是很难，如果用这个思想去做递归的题目可以轻松不少，因为想的少，前提是前期是理解了递归的过程，不然这样直接去想到后面也会寸步难行**

还有一个销毁，销毁我们可不是简单把指针置空就完成任务了，这里也需要递归去实现，和上面的思想一样

先判断结束条件，后面用黑盒去帮你把左右子树销毁，有这个思路，那么写起来就很轻松

void BinaryTreeDestory(BTNode* root)
{
    if (root==NULL)
    {
        return;//直接返回
    }
    BinaryTreeDestory(root->_left);//两个黑盒帮你完成任务
    BinaryTreeDestory(root->_right);
    free(root);//最后别忘记释放
}

那么下面我们就对以上的思想进行一个强化

2.计算二叉树叶子结点的个数

思想：计算叶子结点，那么结束条件肯定也是结点为空就停止，既然是叶子结点，那么肯定是左右子树都为空才是叶子结点，那么后面递归我们就需要用到黑盒去完成

int BinaryTreeLeafSize(BTNode* root)
{
    if (root == NULL)
        return 0;
    if (root->_left == NULL && root->_right == NULL)//两个为空才为叶子结点
        return 1;
    //这里如果不好理解，可以和上面一样把他们拆开然后再一起返回，都是黑盒思想
    return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}

这里没有＋1是没有算自己，因为我们是算的左右结点，如果左右结点是叶子结点那么就返回它就行了

3.二叉树第k层节点个数

思想：第一还是判断条件，如果结点为空，那么就返回，因为结点为空说明结点个数为0，

第二我们要算第k层的结点个数，我们知道如果k=1那么就一个结点，那如果k不是1，那我们就需要去左右子树去找第k层的结点数，剩下的就不需要我说了吧

int BinaryTreeLevelKSize(BTNode* root, int k)
{
    if (root == NULL)
        return 0;
    if (k == 1)
        return 1;
    //交给黑盒,然后返回就行
    return BinaryTreeLevelKSize(root->_left, k - 1)+
    BinaryTreeLevelKSize(root->_right, k - 1);
}

注意这里黑盒的参数，k是要一直减小的，因为是越来越靠近第k层的

4. 二叉树查找值为x的结点

一样的我们的黑盒大法

剩下的你们自己说

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
    if (root == NULL)
        return NULL;
    if (root->_data == x)//找到就返回
        return root;
    //黑盒大法
    BTNode*left=BinaryTreeFind(root->_left,x);
    BTNode* right = BinaryTreeFind(root->_right,x);
    //看那个不为空，不为空就返回
    if (left)
        return left;
    if (right)
        return right;
    //有的人会这样写
    //因为要返回的是指针，这里的或判断是bool型只会返回一个0或者1;
    //return  BinaryTreeFind(root->_left,x)||BinaryTreeFind(root->_right,x);
}

** 以上就是递归思想的总结和二叉树基本操作和实现，可以试试用上面的思想去做一下二叉树的前序遍历中序遍历和后序遍历，这样思路会更加清晰**

这里着重说一下层序遍历

5.二叉树的层序遍历

这里的就不是用黑盒思想那么简单了，这里的遍历需要用到队列去实现，思想就是先把根结点入队列，然后出队列，然后把左右结点入队列，左结点出队列的时候，把左结点的左左节点和右结点入队列，后面的操作和这里一样，这样也就实现了层序遍历

图画的不好还请谅解

void LevelOrder(BTNode* root)
{
    Queue q;
    QueueInit(&q);

    if (root)
        QueuePush(&q, root);//放头节点

    while (!QueueEmpty(&q))如果队列为空就退出来
    {
        BTNode* front = QueueFront(&q);//出第一个结点
        QueuePop(&q);

        printf("%d ", front->data);

        if(front->left)入左右结点
            QueuePush(&q, front->left);

        if (front->right)
            QueuePush(&q, front->right);
    }

    printf("\n");

    QueueDestroy(&q);
}

6.判断是否是完全二叉树

和上面一样都需要用队列实现，如果要用其他方法那就比较麻烦了，不推荐

这里的思想就是层序遍历，然后出数据，因为完全二叉树是连续的不可能出现左子树为空，右子树不为空的情况，所以如果出的数据为空，那么退出，然后再去遍历，如果有不为空的那么就不是完全二叉树

bool BTreeComplete(BTNode* root)
{
    Queue q;
    QueueInit(&q);

    if (root)
        QueuePush(&q, root);

    while (!QueueEmpty(&q))//和层序遍历一样
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);

        // 遇到空就退出
        if (front == NULL)
            break;

        QueuePush(&q, front->left);
        QueuePush(&q, front->right);
    }

    // 检查后面的节点有没有非空
    // 有不是空的，不是完全二叉树
    while (!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);

        if (front)
        {
            QueueDestroy(&q);
            return false;
        }
    }

    QueueDestroy(&q);
    return true;如果走到这里就说明是完全二叉树
}

如果看到这里，就请三连支持一下吧，非常感谢！