企业官网建设流程全解析

目录

摘要：

前置准备：

一：二叉树节点的个数

二：叶子节点个数

三：第k层的节点个数

四：二叉树的深度/高度

五：总代码

摘要：

本文使用递归求二叉树节点个数，求叶子节点个数，求第k层的节点个数，附带递归展开图

前置准备：

本文二叉树模型：

解释：二叉树的创建，详情可见本文：递归实现 前/中/后序 遍历二叉树 的详细讲解-CSDN博客

一：二叉树节点的个数

💡：递归，则必须有终态条件和递归部分，其中的递归部分会不断的逼近终态条件

两种写法：

终态条件：当节点为NULL，返回0

递归部分：节点不为NULL，则递归调用TreeSize(左孩子)和TreeSize(右孩子)，然后返回leftCount + rightCount + 1;

解释：

①：return root==NULL? 0:TreeSize(root->left)+TreeSize(root->right)+1;：

• 这是函数的返回语句，使用了条件运算符（也称为三元运算符）。
• root==NULL：检查传入的节点是否为空（即检查树是否为空或者是否到达了叶节点的子节点）。
• 如果root为NULL（意味着当前子树为空），则返回0，因为空树没有节点，数量为0。
• 如果root不为NULL，则递归计算左子树和右子树的节点数量，并将它们相加，然后加上当前节点（root），因此是TreeSize(root->left) + TreeSize(root->right) + 1。

②：

递归的工作原理如下：

• 递归的基本情况（停止条件）：当递归到叶子节点的子节点时（即遇到NULL），返回0。
• 递归的递推情况：对于非空的树，函数递归地计算左子树和右子树的大小，将这两个值相加，并加上当前节点（root）本身。
• 递归最终会遍历二叉树中的每一个节点，并将它们全部计数一次。

③：

一种错的书写方式:

原因：表达式能用在三目中，而语句不能。return 0 这是一个语句，而0是一个表达式。

递归图：

一些错误的思路：

①：创建size变量，传值作为TreeSize的参数，每次遍历到非空节点则size++，最后size就是节点的个数，❌️！往下递进的过程size的确会变大，但是每个函数中的size不是同一块内存，这就导致回归的过程，size仍是之前函数的值，最后size仍为1

②：使用前中后序的递归代码，将打印语句换成size++，❌️！这种方法虽然仍然采用值传递的方法，但是因为不会把size值回归到上级，所以最后的size的确为节点个数，但是第二次调用TreeSize函数时，上一次调用TreeSize函数的结果仍存储在size中，所以该方法❌️！

③：size采用址传递作为TreeSize的参数，❌️！址传递只是让所有的size都是同一个值，但是仍会出现第二次调用TreeSize时，size仍为第一次调用TreeSize时的值！

④：💡正确方法：递归，二叉树结点的个数 = 1+左子树节点个数+右子树节点个数

二：叶子节点个数

最后的return，也可以写作：

终态条件：

①：当节点为NULL，return 0

②：当节点的左右孩子为空，则return 1，代表该节点为叶子节点

递归部分：节点不为NULL，也不为叶子节点，则递归调用TreeLeafSize(左)+TreeLeafSize(右)，然后return 两个函数的值的和

解释递归的大事化小思路即：叶子结点总数= 左子树的叶子节点+右子树的叶子节点

所以情况如下

a：一个节点是空，返回0

b：一个节点不是空，也不是叶子节点，则向下递进

c：一个节点不是空，且是叶子节点，返回1

如何判断是叶子节点？->本身不为空且左右孩子都为空，也就是前两个if都通过。

递归图：

三：第k层的节点个数

最后的return，也可以写作：

终态条件：

①：当节点为NULL，return 0

②：当K==，则return 1，代表到达第k层，且存在存在

递归部分：节点不为NULL，K不等于1，则递归调用TreeKLeverl(左)+TreeKLeverl(右)，然后return 两个函数的值的和

解释：

①：递归的大事化小思路即：

当前树的第 K 层 = 左子树的第K-1层 + 右子树的第K-1层

也就是说：求第3层=求左子树的第2层+右子树的第2层

②：所以情况如下

a：节点为空，返回0

b：节点不为空，k为1，则返回1

c：节点不为空，k不为1，向下递进

也就是说：我们最后到底第k层的时候，也就是if中的K=1的时候，会对该k层的3（2的左子树） NULL（2的右子树） 5（4的左子树）6(4的右子树) 进行判断，空就是0，非空且k=1为1，而且K一定为1，因为已经到了第K层。

递归图：

四：二叉树的深度/高度

终态条件：当节点为NULL，return 0

递归部分：节点不为NULL，，则递归调用BinaryTreeDepth(左)+BinaryTreeDepth(右)，得到两个函数的值，取左右子树深度较大值max，然后return max+1 ，这个1代表本层的深度

递归图：

五：总代码

