一、什么是树和二叉树？

“树”在现实生活中大家都知道是什么，但在计算机界中却另有所指，指的是一种数据结构。
理论部分我还是引用百度百科上对于数据结构树的简介：

树是一种数据结构，它是由n(n≥0)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树。
————————————————引自百度百科

此外，树还有一些概念：

节点的度： 一个节点含有的子树的个数称为该节点的度； 如上图：A的为6
叶节点或终端节点： 度为0的节点称为叶节点； 如上图：B、C、H、I…等节点为叶节点
非终端节点或分支节点： 度不为0的节点； 如上图：D、E、F、G…等节点为分支节点
双亲节点或父节点： 若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点
孩子节点或子节点： 一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点
兄弟节点： 具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点
树的度： 一棵树中，最大的节点的度称为树的度； 如上图：树的度为6
节点的层次： 从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度： 树中节点的最大层次； 如上图：树的高度为4
堂兄弟节点： 双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点
节点的祖先： 从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
子孙： 以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
森林： 由m（m>0）棵互不相交的树的集合称为森林；

其实对于每一棵树，都可以分为根节点和若干棵子树，每一棵子树也可以被分为根节点和若干棵子树，所以树是一种递归定义的数据结构。
而恰好也是因为树是一种递归定义的数据结构，在我们在我们后面的实现当中，二叉树的各种接口几乎都是使用递归来实现的。

而在树中，有一种特殊的数被应用的非常广泛，那就是二叉树。
所谓的二叉树指的是度最大为2的树，也就是对于一个根节点来说最多有两个子节点，可以只有一个也可以一个没有。

在二叉树中也有两个比较特殊的二叉树：

1. 满二叉树： 一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是
   说，如果一个二叉树的层数为K，且结点总数是 ，则它就是满二叉树。
2. 完全二叉树： 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K
   的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对
   应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
   

其实对于树和二叉树还有很多的性质和公式，但这些在我们的实现中都用不到，想要实现一颗二叉树，我们只需要死死地抓住“递归”这个性质即可。
好，接下来就让我们进入二叉树的实现吧。

二、目标

今天要实现的二叉树主要有以下这些接口：

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* tree, int* pi);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树的高度
int BinaryTreeHeight(BTNode* root);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);
// 二叉树销毁
void BinaryTreeDestory(BTNode* root);

三、实现

3.1、初始化工作

开始之前我们得先定义好二叉树的节点类型，很简单，只需要定义两个左右子树的指针和一个值域即可：

// 重定义数据类型
typedef char BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType val;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

3.2、二叉树的前序遍历

之所以要先讲前序遍历而不是先讲二叉树的创建，是因为后面的创建也要用到前序遍历的思路，所以先讲前序遍历的思路会比较好一点儿。

3.2.1、原理图解

前序遍历即先访问根节点，然后依次是左子树和右子树，那我们应该怎么用代码实现呢？
记得我说过实现二叉树只需要死死地抓住“递归”这个性质，所以前序遍历当然是用递归实现的啦。

其实对于每一颗二叉树，我们都可以抽象的把它看成是三个点，即根节点、左子树、右子树：

而至于，左子树和右子树到底包含着什么内容(到底是空还是也包含了左子树和右子树)，我们可以暂时不管，想象在访问到它们的时候就会自动展开，这也正是递归的精髓所在。

所以对于前序遍历，我们就是先访问根节点(打印)，然后再递归地访问左子树和右子树(左在上右在下)。
对于左子树和右子树的递归结果我们可以暂时不管，它底层会自动处理。
而遇到空节点，我们可以直接返回，或者也可以打印出一个空(NULL)。

3.2.2、代码实现

有了以上思路，那我们写起代码来也就水到渠成了：

void BinaryTreePrevOrder(BTNode* root) {
    if (NULL == root) {
        return;
    }
    printf("%c", root->val);
    BinaryTreePrevOrder(root->left);
    BinaryTreePrevOrder(root->right);
}

3.3、二叉树的创建

