文章目录
前言
👧个人主页：@小沈熬夜秃头中୧⍤⃝❅
😚小编介绍：欢迎来到我的乱七八糟小星球🌝
📋专栏：数据结构
🔑本章内容：手撕链式二叉树
送给各位💌：成为更好的自己才是应该做的事
记得 评论📝 +点赞👍 +收藏😽 +关注💞哦~
提示：以下是本篇文章正文内容，下面案例可供参考
🌟一、二叉树链式结构的实现
🌏1.1 二叉树叶子节点个数
💫代码：
int BTreeLeafSize(BTNode* root)
{
if (root == NULL)
return 0;
if (root->left == NULL && root->right == NULL)
return 1;
return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
}
💫流程图：
🌏1.2 二叉树的高度
💫第一种写法(不支持)：
📒代码：
int BTreeHeight(BTNode* root)
{
if (root == NULL)
return 0;
return BTreeHeight(root->left) > BTreeHeight(root->right) ?
BTreeHeight(root->left) + 1 : BTreeHeight(root->right) + 1;
}
📒流程图：
由图可知，每次比较完后并没有记录数据而是再次调用当树跃高底层最大的那个函数调用的次数就越多，所以这种方法虽然对但是耗时太长，而底层也就变成了所谓的天选打工人
💫第二种写法：
📒代码：
int BTreeHeight(BTNode* root)
{
if (root == NULL)
return 0;
int leftHeight = BTreeHeight(root->left);
int rightHeight = BTreeHeight(root->right );
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
📒流程图：
每次调用都记录上数据，这样比较完直接返回大的那个+1；
🌏1.3 二叉树第K层的节点个数
💫代码：
int BTreeLevelKSize(BTNode* root,int k)
{
if (root == NULL)
return 0;
if (k == 1)
return 1;
return BTreeLevelKSize(root->left, k - 1)
+ BTreeLevelKSize(root->right, k - 1);
}
💫流程图：
🌏1.4 二叉树查找值为x的节点
💫第一种写法(错误示范)：
📒代码：
BTNode* BTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
return NULL;
if (root->data == x)
return root;
BTreeFind(root->left, x);
BTreeFind(root->right, x);
}
📒流程图：
💫第二种写法(正确写法)：
📒代码：
BTNode* BTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
return NULL;
if (root->data == x)
return root;
BTNode* ret1 = BTreeFind(root->left, x);
if (ret1)
return ret1;
BTNode* ret2 = BTreeFind(root->left, x);
if (ret2)
return ret2;
return NULL;
}
📒流程图：
🌟二、全部代码：
#include<stdlib.h>
#include<stdio.h>
#include<assert.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
BTNode*BuyNode(BTDataType x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if (node == NULL)
{
perror("malloc fail");
return NULL;
}
node->data = x;
node->left = NULL;
node->right = NULL;
return node;
}
BTNode* CreatBinaryTree()
{
BTNode* node1 = BuyNode(1);
BTNode* node2 = BuyNode(2);
BTNode* node3 = BuyNode(3);
BTNode* node4 = BuyNode(4);
BTNode* node5 = BuyNode(5);
BTNode* node6 = BuyNode(6);
BTNode* node7 = BuyNode(7);
node1->left = node2;
node1->right = node4;
node2->left = node3;
node4->left = node5;
node4->right = node6;
node5->left = node7;
return node1;
}
void PrevOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%d ", root->data);
PrevOrder(root->left);
PrevOrder(root->right);
}
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
}
//二叉树节点个数 --- 遍历计数
//int size = 0;
//void BTreeSzie(BTNode* root)
//{
// if (root == NULL)
// {
// return size;
// }
// size++;
// BTreeSzie(root->left);
// BTreeSzie(root->right);
// return size;
//}
//int BTreeSzie(BTNode* root)
//{
// static int size = 0;
// //printf("%p,%d\n", &size,size);
// if (root == NULL)
// {
// return size;
// }
// size++;
// BTreeSzie(root->left );
// BTreeSzie(root->right );
// return size;
//}
int BTreeSzie(BTNode* root)
{
return root == NULL ? 0 :
BTreeSzie(root->left)
+ BTreeSzie(root->right) + 1;
}
//二叉树叶子节点个数
int BTreeLeafSize(BTNode* root)
{
if (root == NULL)
return 0;
if (root->left == NULL && root->right == NULL)
return 1;
return BTreeLeafSize(root->left)
+ BTreeLeafSize(root->right);
}
//二叉树树的高度
int BTreeHeight(BTNode* root)
{
if (root == NULL)
return 0;
int leftHeight = BTreeHeight(root->left);
int rightHeight = BTreeHeight(root->right );
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
//二叉树第k层的节点个数
int BTreeLevelKSize(BTNode* root,int k)
{
assert(k > 1);
if (root == NULL)
return 0;
if (k == 1)
return 1;
return BTreeLevelKSize(root->left, k - 1)
+ BTreeLevelKSize(root->right, k - 1);
}
//二叉树查找值为x的节点
BTNode* BTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
return NULL;
if (root->data == x)
return root;
/*BTNode* ret1 = BTreeFind(root->left, x);
if (ret1)
return ret1;
BTNode* ret2 = BTreeFind(root->left, x);
if (ret2)
return ret2;
return NULL;*/
//BTreeFind(root->left, x);
//BTreeFind(root->right, x);
//return NULL;
BTNode* ret1 = BTreeFind(root->left, x);
if (ret1)
return ret1;
return BTreeFind(root->left, x);
}
int main()
{
BTNode* root = CreatBinaryTree();
PrevOrder(root);
printf("\n");
InOrder(root);
printf("\n");
PostOrder(root);
printf("\n");
//printf("BTreeSize:%d\n", BTreeSzie(root));
//printf("BTreeSize:%d\n", BTreeSzie(root));
//printf("BTreeSize:%d\n", BTreeSzie(root));
/*BTreeSzie(root);
printf("BTreeSize:%d\n", size);
size = 0;
BTreeSzie(root);
printf("BTreeSize:%d\n", size);
size = 0;
BTreeSzie(root);
printf("BTreeSize:%d\n", size);*/
printf("BTreeSize:%d\n", BTreeSzie(root));
printf("BTreeLeafSize: % d\n", BTreeLeafSize(root));
printf("BTreeHeight: % d\n", BTreeHeight(root));
printf("BTreeLevelKSize: % d\n", BTreeLevelKSize(root,3));
printf("BTreeLevelKSize: % d\n", BTreeLevelKSize(root,2));
printf("BTreeLevelKSize: % d\n", BTreeLevelKSize(root, 4));
return 0;
}
😽总结
😽Ending,今天的链式二叉树的内容就到此结束啦~，如果后续想了解更多，就请关注我吧，一键三连哦 ~
