🔥个人主页：@草莓熊Lotso

🎬作者简介：C++研发方向学习者

📖个人专栏： 《C语言》 《数据结构与算法》《C语言刷题集》《Leetcode刷题指南》

⭐️人生格言：生活是默默的坚持，毅力是永久的享受。  

前言： 通过前面几篇博客我们已经完成了前中后序的接口实现，我们现在开始需要进行其它二叉树常用方法的实现，比如二叉树节点个数，叶子节点个数等。还是和之前一样分部分实现，最后再展示全部的代码。

---

目录

一.求二叉树节点个数

代码实现： 

test.c： 

二.求二叉树叶子节点个数

代码实现：

test.c： 

 三.求二叉树第k层节点个数

代码实现： 

test.c： 

 四.求二叉树的深度/高度

 代码实现：

test.c： 

 五.二叉树查找值为x的节点

代码实现：

test.c：

 六.二叉树的销毁 

代码实现：

 七.代码展现

Tree.h：

Tree.c：

test.c：

---

一.求二叉树节点个数

--我们先来实现一个求二叉树的节点个数的接口，在正式开始之前我们先把上次写的代码里的test.c中创建树的代码优化一下，这样方便后续操作

#include"Tree.h"BTNode* buyNode(char x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}
BTNode* CreateTree()
{BTNode* nodeA = buyNode('A');BTNode* nodeB = buyNode('B');BTNode* nodeC = buyNode('C');BTNode* nodeD = buyNode('D');BTNode* nodeE = buyNode('E');BTNode* nodeF = buyNode('F');nodeA->left = nodeB;nodeA->right = nodeC;nodeB->left = nodeD;nodeC->left = nodeE;nodeC->right = nodeF;return nodeA;
}void test1()
{BTNode* root = CreateTree();//前中后序遍历//PreOrder(root);//InOrder(root);//PostOrder(root);
}int main()
{test1();return 0;
}

--优化完之后，我们就可以开始实现求二叉树节点个数的接口了 

•  二叉树结点个数=根节点+左子树结点个数+右子树结点个数

代码实现： 

// 二叉树结点个数=根节点+左子树节点个数+右子树节点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

图示如下：

test.c： 

#include"Tree.h"BTNode* buyNode(char x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}
BTNode* CreateTree()
{BTNode* nodeA = buyNode('A');BTNode* nodeB = buyNode('B');BTNode* nodeC = buyNode('C');BTNode* nodeD = buyNode('D');BTNode* nodeE = buyNode('E');BTNode* nodeF = buyNode('F');nodeA->left = nodeB;nodeA->right = nodeC;nodeB->left = nodeD;nodeC->left = nodeE;nodeC->right = nodeF;return nodeA;
}void test1()
{BTNode* root = CreateTree();//前中后序遍历//PreOrder(root);//InOrder(root);//PostOrder(root);//二叉树结点个数printf("Size: %d\n", BinaryTreeSize(root));
}int main()
{test1();return 0;
}

--测试完成，打印出来没有问题，退出码为0 

---

二.求二叉树叶子节点个数

--二叉树的叶子节点就是左右孩子都为空的节点

• 二叉树叶子节点个数=左子树叶子节点个数+右子树叶子节点个数

代码实现：

// 二叉树叶子结点个数=左子树叶子节点个数+右子树节点个数
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);
}

图示如下： 

test.c： 

#include"Tree.h"BTNode* buyNode(char x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}
BTNode* CreateTree()
{BTNode* nodeA = buyNode('A');BTNode* nodeB = buyNode('B');BTNode* nodeC = buyNode('C');BTNode* nodeD = buyNode('D');BTNode* nodeE = buyNode('E');BTNode* nodeF = buyNode('F');nodeA->left = nodeB;nodeA->right = nodeC;nodeB->left = nodeD;nodeC->left = nodeE;nodeC->right = nodeF;return nodeA;
}void test1()
{BTNode* root = CreateTree();//前中后序遍历//PreOrder(root);//InOrder(root);//PostOrder(root);//二叉树结点个数printf("Size: %d\n", BinaryTreeSize(root));//二叉树叶子结点个数printf("LeafSize: %d\n", BinaryTreeLeafSize(root));
}int main()
{test1();return 0;
}

--测试完成，打印没有问题，退出码为0

---

 三.求二叉树第k层节点个数

--当k==1时当前节点就是第k层节点

• 二叉树第k层节点个数=左子树第k-1层节点个数+右子树第k-1层节点个数