其实通过前序遍历序列来创建二叉树在牛客上就有一道题：KY11 二叉树遍历和这里的是一模一样的。
感兴趣的朋友可以去做做。

3.3.1、原理解析

对于二叉树的遍历，其实前中后序的实现都很容易实现，但是对于二叉树的创建，就只有前序创建是最方便的。
因为这就像是单链表一样，如果你先创建了后面的节点，那你就找不到前面的节点了。二叉树也是如此，如果你先创建了左子树或者是右子树，那你怎么找得到根节点呢？
而如果非要用中序或者是后序实现，那也只能单链表那样保存前一个节点的位置，这里用递归实现的话就是在递归的时候再传入一个根节点的指针。但这样做的话就太麻烦了。

所以对于二叉树的创建，我们最好的就是用前序的方法，先创建根节点创建左子树和右子树，最后在返回根节点的指针即可。
因为我们这里是通过前序遍历的字符串来创建二叉树的，所以我们要传入一个序列的字符串，并且传入一个下标。
但因为局部变量的作用域只是在函数内，所以我们的这个下标要以指针的形式传入，这是因为指针的指向是唯一的，所以我们在任何一次递归中对于指针指向的整数的操作都是累加在一个变量上的。这也就避免了下标出错的情况。

3.3.2、代码实现

有了以上思路，那我们写起代码来也就水到渠成了：

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* tree, int* pi) {
    if (NULL == tree) {
        return NULL;
    }
    if ('#' == tree[*pi]) {
        (*pi)++;
        return NULL;
    }
    BTNode* root = (BTNode*)malloc(sizeof(BTNode));
    if (NULL == root) {
        perror("malloc fail!\n");
        exit(-1);
    }
    root->val = tree[*pi];
    (*pi)++;
    root->left = BinaryTreeCreate(tree, pi);
    root->right = BinaryTreeCreate(tree, pi);
    return root;
}

序列中的‘#’表示空。

3.4、二叉树的中序遍历

相信有了前面前序遍历的实现，再来理解中序和后序也就没什么问题了，不同之处也就是访问的先后不一样，即打印的位置不一样。

中序遍历的访问就是放在，左子树和右子树的递归结果中间，而后序就是放在两者之后：

void BinaryTreeInOrder(BTNode* root) {
    if (NULL == root) {
        return;
    }
    BinaryTreeInOrder(root->left);
    printf("%c", root->val);
    BinaryTreeInOrder(root->right);
}

3.5、二叉树的后序遍历

void BinaryTreePostOrder(BTNode* root) {
    if (NULL == root) {
        return;
    }
    BinaryTreePostOrder(root->left);
    BinaryTreePostOrder(root->right);
    printf("%c", root->val);
}

3.6、二叉树的层序遍历

与前中后序遍历不同，前面三个遍历都是用递归来完成了，唯独这个层序遍历不是用递归完成的，层序遍历的完成需要借助队列，然后通过循环的方式来完成。

3.6.1、原理图解

层序遍历就是从上至下，逐层访问，并且方向是从左往右，例如下面的这棵二叉树：

对它进行层序遍历的结果就是：

想要实现层序遍历，我们得要借助队列的先进先出规则，将各个节点的指针压入队列，只有这样我们才能实现“不依赖左子树和右子树的走向”来遍历二叉树，具体看下面的分析：
当只有三个节时：

首先我们现将根节点入队：

然后再将队头元素出队，并判断该节点的左右子树是否有空，将不为空的节点入队，这里的明显不为空，所以我们将左右子树的根节点都入队：

最后因为左右子树之后就没有节点了，所以我们依次将左右节点出队，当队列为空时，遍历就结束了：

所以，这可只有三个节点的二叉树的层序遍历序列就为：“ABC”。
有的朋友可能就认为，这不是和前序遍历一样吗？

其实这就理解错了，我们决不能用个例来分析全局，加入我再增加一个节点：

那结果就和前序遍历不一样了，因为在将B节点入队后不是先将D节点入队，而是先将C节点入队，在弹出B节点时才将D节点入队：

所以最后的遍历序列是：“ABCD”这就和前序不一样了。

