2.7 计算叶子节点个数
这里我们采取的也是分治的思想，相信在经过前两道题的讲解，大家对于分治思想已经有了初步的了解，那么我们这里的思考是，我们的叶子节点等于左子树+右子树的叶子节点个数，那么我们怎么判断叶子节点呢？在了解过叶子节点的特征我们可以知道，叶子节点没有孩子节点。
这里的代码如下：
int BinaryTreeLeafSize(BTNode* root) { if (root == NULL) { return 0; } int leftn = BinaryTreeLeafSize(root->left); int rightn = BinaryTreeLeafSize(root->right); if (root->left == NULL && root->right == NULL) { return leftn+rightn + 1; } return leftn + rightn; }
对于计算叶子节点的个数，为了避免递归的重复访问，我们还是采取用变量记录值的方法，这里返回图如下。
大家可以依据这个过程去理解递归。
2.8 计算树第k层的节点数
这里我们采用的思想还是分治思想，那么这里我们的思路如下
得到一棵树第k层节点数，相当于是我们得到左子树的第k-1层的节点数加上右子树的第k-1层节点数，那么我的代码如下：
int TreeLevel(BTNode* root, int k) { if (root == NULL) { return 0; } if (k == 1) { return 1; } return TreeLevel(root->left, k - 1) + TreeLevel(root->right, k - 1); }
那么我们这里还需要考虑到两个情况：
情况一：也就是我们的第k层大于树的深度，那么这里势必会访问到空节点，那么我们只需要在空节点就返回即可，如果k大于树的深度，那么我们返回的值也是0。如果是我们需要统计的那一层某个节点的某个孩子是空节点，那么我们返回的是那个空节点返回的值加上1，这里也是不影响我们统计第k层节点数的。
情况二：当k=1时，我们此时访问的也是第k层的节点，那么我们一访问到第k层的节点就需要返回1。
这里的返回图我浅显的给大家画一下
大家配合代码以及递归展开图理解一下。
2.9 以内容查询树内的某个节点
这里我相信大家已经猜到了，我们这里采用的还是分治思想，那么我们这里的思路是：从左右子树出发对节点进行访问，访问到我们的节点内容就返回该节点地址，否者返回空。
BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root == NULL) { return NULL; } BTNode* leftn = BinaryTreeFind(root->left, x); if (leftn) { return leftn; } BTNode* rightn = BinaryTreeFind(root->right, x); if (rightn) { return rightn; } return NULL; }
那么我们这里开始访问的是左子树，这里每次对访问的节点进行记录，其次我们这里就会对记录值进行判断，如果为空，不进行返回，则说明我们访问到了空节点，如果不为空则说明我们已经找到了我们所需要的节点，那么这里就会返回我们所需要的值，如果将左右子树遍历我结束，还没有获得我们所查找值，那么就会返回空。
返回图如下：
大家可以自己画一画递归展开图理解一下。
2.10 层序遍历
对于层序遍历我们这里需要使用到我们之前编写的队列这个结构，我们这里的思路是，出上一层，入下一层。那么这里就能合理的将树按照层序遍历的方式进行数据访问。在使用之前我们需要进行一个操作就是我们需要构建一个存储树这种节点的队列，至于队列的介绍，大家可以翻看小编主页的另外一篇文章。那么这里的代码如下：
void BinaryTreeLevelOrder(BTNode* root) { Queue q; QueueInit(&q); 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); } } QueueDestroy(&q); }
但是这里由于我们存储的是树的节点，所以我们需要将队列的存储元素类型改为我们树的指针类型。
如下：
typedef struct BinaryTreeNode* QDataType;//存储类型修改成树的结构的指针类型 typedef struct QListNode { struct QListNode* _pNext; QDataType _data; }QNode; // 队列的结构 typedef struct Queue { QNode* _front; QNode* _rear; int size; }Queue;
这里具体的过程我举例一组例子给大家看看具体过程：
这里大家配合代码理解一下。
2.11 判断是否为完全二叉树
由于这里我们判断一棵树是二叉树或者为完全二叉树，那么我们就要利用完全二叉树的特殊性，这里我们可以发现我们利用层序遍历，完全二叉树的空节点是连续的，那么我们就可以利用这点来判断完全二叉树。
但是这里我们与上面的层序遍历不一致，这里由于我们要判断空是否连续，所以我们需要把空节点也入队列，那么这里我们入队列的判断条件就与我们上方的层序遍历不一致。
这里先给大家看代码，我再给大家讲解代码思路
bool BinaryTreeComplete(BTNode* root) { //思路完全二叉树按层序走，非空节点一定是连续的 Queue q; QueueInit(&q); QueuePush(&q, root); BTNode* front; while (!QueueEmpty(&q))//入队列中的的节点，如果访问到空节点就结束循环 { front = QueueFront(&q); QueuePop(&q); if (front == NULL) { break; } QueuePush(&q, front->left); QueuePush(&q, front->right); } while (!QueueEmpty(&q))//访问到空节点的元素，就不断出队列，直到队列为空还没有访问到除空节点 //以外的节点，说明是完全二叉树，否则不是 { QueuePop(&q); front = QueueFront(&q); if (front != NULL) { QueueDestroy(&q); return false; } } QueueDestroy(&q); return true; }
这里我给大家分别举一个例子，大家理解一下：
普通二叉树：
完全二叉树：
这里我们发现我们遇到NULL后出队列的所有元素都是空节点，因此这时完全二叉树。
3. 功能测试
int main() { BTNode* root = CreatTree(); preorder(root); printf("\n"); Inorder(root); printf("\n"); PostOrder(root); printf("\n"); printf("%d", TreeSize(root)); printf("\n"); printf("%d", TreeHeight(root)); printf("\n"); printf("%d", TreeLevel(root, 4)); printf("%p\n", BinaryTreeFind(root, 5)); printf("%p\n", BinaryTreeFind(root, 50)); printf("叶子节点个数是%d\n", BinaryTreeLeafSize(root)); BinaryTreeLevelOrder(root); printf("\n"); printf("%d", BinaryTreeComplete(root)); return 0; }
这里我们利用我们构建的二叉树将所有我们实现的功能进行测试，这里我们看结果。
