二叉树的叶子个数
求二叉树的叶子个数也是采用分治思想，求 该树的左子树的叶子个数加上该树的右子树的叶子个数，然后该树的左子树和右子树又可以分为 求 该树的左子树的叶子个数加上该树的右子树的叶子个数，依此继续细分，最终计算完后返回的就是每棵子树的叶子结点个数。
判断是否是叶子结点只需判断该结点的左孩子和右孩子是不是都为NULL即可，如果是就返回1。
当然，如果该结点为NULL，就直接返回0。
图示理解：
颜色出现的先后顺序可以看作递归的过程，上树的叶子结点为3。
相关函数接口代码实现：
// 二叉树的叶子个数 int TreeLeafSize(BTNode* root) { // 如果该结点为 NULL ， 说明不是叶子结点，直接返回 0 if (root == NULL) return 0; // 如果该结点的左孩子和右孩子都为 NULL ，说明该结点为叶子结点，返回 1 if (root->left == NULL && root->right == NULL) return 1; // 递归左子树和右子树，统计左右子树的叶子结点 return TreeLeafSize(root->left) + TreeLeafSize(root->right); }
求出二叉树的高度
求二叉树的高度也是采用分治思想：先求出该树的左子树的高度，再求出该树的右子树高度，然后比较得到高度高的那个加上自己（就是加一）。该树的左子树和右子树又是这样的一个操作：先求出该树的左子树的高度，再求出该树的右子树高度，然后比较得到高度高的那个加上自己（就是加一）。依次细分，最终递归返回得到的就是整棵树的高度（深度）。
图示理解：
相关函数接口代码实现：
// 二叉树的高度（深度） int TreeHeight(BTNode* root) { // 分治思想 // 如果该节点为空，没有高度，返回0 if (root == NULL) return 0; // 递归统计左右子树的高度 int leftheight = TreeHeight(root->left); int rightheight = TreeHeight(root->right); // 返回左右子树高度大小大的那个并加一，加一是加上该结点的高度1 return leftheight > rightheight ? leftheight + 1 : rightheight + 1; }
第K层的结点个数
求第K层的结点个数，如果K是1，就是根节点，答案为1；如果K是2，就是第二层的结点个数，此时我们在递归的时候，每向下递归一层，就把K视为K - 1一次，所以到达第二层的时候，K为1。由上不难发现，当K为1所在的层就是需要统计结点个数的层。因此有了判断：当该结点所在的层数有 K == 1 ，返回1。如果在第K层前或在第K层遇到NULL就返回0。
同样的，这里采用递归，分别递归左和右去寻找处在第K层的结点。
图示理解：
相关函数接口代码实现：
// 二叉树第K层的结点个数 int TKLevelNodeSize(BTNode* root, int k) { // 如果到达第K层之前或者到达第K层该结点为NULL，直接返回0 //（说明不是第K层的结点或者在第K层为NULL） if (root == NULL) return 0; // 如果k减到1了，说明到达第K层了，此时该结点有效，应计数1 if (k == 1) return 1; return TKLevelNodeSize(root->left, k - 1) + TKLevelNodeSize(root->right, k - 1); }
查找值为X的结点
查找值为X的结点，先在该树的左子树找，如果找到了就直接返回，如果找不到，再到该树的右子树去找，如果右子树找到了也直接返回，如果找不到，左右子树都没有，就返回NULL。
同样的，将上一条继续细分，这样递归下去就只有找到和找不到两种情况，如果找到了就返回找到的那个结点的指针，如果找不到就返回NULL。
图示理解：
相关函数接口代码实现：
// 二叉树结点数据的查找 BTNode* TreeDataFind(BTNode* root, BTDataType x) { // 如果该结点为NULL， 返回NULL if (root == NULL) return NULL; // 找到了就返回指向该结点的指针 if (root->data == x) return root; // 先在左边找 BTNode* lret = TreeDataFind(root->left, x); // 如果寻找不到返回NULL，这里if就不进去 if (lret) return lret; // 如果左没找到就找右 BTNode* rret = TreeDataFind(root->right, x); // 如果寻找不到返会NULL，这里if就不进去 if (rret) return rret; // 如果左右都没找到就返回NULL return NULL; }
二叉树的层序遍历
层序遍历就是一层一层的从左到右打印结点的数据，这里递归就办不到了，那么如何来实现呢？
首先我们需要一个队列，这个队列存储的数据是树结点的指针，我们先将根结点入队列（如果根结点为NULL就不入），然后取队头数据存下来（front） 并 出队列操作，接着打印front指向的结点的数据(front->data)，最后将front指向的结点的左孩子和右孩子分别入队列（如果为NULL就不入）。整个操作是一个循环，当队列为空时结束遍历。
队列的代码可以直接从之前写的队列那一章拷贝过来(这里就不放了)：-> 队列传送门 <-
图示理解：
相关函数接口代码实现：
// 层序遍历，利用队列来操作 void LevelOrder(BTNode* root) { // 队列的每一个数据是一个树的结点 Que q; QInit(&q); // 如果根节点不为NULL就入队列 if (root) QPush(&q, root); // 队列不为空就继续 while (!QEmpty(&q)) { // 取队头元素（树的结点） BTNode* front = QFront(&q); // 出队列是释放队头的空间，在队头存放的树的结点没有被释放 QPop(&q); // 打印树结点中的数据 printf("%d ", front->data); // 如果该队头树结点的左孩子不为空就入队列 if (front->left) QPush(&q, front->left); // 如果该对头树节点的右孩子不为空就入队列 if (front->right) QPush(&q, front->right); } printf("\n"); // 记得销毁队列噢，防止内存泄漏 QDestroy(&q); }
是否为完全二叉树
- 判断一棵二叉树是否为完全二叉树，首先要知道什么是完全二叉树，前面 树的介绍 这一章详细讲解了完全二叉树，这里就不做过多探讨。
- 我们需要知道的是，一棵完全二叉树，我们以层序的视角去看待它，会发现它是连续的：
所以根据此性质，这里可以运用层序遍历的思想，用一个队列来解决。
但与层序遍历不同的是，这里的入队列，是NULL也入，每次出队列就同时入队列这个出队列的数据的左孩子和右孩子，当出队列的这个树结点的指针为NULL的时候，说明前面的连续的有效结点组成的树是一颗完全二叉树，此时跳出循环。
跳出循环后，此时队列里面还有数据，如果队列里的数据全是NULL就说明这是一棵完全二叉树，如果队列里的数据有一个不是NULL，它就不是一棵完全二叉树。
图示理解：
相关函数接口代码实现：
// 判断该二叉树是否为完全二叉树 bool BTComplate(BTNode* root) { Que q; QInit(&q); // 如果root不为NULL就入队列 if (root) QPush(&q, root); while (!QEmpty(&q)) { // 取队头元素，就是一个树的结点 BTNode* front = QFront(&q); QPop(&q); // 如果当前结点是NULL，说明前面每层连续的有效结点都出队列了，直接跳出循环 if (front == NULL) break; // 入front结点的左孩子和右孩子，NULL也入 QPush(&q, front->left); QPush(&q, front->right); } // 如果队列不为NULL，接下来就是判断的重要一步了 // 根据完全二叉树的性质，当前面每层连续的有效结点都走完时 // 剩下队列里的元素如果都是NULL就说明该二叉树是一棵完全二叉树 // 如果有一个结点不为NULL，那么就说明该二叉树不是完全二叉树 while (!QEmpty(&q)) { BTNode* front = QFront(&q); QPop(&q); if (front) { // 如果找到一个有效结点，就说明该二叉树不是完全二叉树，直接返回false // 返回前记得销毁队列噢 QDestroy(&q); return false; } } // 如果前面循环走完，说明符合完全二叉树的性质，最后返回true // 返回前记得销毁队列噢 QDestroy(&q); return true; }
关于二叉树的销毁
- 二叉树的销毁也是一个递归的过层，这里采用的是后序遍历来依次销毁，因为如果采用前序或中序的话，递归就回不去了。
图示理解：
相关函数接口代码实现：
// 二叉树的销毁 // 注意一定是要通过后续遍历来销毁 // 因为后序遍历是 左 右 根 ，销毁左右再销毁根 // 这样能够递归返回回去 void BTDestroy(BTNode* root) { if (root == NULL) return; BTDestroy(root->left); BTDestroy(root->right); // 释放（返还）root指向的结点的空间 free(root); }
完整的二叉树代码
▶️队列的代码可以直接从之前写的队列那一章拷贝过来(这里就不放了)：->队列传送门<-。注意：拷贝过来后，要改一下队列存放的数据的类型（改为一个指向树的结点的指针）。
初等二叉树的完整代码BinaryTree.c
// 引入队列头文件之后，因为队列头文件里有下面的库函数包含，所以这里就不必重复包含了 //#include <stdio.h> //#include <assert.h> //#include <stdlib.h> //#include <stdbool.h> #include "queue.h" typedef int BTDataType; typedef struct TreeNode { // 存储数据 BTDataType data; // 指向左结点的指针 struct TreeNode* left; // 指向右结点的指针 struct TreeNode* right; }BTNode; // 得到一个结点 BTNode* BuyTreeNode(BTDataType x) { BTNode* newnode = (BTNode*)malloc(sizeof(BTNode)); // 判断一下是否申请空间失败 assert(newnode); newnode->data = x; // 两个指针都初始化 NULL newnode->left = NULL; newnode->right = NULL; // 返回指向这个结点空间的指针 return newnode; } // 自行建一棵树，可随意建树，但必须要是二叉树 BTNode* BuyTree() { // 依次得到一个结点 BTNode* n1 = BuyTreeNode(1); BTNode* n2 = BuyTreeNode(2); BTNode* n3 = BuyTreeNode(3); BTNode* n4 = BuyTreeNode(4); BTNode* n5 = BuyTreeNode(5); BTNode* n6 = BuyTreeNode(6); BTNode* n7 = BuyTreeNode(7); // 通过每个结点内的指针进行树的连接 n1->left = n2; n2->left = n3; n1->right = n4; n4->left = n5; n4->right = n6; n2->right = n7; // 返回所有结点的祖先结点 return n1; } // 二叉树的前序遍历 void PreOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } // 根 左 右 printf("%d ", root->data); PreOrder(root->left); PreOrder(root->right); } // 二叉树的中序遍历 void InOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } // 左 根 右 InOrder(root->left); printf("%d ", root->data); InOrder(root->right); } // 二叉树的后序遍历 void PostOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } // 左 右 根 PostOrder(root->left); PostOrder(root->right); printf("%d ", root->data); } // 二叉树的结点个数 int TreeNodeSize(BTNode* root) { // +1 是算上自己为一个结点 return root == NULL ? 0 : TreeNodeSize(root->left) + TreeNodeSize(root->right) + 1; } // 二叉树的叶子个数 int TreeLeafSize(BTNode* root) { // 如果该结点为 NULL ， 说明不是叶子结点，直接返回 0 if (root == NULL) return 0; // 如果该结点的左孩子和右孩子都为 NULL ，说明该结点为叶子结点，返回 1 if (root->left == NULL && root->right == NULL) return 1; // 递归左子树和右子树，统计左右子树的叶子结点 return TreeLeafSize(root->left) + TreeLeafSize(root->right); } // 二叉树的高度（深度） int TreeHeight(BTNode* root) { // 分治思想 // 如果该节点为空，没有高度，返回0 if (root == NULL) return 0; // 递归统计左右子树的高度 int leftheight = TreeHeight(root->left); int rightheight = TreeHeight(root->right); // 返回左右子树高度大小大的那个并加一，加一是加上该结点的高度1 return leftheight > rightheight ? leftheight + 1 : rightheight + 1; } // 二叉树第K层的结点个数 int TKLevelNodeSize(BTNode* root, int k) { // 如果到达第K层之前或者到达第K层该结点为NULL，直接返回0 //（说明不是第K层的结点或者在第K层为NULL） if (root == NULL) return 0; // 如果k减到1了，说明到达第K层了，此时该结点有效，应计数1 if (k == 1) return 1; return TKLevelNodeSize(root->left, k - 1) + TKLevelNodeSize(root->right, k - 1); } // 二叉树结点数据的查找 BTNode* TreeDataFind(BTNode* root, BTDataType x) { if (root == NULL) return NULL; if (root->data == x) return root; BTNode* lret = TreeDataFind(root->left, x); if (lret) return lret; BTNode* rret = TreeDataFind(root->right, x); if (rret) return rret; return NULL; } // 层序遍历，利用队列来操作 void LevelOrder(BTNode* root) { // 队列的每一个数据是一个树的结点 Que q; QInit(&q); // 如果根节点不为NULL就入队列 if (root) QPush(&q, root); // 队列不为空就继续 while (!QEmpty(&q)) { // 取队头元素（树的结点） BTNode* front = QFront(&q); // 出队列是释放队头的空间，在队头存放的树的结点没有被释放 QPop(&q); // 打印树结点中的数据 printf("%d ", front->data); // 如果该队头树结点的左孩子不为空就入队列 if (front->left) QPush(&q, front->left); // 如果该对头树节点的右孩子不为空就入队列 if (front->right) QPush(&q, front->right); } printf("\n"); // 记得销毁队列噢，防止内存泄漏 QDestroy(&q); } // 判断该二叉树是否为完全二叉树 bool BTComplate(BTNode* root) { Que q; QInit(&q); // 如果root不为NULL就入队列 if (root) QPush(&q, root); while (!QEmpty(&q)) { // 取队头元素，就是一个树的结点 BTNode* front = QFront(&q); QPop(&q); // 如果当前结点是NULL，说明前面每层连续的有效结点都出队列了，直接跳出循环 if (front == NULL) break; // 入front结点的左孩子和右孩子，NULL也入 QPush(&q, front->left); QPush(&q, front->right); } // 如果队列不为NULL，接下来就是判断的重要一步了 // 根据完全二叉树的性质，当前面每层连续的有效结点都走完时 // 剩下队列里的元素如果都是NULL就说明该二叉树是一棵完全二叉树 // 如果有一个结点不为NULL，那么就说明该二叉树不是完全二叉树 while (!QEmpty(&q)) { BTNode* front = QFront(&q); QPop(&q); if (front) { // 如果找到一个有效结点，就说明该二叉树不是完全二叉树，直接返回false // 返回前记得销毁队列噢 QDestroy(&q); return false; } } // 如果前面循环走完，说明符合完全二叉树的性质，最后返回true // 返回前记得销毁队列噢 QDestroy(&q); return true; } // 二叉树的销毁 // 注意一定是要通过后续遍历来销毁 // 因为后序遍历是 左 右 根 ，销毁左右再销毁根 // 这样能够递归返回回去 void BTDestroy(BTNode* root) { if (root == NULL) return; BTDestroy(root->left); BTDestroy(root->right); // 释放（返还）root指向的结点的空间 free(root); } int main() { BTNode* root = BuyTree(); PreOrder(root); printf("\n"); InOrder(root); printf("\n"); PostOrder(root); printf("\n"); printf("TreeNodeSize = %d\n", TreeNodeSize(root)); printf("TreeLeafSize = %d\n", TreeLeafSize(root)); printf("TreeHeight = %d\n", TreeHeight(root)); printf("TreeKNodeSize = %d\n", TKLevelNodeSize(root, 3)); printf("TreeFindData = %d\n", TreeDataFind(root, 6)->data); LevelOrder(root); if (BTComplate(root)) printf("Full binary tree!\n"); else printf("Not full binary tree!\n"); BTDestroy(root); return 0; }
☑️写在最后
💝回顾上文，其中的分治思想值得我们探讨。普通二叉树学完之后，初阶的数据结构就告一段落了，整体来说，初阶数据结构还是不难的，掌握其之后，我相信应付学校的考试那是绰绰有余。后面我会给大家带来高阶数据结构的文章，大家准备好接招吧嘿嘿！
❤️🔥后续将会继续输出有关数据结构与算法的文章，你们的支持就是我写作的最大动力！
感谢阅读本小白的博客，错误的地方请严厉指出噢~