#include <stdio.h> #include <stdlib.h> #include <assert.h> // 1. 二叉树节点定义 typedef struct BinaryTreeNode { int val; struct BinaryTreeNode* left; struct BinaryTreeNode* right; } BTNode; // 2. 创建新节点 BTNode* BuyNode(int x) { BTNode* newNode = (BTNode*)malloc(sizeof(BTNode)); if (newNode == NULL) { perror("malloc fail"); exit(-1); } newNode->val = x; newNode->left = NULL; newNode->right = NULL; return newNode; } // 3. 求第 k 层的节点个数（根为第 1 层） int TreeLevel(BTNode* root, int k) { assert(k > 0); // k 必须为正整数 if (root == NULL) { return 0; } if (k == 1) { // 到达目标层 return 1; } // 递归：左子树第 (k-1) 层 + 右子树第 (k-1) 层 return TreeLevel(root->left, k - 1) + TreeLevel(root->right, k - 1); } //// 3. 求第 k 层的节点个数 //int TreeLevel(BTNode* root, int k) { // assert(k > 0); // k 必须为正整数 // // if (root == NULL) { // return 0; // } // // if (k == 1) { // 到达目标层 // return 1; // } // // // 计算左子树中第 (k-1) 层的节点数（相对于左子树根） // int left_k_minus_1_count = TreeLevel(root->left, k - 1); // // 计算右子树中第 (k-1) 层的节点数（相对于右子树根） // int right_k_minus_1_count = TreeLevel(root->right, k - 1); // // // 当前树第 k 层的节点数 = 左子树第 (k-1) 层节点数 + 右子树第 (k-1) 层节点数 // return left_k_minus_1_count + right_k_minus_1_count; //} // 4. 求叶子节点个数（左右孩子都为空） int TreeLeafSize(BTNode* root) { if (root == NULL) { return 0; } // 如果是叶子节点（左右都为空） if (root->left == NULL && root->right == NULL) { return 1; } // 递归：左子树叶子数 + 右子树叶子数 return TreeLeafSize(root->left) + TreeLeafSize(root->right); } //4. 求叶子节点个数 //int TreeLeafSize(BTNode* root) { // if (root == NULL) { // return 0; // 空树没有叶子 // } // // if (root->left == NULL && root->right == NULL) { // return 1; // 找到一个叶子节点 // } // // // 递归分解：计算左右子树的叶子数 // int leftLeafCount = TreeLeafSize(root->left); // int rightLeafCount = TreeLeafSize(root->right); // // // 合并结果：当前树的叶子数 = 左子树叶子数 + 右子树叶子数 // return leftLeafCount + rightLeafCount; //} // 5. 求总节点个数 int TreeSize(BTNode* root) { // 三元运算符写法（简洁） return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1; } // 5. 求总节点个数 //int TreeSize(BTNode* root) { // if (root == NULL) { // 递归的终止条件 // return 0; // } // else { // 递归 // // 当前节点不为空，则总节点数 = 左子树节点数 + 右子树节点数 + 1（当前节点） // int leftCount = TreeSize(root->left); // int rightCount = TreeSize(root->right); // return leftCount + rightCount + 1; // } //} // 6. ⼆叉树的深度/⾼度 int BinaryTreeDepth(BTNode* root) { // 基础情况：如果根节点为空，则深度为 0 if (root == NULL) { return 0; } // 递归计算左子树的深度 int left_depth = BinaryTreeDepth(root->left); // 递归计算右子树的深度 int right_depth = BinaryTreeDepth(root->right); // 当前树的深度 = max(左子树深度, 右子树深度) + 1 (当前节点层) // 需要比较左右子树深度，取较大者 if (left_depth > right_depth) { return left_depth + 1; } else { return right_depth + 1; // 包括 left_depth == right_depth 的情况 } // 或者使用三元运算符 (ternary operator) 来简化比较和返回： // return (left_depth > right_depth ? left_depth : right_depth) + 1; } // 7. （可选）释放内存 void DestroyTree(BTNode* root) { if (root == NULL) return; DestroyTree(root->left); DestroyTree(root->right); free(root); } // 8. 主函数：构建树并测试所有功能 int main() { // 构建如下树： // 1 // / \ // 2 4 // / / \ // 3 5 6 BTNode* n1 = BuyNode(1); BTNode* n2 = BuyNode(2); BTNode* n3 = BuyNode(3); BTNode* n4 = BuyNode(4); BTNode* n5 = BuyNode(5); BTNode* n6 = BuyNode(6); n1->left = n2; n1->right = n4; n2->left = n3; n4->left = n5; n4->right = n6; printf("=== 统计信息 ===\n"); printf("总节点数: %d\n", TreeSize(n1)); printf("叶子节点数: %d\n", TreeLeafSize(n1)); printf("第 1 层节点数: %d\n", TreeLevel(n1, 1)); // 应为 1 printf("第 2 层节点数: %d\n", TreeLevel(n1, 2)); // 应为 2 (2, 4) printf("第 3 层节点数: %d\n", TreeLevel(n1, 3)); // 应为 3 (3, 5, 6) printf("第 4 层节点数: %d\n", TreeLevel(n1, 4)); // 应为 0 printf("二叉树高度为: %d\n", BinaryTreeDepth(n1)); // 释放内存 DestroyTree(n1); return 0; }

📌 [ 作者 ] shylyly
📃 [ 首次发布 ] 2024.8.19
❌ [ 最新修改 ] 2026.6.1
📜 [ 声明 ] 由于笔者水平有限，文中难免有疏漏或不妥之处，还望读者不吝赐教