重复执行上面的操作，我们可以报次的一个规律是：对于任何一颗二叉树及其子树，我们都是先将它的左子树的左右子树入队，再将它的右子树的左右子树入队，当然空节点就不需要入队了。
这样就完成了层序遍历。

3.6.2、代码实现

有了以上思路，那我们写起代码来也就水到渠成了：

void BinaryTreeLevelOrder(BTNode* root) {
    if (NULL == root) {
        printf("NULL\n");
        return;
    }
    Queue queue;
    QueueInit(&queue);
    QueuePush(&queue, root);
    BTNode* curRoot = NULL;
    while (!QueueEmpty(&queue)) {
        curRoot = QueueFront(&queue);
        QueuePop(&queue);
        printf("%c", curRoot->val);
        if (curRoot->left) {
            QueuePush(&queue, curRoot->left);
        }
        if (curRoot->right) {
            QueuePush(&queue, curRoot->right);
        }
    }
    QueueDestroy(&queue);
    printf("\n");
}

3.7、二叉树的节点个数

3.7.1、原理图解

其实统计节点个数也是有点像前序遍历，当然也是用递归来实现。
同样的我们还是可以把所有的二叉树都抽象成只有三个节点的形式：

所以在每次调用中，我们就只需要计算当前节点(根节点)，的节点数，然后左右子树的节点数就交给递归来完成啦，想象递归就是一个干苦力的，他会老老实实的帮我们完成其他任务，我们只需要关心自己的那一点任务即可。
对于根节点，如果根节点为空，那我们就返回0，否则我们就返回左右子树节点数的递归结果再加上根节点的节点数1即可。

3.7.2、代码实现

有了以上思路，那我们写起代码来也就水到渠成了：

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

3.8、二叉树的叶子结点个数

3.8.1、原理解析

其实统计叶子结点的个数和上面的统计节点个数思路类似，也是一个前序的思路，其实只是统计节点个数变一下型就好了。
叶子结点，即左右子树都为空的节点，那我们的返回条件就要相应的更改了，只有在左右子树都为空的情况下我们才返回1，当然空节的话也是返回0。而最后的递归返回就不用再加1了，因为很明显，如果一个根节点的左右子树有一个不为空，那这个根节点就一定不为叶子结点了。

3.8.2、代码实现

有了以上思路，那我们写起代码来也就水到渠成了：

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

3.9、二叉树第k层节点个数

3.9.1、原理图解

解决这个接口其实我们得用到一个等价思维，因为第k层的位置是不变的，而我们没往下走一层，都会离第k层越来越近。
假设根节点为第1层，所以我们要统计第k层的节点个数，就可以转化成统计第2层的第k - 1层的节点个数、统计第3层的第k - 2层的节点个数……
一次类推，当k递减到1时候，说明我们已经到达了第k层，也就不用再往下走了。

返回条件是：
如果根节点为空，无论是第几层都是返回0。
如果k为1并且根不为空，返回1.
如果跟不为空且k还不为1，递归返回左子树和右子树的第k - 1层统计结果。

3.9.2、代码实现

有了以上思路，那我们写起代码来也就水到渠成了：

