当前位置：网站首页>二叉树的基础练习
二叉树的基础练习
2022-08-04 09:47:00 【kocc】
文章目录
二叉树的基础练习
typedef char BTDataType;
typedef struct BinaryTreeNode
{
BTDataType _data;
struct BinaryTreeNode* _left;
struct BinaryTreeNode* _right;
}BTNode;
通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTnode* BinaryTreeCreate(BTDataType* a, int n, int* pi)//n为字符串长度
{
if(a[*pi]=='#'|| *pi >= n)//当字符串下标上溢或者对应的位置为空时，将结点指针指向空
{
(*pi)++;
return NULL;
}
BTnode* root = (BTnode*)malloc(sizeof(BTnode));
root->data = a[(*pi)++];
root->left= BinaryTreeCreate(a,n,pi);
root->right=BinaryTreeCreate(a,n,pi);
return root;
}
二叉树销毁
//利用后序遍历的方式来进行销毁：逐次递归销毁左子树、右子树、根...
void BinaryTreeDestory(BTNode* root)//在这传入一级指针，free的动作就要在调用函数之后来完成，在函数内部完成是无效的
{
if(root==NULL)
{
return ;
}
BinaryTreeDestory(root->left);
BinaryTreeDestory(root->right);
free(root);
}
二叉树节点个数
//思路1：遍历+计数
int count =0;
BinaryTreeSize(tree,&count)
void BinaryTreeSize(BTNode* root,int* pcount)
{
//刚开始的想法是直接定义一个局部静态变量来计数，但是存在的问题就是没有办法把它用完初始化成0，多次调用结果就会出错，特别是在OnlineJudge的时候
//然后又思考是否可以定义一个全局变量来计数，但这其实存在线程安全的问题
//因此我们选择多套一层，直接传入全局变量的指针来间接计数即可
if(root==NULL)
{
return;
}
++(*pcount);
BinaryTreeSize(root->left,pcount);
BinaryTreeSize(root->right,pcount);
}
//思路2：子问题的递归思想
int BinaryTreeSize(BTNode* root)
{
return root==NULL?
0:
BinaryTreeSize(root->left)+BinaryTreeSize(root->right)+1;//左子树+右子树+自己
}
二叉树叶子节点个数
//也可以利用遍历来做
//此处我们利用分治思想
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层 =根的左子树的第k-1层 + 根的右子树的第k-1层...
int BinaryTreeLevelKSize(BTNode* root, int k)
{
if(k==0)
{
return 0;
}
if(k==1)
{
return 1;
}
return BinaryTreeLevelKSize(root->left,k-1) +
BinaryTreeLevelKSize(root->right,k-1);
//举个例子：
//根的第三层=根的左子树的第二层 + 根的右子树的第二层=...依次递归下去
}
二叉树查找值为x的节点
//思想:分治前序
//先判断根是不是，再判断左边的树是不是，再判断右边的树是不是...
//注意此题并不是直接返回，而是此次的返回值是要作为上一层递归的依据
//比如这一层返回空，上一层就接着走，这一层若找到，返回值让上一层接收到，上一层再返回给上上一层，直至退出递归
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if(root==NULL)
{
return NULL;
}
if(root->data==x)
{
return root;
}
BTNode* ret1=BinaryTreeFind(root->left,x)
if(ret1)
{
return ret1;
}
BTNode* ret2=BinaryTreeFind(root->right,x)//逻辑更加清晰的写法
if(ret2)
{
return ret2;
}
return NULL;
}
//该查找的好处是取到了该数的指针，可以直接完成修改
int TreeSize(struct TreeNode* root)
{
return root==NULL ? 0 : TreeSize(root->left)+TreeSize(root->right)+1;
}//计算出此数的结点数
void _preorder(struct TreeNode* root,int *a,int* pi)
{
if(root==NULL)
{
return;
}
a[(*pi)++]=root->val;//前中后序的区别在这
_preorder(root->left,a,pi);
_preorder(root->right,a,pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
int size=TreeSize(root);
int *a=malloc(sizeof(int)*size);//malloc出一个数组
assert(a);
*returnSize=size;
int i=0;
_preorder(root,a,&i);//调用前序遍历，注意此时传入计数变量的指针
return a;
}
//与前序没有什么大的区别
int TreeSize(struct TreeNode* root)
{
return root==NULL ? 0 : TreeSize(root->left)+TreeSize(root->right)+1;
}
void _inorder(struct TreeNode* root,int *a,int* pi)
{
if(root==NULL)
{
return;
}
_inorder(root->left,a,pi);
a[(*pi)++]=root->val;//前中后序的区别在这
_inorder(root->right,a,pi);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize)
{
int size=TreeSize(root);
int *a=malloc(sizeof(int)*size);
assert(a);
*returnSize=size;
int i=0;
_inorder(root,a,&i);
return a;
}
int TreeSize(struct TreeNode* root)
{
return root==NULL ? 0 : TreeSize(root->left)+TreeSize(root->right)+1;
}
void _postorder(struct TreeNode* root,int *a,int* pi)
{
if(root==NULL)
{
return;
}
_postorder(root->left,a,pi);
_postorder(root->right,a,pi);
a[(*pi)++]=root->val;//前中后序的区别在这
}
int* postorderTraversal(struct TreeNode* root, int* returnSize)
{
int size=TreeSize(root);
int *a=malloc(sizeof(int)*size);
assert(a);
*returnSize=size;
int i=0;
_postorder(root,a,&i);
return a;
}
层序遍历
深度优先遍历：前序、中序、后序
广度优先遍历：层序遍历
层序遍历需要利用【队列】的数据结构来进行
//思路：先把根入队列，借助队列先进先出的性质，上一层结点出队列时，带下一层的结点进去
// 假设我们已经造好了一个队列供我们使用
void BinaryTreeLevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
if(root)//若根不为空进入
{
QueuePush(&q,root);
}
if(!QueueEmpty(&q))
{
BTnode* front=Queuefront(&q);
Queuepop(&q);//pop的是结点的指针，那个树结点还是在的
printf("%d ",front->data);
if(front->left)
{
QueuePush(&q,front->left);
}
if(front->right)
{
QueuePush(&q,front->right);
}
}
printf("\n");
QueueDestory(&q);
}
判断二叉树是否是完全二叉树
//思路： 层序遍历，空结点也进队列，当第一个空结点出队列时，检查出队列后续是否都为空，若是那就是完全二叉树，反之则不是。
bool BinaryTreeComplete(BTNode* root)
{
Queue q;
QueueInit(&q);
if(root)//若根不为空进入
{
QueuePush(&q,root);
}
while(!QueueEmpty(&q))
{
BTnode* front=Queuefront(&q);
Queuepop(&q);
if(front==NULL)
{
break;
}
QueuePush(&q,front->left);
QueuePush(&q,front->right);
}
while(!QueueEmpty(&q))
{
BTnode* front=Queuefront(&q);
Queuepop(&q);
if(front!=NULL)
{
QueueDestory(&q);
return false;
}
}
QueueDestory(&q);
return true;
}
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
//分治递归思想：先比较根 在比较左子树再比较右子树 递归即可
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
if(p==NULL && q==NULL)//均为空树
{
return true;
}
if(p==NULL || q==NULL)//若一个为空一个不为空
{
return false;
}
if(p->val!=q->val)
{
return false;
}
if(!isSameTree(q->left,p->left))//递归比较左右子树
{
return false;
}
if(!isSameTree(q->right,p->right))
{
return false;
}
return true;
}
检查它是否轴对称
//将根的左右子树看作两个不同的树，问题就转变成 【判断两颗树是否相等】
//但要注意的是，此时判断是拿左的左子树和右的右子树比对，因为是判断对称
bool isSameTree(struct TreeNode* p,struct TreeNode* q)
{
if(p==NULL && q==NULL)
{
return true;
}
if(p==NULL || q==NULL)
{
return false;
}
if(p->val!=q->val)
{
return false;
}
if(!isSameTree(p->left,q->right))//注意这里是left 和 right
{
return false;
}
if(!isSameTree(p->right,q->left))
{
return false;
}
return true;
}
bool isSymmetric(struct TreeNode* root)
{
if(root==NULL)
{
return true;
}
return isSameTree(root->left,root->right);
}
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
if(p==NULL && q==NULL)//均为空树
{
return true;
}
if(p==NULL || q==NULL)//若一个为空一个不为空
{
return false;
}
if(p->val!=q->val)
{
return false;
}
if(!isSameTree(q->left,p->left))//递归比较左右子树
{
return false;
}
if(!isSameTree(q->right,p->right))
{
return false;
}
return true;
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{
if(root==NULL)
{
return false;
}
return isSameTree(root,subRoot)||//复用一下isSameTree
isSubtree(root->left,subRoot)||
isSubtree(root->right,subRoot);//遍历树，让树中的每一个子树都与subroot比较一下 如果有就return
}
//交换一下左右节点，然后再递归的交换左节点，右节点
void Traversal(struct TreeNode* root)
{
if(root==NULL)
{
return;
}
//左右子节点交换位置
//自上而下
struct TreeNode* temp= root->left;
root->left = root->right;
root->right = temp;
//左
Traversal(root->left);
//右
Traversal(root->right);
}
struct TreeNode* invertTree(struct TreeNode* root)
{
Traversal(root);
return root;
}
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
//分治：左子树高度与右子树高度比，大的那个再加1（加上根）
int maxDepth(struct TreeNode* root)
{
if(root==NULL)
{
return 0;
}
int left=maxDepth(root->left);
int right=maxDepth(root->right);
return left>right?left+1:right+1;
}
如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
//思想还是一样的，此题类似于查找的变形
//每个根都与自己的左孩子与右孩子相比是否相等，逐次递归即可
bool isUnivalTree(struct TreeNode* root)
{
if(root==NULL)
{
return true;
}
if(root->left && root->val!=root->left->val)
{
return false;
}
if(root->right && root->val!=root->right->val)
{
return false;
}
return isUnivalTree(root->left) && isUnivalTree(root->right);
}
#include<stdio.h>
typedef struct BinaryTreeNode
{
char data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTnode;
BTnode* CreateTree(char* a,int* pi)//按照前序的规则去创建一棵树
{
if(a[*pi]=='#')
{
(*pi)++;
return NULL;
}
BTnode* root = (BTnode*)malloc(sizeof(BTnode));
root->data = a[(*pi)++];
root->left= CreateTree(a,pi);
root->right=CreateTree(a,pi);
return root;
}
void Inorder(BTnode* root)//中序遍历
{
if(root==NULL)
{
return;
}
Inorder(root->left);
printf("%c ",root->data);
Inorder(root->right);
}
int main()
{
char a[1000];
scanf("%s",a);
int i = 0;
BTnode* tree=CreateTree(a,&i);//传指针
Inorder(tree);
return 0;
}
边栏推荐
- 多了＆lt;audio controls=
- How Oracle for current library or certain library data on the same server number?
- ps抠图怎么抠出来，自学ps软件photoshop2022，ps怎么抠出想要的部分-笔记记录
- Get the number of cpu cores
- 冰蝎逆向初探
- pyvista 的介绍与使用
- Post-94 Byte P7 posted the salary slip: It's really good to make up for this...
- 蜜芽CEO刘楠：垂直电商黄金时代已落幕 坚定转型品牌之路
- MindSpore:【mindinsight】【Profiler】用execution_time推导出来的训练耗时远小于真实的耗时
- LeetCode581+621+207
猜你喜欢
Win11如何隐藏输入法悬浮窗？
Techwiz OLED：OLED器件的发光效率
数据万象内容审核 — 共建安全互联网，专项开展“清朗”直播整治行动
MindSpore：Batchnorm only support nchw input!
NAT/NAPT地址转换(内外网通信)技术详解【华为eNSP】
TiFlash 源码阅读（五） DeltaTree 存储引擎设计及实现分析 - Part 2
字符串相关题目
LeetCode中等题之旋转图像
Detailed explanation of NAT/NAPT address translation (internal and external network communication) technology [Huawei eNSP]
参数优化文档介绍
随机推荐
浅聊偏函数
菲沃泰科创板上市：市值123亿 宗坚赵静艳夫妇身价76亿
Shell编程的条件语句
路由/三层交换机DHCP下发地址详解【华为eNSP】
Redis 内存满了怎么办？这样置才正确！
【c】操作符详解（二）
学习使用php把stdClass Object转array的方法整理
请你谈谈网站是如何进行访问的？【web领域面试题】
VSCode学习资料
Inheritance and the static keyword
Detailed Explanation of Addresses Delivered by DHCP on Routing/Layer 3 Switches [Huawei eNSP]
LeetCode简单题之最好的扑克手牌
gom登录器配置教程_谷歌浏览器如何使用谷歌搜索引擎
交换机链路聚合详解【华为eNSP】
MindSpore:MindSpore GPU版本安装问题
VRRP + MSTP configuration, huawei eNSP experiment 】 【
XCTF-reverse-signin
Acwing 3208. Z字形扫描 偏移量+扩展图
请问下Flink SQL如何写hologres分区表？我想要每天一个分区
什么是元宇宙？