节点个数以及高度等
【摘要】 ❓ 实现以下接口 ❔// 二叉树节点个数int BinaryTreeSize(BTNode* root);// 二叉树叶子节点个数int BinaryTreeLeafSize(BTNode* root);// 二叉树第k层节点个数int BinaryTreeLevelKSize(BTNode* root, int k);//二叉树深度/高度int BinaryTreeDepth(BTNode...
❓ 实现以下接口 ❔
// 二叉树节点个数
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);
❗ 实现代码 ❕
❤ BinaryTreeSize ❤
🔑 核心思想1 :使用前序 || 中序 || 后序遍历,全局变量记录
❌ 但是以下代码有 Bug :如果采用前序重复遍历 2 次
✔ 经查,问题出在全局变量上,这里只需要在第 2 次遍历时置 0 即可
⚠ 在以后的知识面更大后,其实你会发现这种操作还有线程安全的问题
🔑 核心思想 2:函数使用带返回值的方式,其内部的递归本质上是一个后序遍厉
❤ BinaryTreeLeafSize ❤
🔑 核心思想 :以 left 和 right 为标志,如果都为 NULL,则累加
❤ BinaryTreeLevelKSize ❤
🔑 核心思想 :求当前树的第 k 层 = 左子树的第 k - 1 层 + 右子树的第 k - 1 层 (当 k = 1 时,说明此层就是目标层)
❤ BinaryTreeDepth ❤
🔑 核心思想 :当前树的深度 = max (左子树的深度,右子树的深度) + 1
❤ BinaryTreeFind ❤
🔑 核心思想 :
1、先判断是不是当前节点,是就返回;
2、先去左树找,找到就返回
3、左树没找到,再找右树
#include<stdio.h>
#include<stdlib.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
BTNode* BuyNode(BTDataType x)
{
BTNode* node = malloc(sizeof(BTNode));
node->data = x;
node->left = NULL;
node->right = NULL;
return node;
}
// 二叉树节点个数
//1、前序递归遍历
int sz1 = 0;
void BinaryTreeSize1(BTNode* root)
{
if (root == NULL)
return;
else
sz1++;
BinaryTreeSize1(root->left);
BinaryTreeSize1(root->right);
}
//2、中序递归遍历
int sz2 = 0;
void BinaryTreeSize2(BTNode* root)
{
if (root == NULL)
return;
BinaryTreeSize2(root->left);
if (root != NULL)
sz2++;
BinaryTreeSize2(root->right);
}
//3、后序递归遍历
int sz3 = 0;
void BinaryTreeSize3(BTNode* root)
{
if (root == NULL)
return;
BinaryTreeSize3(root->left);
BinaryTreeSize3(root->right);
if (root != NULL)
sz3++;
}
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
return root == NULL ? 0 : 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
//二叉树叶子节点个数
int BinaryTreeLeaSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
else if (root->left == NULL && root->right == NULL)
{
return 1;
}
else
{
return BinaryTreeLeaSize(root->left) + BinaryTreeLeaSize(root->right);
}
}
//二叉树第k层节点个数
int BinaryTreeLeveLKSize(BTNode* root, int k)
{
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
return BinaryTreeLeveLKSize(root->left, k - 1) + BinaryTreeLeveLKSize(root->right, k - 1);
}
//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root)
{
if (root == NULL)
{
return 0;
}
int leftDepth = BinaryTreeDepth(root->left);
int rightDepth = BinaryTreeDepth(root->right);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
{
return NULL;
}
if (root->data == x)
{
return root;
}
BTNode* retleft = BinaryTreeFind(root->left, x);
if (retleft)
{
return retleft;
}
BTNode* retright = BinaryTreeFind(root->right, x);
if (retright)
{
return retright;
}
return NULL;
}
BTNode* CreatBinaryTree()
{
BTNode* node1 = BuyNode('A');
BTNode* node2 = BuyNode('B');
BTNode* node3 = BuyNode('C');
BTNode* node4 = BuyNode('D');
BTNode* node5 = BuyNode('E');
BTNode* node6 = BuyNode('F');
node1->left = node2;
node1->right = node3;
node2->left = node4;
node3->left = node5;
node3->right = node6;
return node1;
}
void PreOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%c ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}
int main()
{
BTNode* root = CreatBinaryTree();
//遍厉前中后序输出二叉树节点的个数
BinaryTreeSize1(root);
BinaryTreeSize2(root);
BinaryTreeSize3(root);
printf("BinaryTreeSize:%d\n", sz1);
printf("BinaryTreeSize:%d\n", sz2);
printf("BinaryTreeSize:%d\n", sz3);
printf("-----------------cur-----------------\n");
//优化二叉树节点的个数
printf("BinaryTreeSize:%d\n", BinaryTreeSize(root));
printf("-----------------cur-----------------\n");
//二叉树叶子节点个数
printf("BinaryTreeLeaSize:%d\n", BinaryTreeLeaSize(root));
printf("-----------------cur-----------------\n");
//二叉树第k层节点个数
printf("BinaryTreeLeveLKSize:%d\n", BinaryTreeLeveLKSize(root, 3));
printf("-----------------cur-----------------\n");
//二叉树的深度/高度
printf("BinaryTreeDepth:%d\n", BinaryTreeDepth(root));
printf("-----------------cur-----------------\n");
// 二叉树查找值为x的节点
BTNode* ret = BinaryTreeFind(root, 'D');
if(ret)
{
printf("找到了\n");
}
else
{
printf("没找到\n");
}
PreOrder(root);
return 0;
}
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)