【数据结构初阶】--二叉树(五)
🔥个人主页：@草莓熊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;
}往期回顾：
【数据结构初阶】--树和二叉树先导篇
【数据结构初阶】--二叉树(二)
【数据结构初阶】--二叉树(三)
【数据结构初阶】--二叉树(四)
结语：在这篇博客中我们一起实现了二叉树的大部分常用接口，后面还有一个判断是否为完全二叉树和一个层序遍历的实现。如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持。