函数一 求二叉树叶节点的个数
这里要求我们统计叶节点的个数
我们想想 怎么统计呢？
还是老规矩 先上图
首先我们怎么判断叶节点呢？
如果这个节点它的左孩子和右孩子都是空指针
那么它就是一个叶节点
所以说当我们遇到左右节点都是空的时候返回一个一
核心代码表示如下
int BinaryTreeLeafSize(BTnode* root) { // 判断极限值 if (root==NULL) { return 0; } if (root->left==NULL && root->right==NULL) { return 1; } // 如果不是极限值怎么办 return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right); }
接下来让我们测试下
可以完美运行
我们来看看节点个数是不是4
确实是4没错 下一题！
函数二 求二叉树第K层的节点个数
还是一样 我们假设 K就是等于一
如果说是一个空数的话就返回0
如果说有值的话就返回一个1就可以
假设这个这层既不为空 又不是第K层的话 那么就说明第K层肯定是子树下面
那么就说明是左右子树的第（K-1）层
那么只将它们相加并且返回它们的值就好了
核心代码表示如下
int BinaryTreeLevelKSize(BTnode* root, int k) { // 极限情况 K=1 if (root==NULL) { return 0; } if (k==1) { return 1; } // 说明这棵树的节点在root节点下面 // 转化为求子节点的k-1节点问题 return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1); }
我们来看看结果怎么样
符合预期
函数三 求二叉树的深度
这里还是一样 我们先来看图
我们先来看第极限的情况
假如我们的本身就是一个空树的话 我们可以直接返回0
如果不是空树的话我们可以寻找我们的左子树和右子树中的较大值（一样大返回哪一个都可以）
将它们加一后返回就可以
核心代码如下
int BinaryTreeHight(BTnode* root) { // 极限情况 if (root==NULL) { return 0; } // 后面的情况 int left = BinaryTreeHight(root->left); int right = BinaryTreeHight(root->right); return left > right ? left + 1 : right + 1; }
还是一样我们来看看效果
深度是4确实没错
函数四 求某个值为X的节点
还是一样 我们首先考虑极限情况
假设值就在根上
那么我们直接返回根的位置就好了
否则的话我们就往左边右边子树遍历
我们来看看核心代码
BTnode* BinaryTreeFind(BTnode* root, BTdate x) { // 极限情况 if (root==NULL) { return NULL; } if (root->date==x) { return root; } // 找左子树 BTnode* left = BinaryTreeFind(root->left, x); if (left) { return left; } // 找右子树 BTnode* right = BinaryTreeFind(root->left, x); if (right) { return right; } // 都没找到 return NULL; }
我们发现这里可以找出来了
以上就是本篇博客的全部内容啦 由于博主才疏学浅 所以难免会出现纰漏 希望大佬们看到错误之后能够
不吝赐教 在评论区或者私信指正 博主一定及时修正
那么大家下期再见咯
