4.2.4 层序遍历实现代码
对队列还有不清楚的同学可以看看这篇文章，队列是一篇完整的文章哦，点后面文字跳转，https://blog.csdn.net/Ljy_cx_21_4_3/article/details/130739681
// 层序遍历 void BinaryTreeLevelOrder(BTNode* root) { Queue q; QueueInit(&q); if (root) QueuePush(&q, root); while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q);//先将队头元素记下来 QueuePop(&q); printf("%c ", front->data); if (front->left) QueuePush(&q, front->left); if (front->right) QueuePush(&q, front->right); } QueueDestroy(&q); } int main() { char a[] = { '1','2','3',NULL,NULL,'4',NULL,'5','6',NULL,NULL,NULL,NULL }; int i = 0; BTNode* root = BinaryTreeCreate(a, &i); BinaryTreeLevelOrder(root); printf("\n"); return 0; }
4.3 节点个数
4.3.1 二叉树节点个数 -- BinaryTreeSize
思想：我们知道，二叉树是分为根节点，左子树，右子树三部分的。所以我们要求二叉树的节点总个数时，只需要求左子树，右子树的节点个数，再加上根节点，就计算出了二叉树的节点个数。
我们举个例子来类比一下这个思想：
如果一个高中学校的校长不知道学校有多少名学生，现在校长要查一下学校现有多少名学生时，校长不可能每个班去数人数，这效率太低了。校长这时将任务分给三个年级组长，各年级组长去统计各年级人数，最后汇总给校长，加起来就好了。年级组长也纷纷效仿，让每个班的班主任去统计，班主任将任务派给各班班长，班长数完人一级一级的汇报上去，最后到校长那里，校长只需要将年级组长汇报上来的人数加起来即可。这种方式其实就是分治思想，分而治之，效率不仅提高了，出错率也会大大降低。
我们画图来明确一下:
实现代码：
int BinaryTreeSize(BTNode* root) { if (NULL == root) return 0; //分治算法 return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1; //简化 //return root == NULL ? 0 : BinaryTreeSize(root->left) // + BinaryTreeSize(root->right) + 1;//简化代码 }
递归图：
结果展示：
4.3.2 二叉树叶子节点个数 -- BinaryTreeLeafSize
思想：在统计叶子节点的时候用到的思路依旧是分治思想，左子树的叶子节点+右子树的叶子节点就是整个二叉树的叶子节点。 叶子节点即就是度为 0 的节点，因此判断条件就是节点的左右孩子都为空。
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); }
运行结果：
4.3.3 二叉树第k层节点个数 -- BinaryTreeLevelKSize
思想：仍旧是分治的思想，因为要计算二叉树的第K层节点个数，因此只要计算出左右子树的 k-1 层的节点个数即可。
这里分三种情况：
1.当 k<0 时，返回 0；
2.当 k=1 时，第一层就一个根节点，返回 1；
3.当 k>1 时，按照思想往下递归。
实现代码：
int BinaryTreeLevelKSize(BTNode* root, int k) { assert(k > 0); if (NULL == root) return 0; if (1 == k) return 1; return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1); }
运行结果：
4.4 树的高度 -- BTreeHeight
思想：二叉树的高度我们依旧使用分治思想，求出左数高度与右数高度，分别 +1（加上根节点这一层），哪个值大哪个就是树的高度。
实现代码：
int BTreeHeight(BTNode* root) { if (NULL == root) return 0; int leftH = BTreeHeight(root->left); int rightH = BTreeHeight(root->right); return leftH > rightH ? leftH + 1 : rightH + 1; }
4.5 二叉树查找值为x的节点 -- BinaryTreeFind
思想：依旧是分治思想，递归实现，要找节点值为x的节点，我们先看根节点是不是，再递归左右子树的每一个基点。
实现代码：
BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (NULL == root) return NULL; if (root->data == x) return root; BTNode* ret1 = BinaryTreeFind(root->left, x); if (ret1) return ret1; BTNode* ret2 = BinaryTreeFind(root->right, x); if (ret2) return ret2; return NULL; }
运行结果：