代码实现： 

// 二叉树第k层节点个数=左子树第K-1层节点个数+右子树第k-1层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL){return 0;}//判断是否为第k层if (k == 1){return 1;}//每次注意要k-1return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

图示如下： 

test.c： 

#include"Tree.h"BTNode* buyNode(char x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}
BTNode* CreateTree()
{BTNode* nodeA = buyNode('A');BTNode* nodeB = buyNode('B');BTNode* nodeC = buyNode('C');BTNode* nodeD = buyNode('D');BTNode* nodeE = buyNode('E');BTNode* nodeF = buyNode('F');nodeA->left = nodeB;nodeA->right = nodeC;nodeB->left = nodeD;nodeC->left = nodeE;nodeC->right = nodeF;return nodeA;
}void test1()
{BTNode* root = CreateTree();//前中后序遍历//PreOrder(root);//InOrder(root);//PostOrder(root);//二叉树结点个数printf("Size: %d\n", BinaryTreeSize(root));//二叉树叶子结点个数printf("LeafSize: %d\n", BinaryTreeLeafSize(root));//第k层节点个数printf("K Size: %d\n", BinaryTreeLevelKSize(root,3));
}int main()
{test1();return 0;
}

--测试完成，打印没有问题，退出码为0

---

 四.求二叉树的深度/高度

• 二叉树的高度=根节点+max(左子树的高度，右子树的高度)

 代码实现：

//二叉树的深度/高度=根节点+max(左子树高度，右子树高度)
int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}int leftdepth = BinaryTreeDepth(root->left);int rightdepth = BinaryTreeDepth(root->right);return 1 + (leftdepth > rightdepth ? leftdepth : rightdepth);
}

图示如下：

test.c： 

#include"Tree.h"BTNode* buyNode(char x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}
BTNode* CreateTree()
{BTNode* nodeA = buyNode('A');BTNode* nodeB = buyNode('B');BTNode* nodeC = buyNode('C');BTNode* nodeD = buyNode('D');BTNode* nodeE = buyNode('E');BTNode* nodeF = buyNode('F');nodeA->left = nodeB;nodeA->right = nodeC;nodeB->left = nodeD;nodeC->left = nodeE;nodeC->right = nodeF;return nodeA;
}void test1()
{BTNode* root = CreateTree();//前中后序遍历//PreOrder(root);//InOrder(root);//PostOrder(root);//二叉树结点个数printf("Size: %d\n", BinaryTreeSize(root));//二叉树叶子结点个数printf("LeafSize: %d\n", BinaryTreeLeafSize(root));//第k层节点个数printf("K Size: %d\n", BinaryTreeLevelKSize(root,3));//二叉树的深度/高度printf("Depth: %d\n", BinaryTreeDepth(root));
}int main()
{test1();return 0;
}

--测试完成，打印没有问题，退出码为0

---

 五.二叉树查找值为x的节点

--递归查找，找到了就返回当前节点，如果是在左子树中找到就直接返回，没找到继续来到右子树找，最好都没找到就返回NULL

代码实现：

// 二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode*leftroot = BinaryTreeFind(root->left, x);//如果leftroot不为空就是找到了直接返回if (leftroot){return leftroot;}//没找到就继续右子树找BTNode* rightroot = BinaryTreeFind(root->right, x);if (rightroot){return rightroot;}//都没找到就返回空return NULL;
}

图示如下： 

test.c：

#include"Tree.h"BTNode* buyNode(char x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}
BTNode* CreateTree()
{BTNode* nodeA = buyNode('A');BTNode* nodeB = buyNode('B');BTNode* nodeC = buyNode('C');BTNode* nodeD = buyNode('D');BTNode* nodeE = buyNode('E');BTNode* nodeF = buyNode('F');nodeA->left = nodeB;nodeA->right = nodeC;nodeB->left = nodeD;nodeC->left = nodeE;nodeC->right = nodeF;return nodeA;
}void test1()
{BTNode* root = CreateTree();//前中后序遍历//PreOrder(root);//InOrder(root);//PostOrder(root);//二叉树结点个数printf("Size: %d\n", BinaryTreeSize(root));//二叉树叶子结点个数printf("LeafSize: %d\n", BinaryTreeLeafSize(root));//第k层节点个数printf("K Size: %d\n", BinaryTreeLevelKSize(root,3));//二叉树的深度/高度printf("Depth: %d\n", BinaryTreeDepth(root));//二叉树查找值为x的结点BTNode* pos = BinaryTreeFind(root, 'E');if (pos){printf("找到了\n");}else {printf("没找到\n");}
}int main()
{test1();return 0;
}

