目录摘要前置准备一二叉树节点的个数二叶子节点个数三第k层的节点个数四二叉树的深度/高度五总代码摘要本文使用递归求二叉树节点个数求叶子节点个数求第k层的节点个数附带递归展开图前置准备本文二叉树模型解释二叉树的创建详情可见本文递归实现 前/中/后序 遍历二叉树 的详细讲解-CSDN博客一二叉树节点的个数递归则必须有终态条件和递归部分其中的递归部分会不断的逼近终态条件两种写法终态条件当节点为NULL返回0递归部分节点不为NULL则递归调用TreeSize(左孩子)和TreeSize(右孩子)然后返回leftCount rightCount 1;解释①return rootNULL? 0:TreeSize(root-left)TreeSize(root-right)1;这是函数的返回语句使用了条件运算符也称为三元运算符。rootNULL检查传入的节点是否为空即检查树是否为空或者是否到达了叶节点的子节点。如果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也可以写作终态条件①当节点为NULLreturn 0②当节点的左右孩子为空则return 1代表该节点为叶子节点递归部分节点不为NULL也不为叶子节点则递归调用TreeLeafSize(左)TreeLeafSize(右)然后return 两个函数的值的和解释递归的大事化小思路即叶子结点总数 左子树的叶子节点右子树的叶子节点所以情况如下a一个节点是空返回0b一个节点不是空也不是叶子节点则向下递进c一个节点不是空且是叶子节点返回1如何判断是叶子节点-本身不为空且左右孩子都为空也就是前两个if都通过。递归图三第k层的节点个数最后的return也可以写作终态条件①当节点为NULLreturn 0②当K则return 1代表到达第k层且存在存在递归部分节点不为NULLK不等于1则递归调用TreeKLeverl(左)TreeKLeverl(右)然后return 两个函数的值的和解释①递归的大事化小思路即当前树的第 K 层 左子树的第K-1层 右子树的第K-1层也就是说求第3层求左子树的第2层右子树的第2层②所以情况如下a节点为空返回0b节点不为空k为1则返回1c节点不为空k不为1向下递进也就是说我们最后到底第k层的时候也就是if中的K1的时候会对该k层的32的左子树 NULL2的右子树 54的左子树6(4的右子树) 进行判断空就是0非空且k1为1而且K一定为1因为已经到了第K层。递归图四二叉树的深度/高度终态条件当节点为NULLreturn 0递归部分节点不为NULL则递归调用BinaryTreeDepth(左)BinaryTreeDepth(右)得到两个函数的值取左右子树深度较大值max然后return max1 这个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 [ 声明 ] 由于笔者水平有限文中难免有疏漏或不妥之处还望读者不吝赐教
二叉树递归求节点数/叶子节点数/第k层的节点数/深度
发布时间：2026/6/2 21:10:10
目录摘要前置准备一二叉树节点的个数二叶子节点个数三第k层的节点个数四二叉树的深度/高度五总代码摘要本文使用递归求二叉树节点个数求叶子节点个数求第k层的节点个数附带递归展开图前置准备本文二叉树模型解释二叉树的创建详情可见本文递归实现 前/中/后序 遍历二叉树 的详细讲解-CSDN博客一二叉树节点的个数递归则必须有终态条件和递归部分其中的递归部分会不断的逼近终态条件两种写法终态条件当节点为NULL返回0递归部分节点不为NULL则递归调用TreeSize(左孩子)和TreeSize(右孩子)然后返回leftCount rightCount 1;解释①return rootNULL? 0:TreeSize(root-left)TreeSize(root-right)1;这是函数的返回语句使用了条件运算符也称为三元运算符。rootNULL检查传入的节点是否为空即检查树是否为空或者是否到达了叶节点的子节点。如果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也可以写作终态条件①当节点为NULLreturn 0②当节点的左右孩子为空则return 1代表该节点为叶子节点递归部分节点不为NULL也不为叶子节点则递归调用TreeLeafSize(左)TreeLeafSize(右)然后return 两个函数的值的和解释递归的大事化小思路即叶子结点总数 左子树的叶子节点右子树的叶子节点所以情况如下a一个节点是空返回0b一个节点不是空也不是叶子节点则向下递进c一个节点不是空且是叶子节点返回1如何判断是叶子节点-本身不为空且左右孩子都为空也就是前两个if都通过。递归图三第k层的节点个数最后的return也可以写作终态条件①当节点为NULLreturn 0②当K则return 1代表到达第k层且存在存在递归部分节点不为NULLK不等于1则递归调用TreeKLeverl(左)TreeKLeverl(右)然后return 两个函数的值的和解释①递归的大事化小思路即当前树的第 K 层 左子树的第K-1层 右子树的第K-1层也就是说求第3层求左子树的第2层右子树的第2层②所以情况如下a节点为空返回0b节点不为空k为1则返回1c节点不为空k不为1向下递进也就是说我们最后到底第k层的时候也就是if中的K1的时候会对该k层的32的左子树 NULL2的右子树 54的左子树6(4的右子树) 进行判断空就是0非空且k1为1而且K一定为1因为已经到了第K层。递归图四二叉树的深度/高度终态条件当节点为NULLreturn 0递归部分节点不为NULL则递归调用BinaryTreeDepth(左)BinaryTreeDepth(右)得到两个函数的值取左右子树深度较大值max然后return max1 这个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 [ 声明 ] 由于笔者水平有限文中难免有疏漏或不妥之处还望读者不吝赐教