int BinaryTreeLevelKSize(BTNode* root, int k) {
    assert(k > 0);
    if (NULL == root) {
        return 0;
    }
    if (1 == k && root != NULL) {
        return 1;
    }
    return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

3.10、二叉树的高度

二叉树的高度即二叉树的最大深度、二叉树的层数。

3.10.1、原理图解

这里的计算高度其实也使用了一个前序的思路，极限计算根节点的高度，如果根节点为空就直接返回0，再计算左右子树的高度。
只不过这计算的左右子树的高度要进行二选一，选出其中较大的高度再加上根的高度1，因为二叉树的高度即为二叉树的最大深度，我们很有可能遇到的是两颗子树的高度不相同的情况：

所以我们每次的递归中到要选择的是左右子树中高度最大的那个。

3.10.2、代码实现

有了以上思路，那我们写起代码来也就水到渠成了：

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

3.11、二叉树的查找值为X的节点

3.11.1、原理图解

节点的查找虽然说使用前中后的思路都行，还是优先使用前序的思路会比较好，因为如果查找同一个节点，使用前序思路的递归层数要比使用中序或后续的层数要少一点，而若是使用的是中序或后序，可能就要递归到最底层然后回归了才能找到。
例如下面这棵树，我们想要找到值为B的节点：

如果我们使用的是前序的思路，因为前序一进函数就进行比较，所以我们这里最多只用递归两层就能找到了：

而使用中序的话，那我们就要先递归到最底层，然后返回才能找到：

很明显就多了很多递归，中序尚且如此，后续就更不用说了。
所以查找我们也是优先采用先序。

3.11.2、代码实现

有了以上思路，那我们写起代码来也就水到渠成了：

BTNode* BinaryTreeFind(BTNode* root, BTDataType x) {
    if (NULL == root) {
        return NULL;
    }
    if (root->val = x) {
        return root;
    }
    BTNode* leftNode = BinaryTreeFind(root->left, x);
    if (leftNode) { // 为空就表示找不到，就不返回
        return leftNode;
    }

    BTNode* rightNode = BinaryTreeFind(root->right, x);
    if (rightNode) {
        return rightNode;
    }
    return NULL; // 左右子树都找不到，就返回空
}

3.12、判断二叉树是否为完全二叉树

3.12.1、原理图解

其实判断完全二叉树的思路和层序遍历的思路如出一辙，只不过结束的条件不用罢了。
我们先来回顾一下完全二叉树的概念：

完全二叉树： 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K
的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

抛这些冗长的概念不谈，我们就把目光放在“当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应”这个条件上。
那么什么才是一一对应呢？
我们可以先拿一个满二叉树和完全二叉树编上号对比一下：

如上图，可以理解为完全二叉树的各个节点的编号的位置和满二叉树的位置是可以重合的，即某一个在在满二叉树的第几层第几子树的左子树还是右子树，在完全二叉树中也是一样的。
所以在完全二叉树中决不能出现这种情况：

就是最底层的叶子结点不是并排在一起，中间空了一位，这就满二叉树对不上了。
其实也可以总结为，若完全二叉树的最底层的叶子结点未满，那么最后一个叶子结点一定是左孩子。

所以这也正是完全二叉树能用层序遍历的思路实现的原因，因为最后一层的叶子结点是连续的，所以当我们层序遍历在遇到空的时候，再往后走一定也都是空了：

而后面只要在遇到一个不为空的，就可以判定出不是完全二叉树。

所以判断完全二叉树的代码也就以下出来了：

3.12.2、代码实现

有了以上思路，那我们写起代码来也就水到渠成了：

bool BinaryTreeComplete(BTNode* root) {
    Queue queue;
    QueueInit(&queue);
    QueuePush(&queue, root);
    BTNode* curRoot = NULL;
    while (!QueueEmpty(&queue)) {
        curRoot = QueueFront(&queue);
        if (NULL == curRoot) {
            break;
        }
        QueuePop(&queue);
        QueuePush(&queue, curRoot->left);
        QueuePush(&queue, curRoot->right);
    }

    while (!QueueEmpty(&queue)) {
        curRoot = QueueFront(&queue);
        if (curRoot != NULL) {
            QueueDestroy(&queue);
            return false;
        }
        QueuePop(&queue);
    }
    QueueDestroy(&queue);
    return true;
}

3.13、二叉树的销毁

3.13.1、原理解析

二叉树的销毁最适合用的是后序的思路，因为先将根节点销毁了，那你就找不到左右子树了，这样还要额外的再保存左右子树的指针，太麻烦了。
而使用后序，因为递归的回归性，在销毁了后面的节点之后就会返回到上一个节点。所以这也就很方便，不用我们再额外的保存节点了。

3.13.2、代码实现

有了以上的思路，那我们写起代码来也就水到渠成了：

void BinaryTreeDestory(BTNode* root) {
    if (NULL == root) {
        return;
    }
    BinaryTreeDestory(root->left);
    BinaryTreeDestory(root->right);
    free(root);
}