--测试完成，找的到E，退出码为0

---

 六.二叉树的销毁 

--由于提前释放根节点无法找到其左右节点，所以我们得采用后续遍历的思想，最后处理根节点，

还有这里得传地址，后续的使用也需要注意一下写法。

代码实现：

// 二叉树销毁--采用后序遍历的思想
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestory(&(*root)->left);BinaryTreeDestory(&(*root)->right);free(*root);*root = NULL;
}

图示如下：

---

 七.代码展现

Tree.h：

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef char BTDataType;
typedef struct BinaryNode
{BTDataType data;struct BinaryNode* left;//左孩子struct BinaryNode* right;//右孩子
}BTNode;//前序遍历
void PreOrder(BTNode* root);//中序遍历
void InOrder(BTNode* root);//后序遍历
void PostOrder(BTNode* root);// 二叉树结点个数
int BinaryTreeSize(BTNode* root);// 二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root);// 二叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root);// 二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);// 二叉树销毁
void BinaryTreeDestory(BTNode** root);

Tree.c：

#include"Tree.h"//前序遍历
void PreOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}//根左右printf("%c ", root->data);PreOrder(root->left);PreOrder(root->right);
}//中序遍历
void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}//左根右InOrder(root->left);printf("%c ", root->data);InOrder(root->right);
}//后序遍历
void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}//左右根PostOrder(root->left);PostOrder(root->right);printf("%c ", root->data);
}// 二叉树结点个数=根节点+左子树节点个数+右子树节点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}// 二叉树叶子结点个数=左子树叶子节点个数+右子树节点个数
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);
}// 二叉树第k层节点个数=左子树第K-1层节点个数+右子树第k-1层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL){return 0;}//判断是否为第k层if (k == 1){return 1;}//每次注意要k-1return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}//二叉树的深度/高度=根节点+max(左子树高度，右子树高度)
int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}int leftdepth = BinaryTreeDepth(root->left);int rightdepth = BinaryTreeDepth(root->right);return 1 + (leftdepth > rightdepth ? leftdepth : rightdepth);
}// 二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode*leftroot = BinaryTreeFind(root->left, x);//如果leftroot不为空就是找到了直接返回if (leftroot){return leftroot;}//没找到就继续右子树找BTNode* rightroot = BinaryTreeFind(root->right, x);if (rightroot){return rightroot;}//都没找到就返回空return NULL;
}// 二叉树销毁--采用后序遍历的思想
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestory(&(*root)->left);BinaryTreeDestory(&(*root)->right);free(*root);*root = NULL;
}

test.c：

#include"Tree.h"BTNode* buyNode(char x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}
BTNode* CreateTree()
{BTNode* nodeA = buyNode('A');BTNode* nodeB = buyNode('B');BTNode* nodeC = buyNode('C');BTNode* nodeD = buyNode('D');BTNode* nodeE = buyNode('E');BTNode* nodeF = buyNode('F');nodeA->left = nodeB;nodeA->right = nodeC;nodeB->left = nodeD;nodeC->left = nodeE;nodeC->right = nodeF;return nodeA;
}void test1()
{BTNode* root = CreateTree();//前中后序遍历//PreOrder(root);//InOrder(root);//PostOrder(root);//二叉树结点个数printf("Size: %d\n", BinaryTreeSize(root));//二叉树叶子结点个数printf("LeafSize: %d\n", BinaryTreeLeafSize(root));//第k层节点个数printf("K Size: %d\n", BinaryTreeLevelKSize(root,3));//二叉树的深度/高度printf("Depth: %d\n", BinaryTreeDepth(root));//二叉树查找值为x的结点BTNode* pos = BinaryTreeFind(root, 'E');if (pos){printf("找到了\n");}else {printf("没找到\n");}// 二叉树销毁BinaryTreeDestory(&root);
}int main()
{test1();return 0;
}

---

往期回顾：

【数据结构初阶】--树和二叉树先导篇

【数据结构初阶】--二叉树(二)

【数据结构初阶】--二叉树(三)

【数据结构初阶】--二叉树(四)

结语：在这篇博客中我们一起实现了二叉树的大部分常用接口，后面还有一个判断是否为完全二叉树和一个层序遍历的实现。如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持。