数据结构第十四弹---链式二叉树基本操作(下)

news/2024/2/25 12:57:20/文章来源:https://blog.csdn.net/2201_75584283/article/details/135457932

链式二叉树

  • 1、翻转二叉树
  • 2、判断两棵树是否相同
  • 3、判断二叉树是否是单值二叉树
  • 4、对称二叉树
  • 5、判断二叉树是否是平衡二叉树
  • 6、判断二叉树是否是另一棵二叉树的子树
  • 7、二叉树的销毁
  • 8、二叉树的深度遍历
    • 8.1、前序遍历
    • 8.2、中序遍历
    • 8.3、后序遍历
  • 9、二叉树的构造和遍历
  • 总结

1、翻转二叉树

如何翻转一颗二叉树?首先我们可以先观察一下翻转前后的变化。如下图。
在这里插入图片描述
画图分析
在这里插入图片描述
通过观察,可以发现:翻转后,根的左右子树的位置交换了;根的孩子的左右子树的位置也交换了;根的孩子的孩子的左右子树的位置也交换了…

思路:
1、翻转左子树
2、翻转右子树
3、交换左右子树位置

代码实现

//翻转二叉树
BTNode* invertTree(BTNode* root)
{if (root == NULL)//根为空,直接返回return NULL;BTNode* left = invertTree(root->left);//翻转左子树BTNode* right = invertTree(root->right);//翻转右子树//左右子树位置交换root->left = right;root->right = left;return root;
}

2、判断两棵树是否相同

在这里插入图片描述
在这里插入图片描述
根据上图可知,相等的两棵树需要根节点数值相等,左右子树数值也相等。

因此可以将问题拆分为子问题。
1、两棵树根节点都为空,则相同。
2、两棵树根节点一个为空,则不相同。
3、两棵树根节点都不为空,两棵树的根的值不相等则不相同。
4、判断左右子树是否相等。

代码实现

bool isSameTree(BTNode* p, BTNode* q)
{if (p == NULL&&q == NULL)//两棵树均为空,则相同return true;if (p == NULL || q == NULL)//两棵树中只有一棵树为空,则不相同return false;if (p->data != q->data)//两棵树根的值不同,则不相同return false;return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);//两棵树的左子树相同并且右子树相同,则这两棵树相同
}

3、判断二叉树是否是单值二叉树

单值二叉树:即二叉树的每个结点具有相同的值。

思路:
1、判断根节点是否为空,为空则是单值二叉树。
2、在左子树存在的情况下,判断左孩子的值是否等于根节点的值。
3、在右子树存在的情况下,判断右孩子的是否等于根节点的值。
4、判断左子树和右子树是否为单值二叉树。

代码实现

//判断二叉树是否是单值二叉树
bool isUnivalTree(BTNode* root)
{if (root == NULL)//根为空,是单值二叉树return true;if (root->left && root->left->data != root->data)//左孩子存在,但左孩子的值不等于根的值return false;if (root->right && root->right->data != root->data)//右孩子存在,但右孩子的值不等于根的值return false;return isUnivalTree(root->left) && isUnivalTree(root->right);//左子树是单值二叉树并且右子树是单值二叉树
}

4、对称二叉树

在这里插入图片描述
在这里插入图片描述
如上图所示,事例一为对称二叉树,事例二不为对称二叉树。可以得知,对称二叉树左孩子等于右孩子,左子树等于右子树。

思路:
1、判断根节点是否为空,为空则为对称二叉树。
2、根节点存在,且左右子树均为空,则为对称二叉树。
3、根节点存在且左右子树其中一个为空,则不为对称二叉树。
4、根节点存在且左右子树均不为空,且左右子树值不相等,则不为对称二叉树。
5、判断左子树是否等于右子树,右子树是否等于左子树。(递归,需要传两个参数,原函数为一个参数,所以创建新的函数实现递归函数)

代码实现

bool _isSymmetric(struct TreeNode* root1,struct TreeNode* root2)
{//1.都为空的if(root1==NULL && root2 == NULL)return true;//2.其中一个子树为空if(root1 == NULL || root2 == NULL)return false;//3.都不为空if(root1->val != root2->val)return false;return _isSymmetric(root1->left,root2->right)&& _isSymmetric(root1->right,root2->left);
} 
bool isSymmetric(struct TreeNode* root) 
{//根为空,则为真if(root==NULL)return true;//将左子树与右子树进行比较 然后递归 原函数只有一个参数,可以构建一个新函数进行比较return _isSymmetric(root->left,root->right);
}

5、判断二叉树是否是平衡二叉树

平衡二叉树:即每个结点的左右两个子树的高度差的绝对值不超过1。
在这里插入图片描述

思路:
1、判断根节点是否为空,为空则是平衡二叉树。
2、计算左子树的高度。
3、计算右子树的高度。
4、如果左右子树的高度差不超过1并且左右子树均为平衡二叉树则为平衡二插树。

代码实现

//判断二叉树是否是平衡二叉树
bool isBalanced(BTNode* root)
{if (root == NULL)//空树是平衡二叉树return true;int leftDepth = BinaryTreeMaxDepth(root->left);//求左子树的深度int rightDepth = BinaryTreeMaxDepth(root->right);//求右子树的深度//左右子树高度差的绝对值不超过1 && 其左子树是平衡二叉树 && 其右子树是平衡二叉树return abs(leftDepth - rightDepth) < 2 && isBalanced(root->left) && isBalanced(root->right);
}

6、判断二叉树是否是另一棵二叉树的子树

在这里插入图片描述
判断二叉树是否是另一个棵树的子树:即root中是否包含与subRoot相同结构和结点值的子树。(subRoot不为空)

思路:
1、如果根节点为空,则不是。
2、判断根节点是否与子树相等,相等则是。
3、判断左子树是否与子树相等,相等则是。
4、判断右子树是否与子树相等,相等则是。

代码实现

bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{//1.都为空if(p==NULL && q==NULL)return true;//2.一个为空if(p==NULL || q==NULL)return false;//3.根都不为空 且val不相等if(p->val!=q->val)return false;//4.根不为空 且根相等 则比较左右子树return isSameTree(p->left,q->left) &&isSameTree(p->right,q->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{if(root == NULL)return false;return isSameTree(root,subRoot)//根节点与子树||isSubtree(root->left,subRoot)//左子树与子树||isSubtree(root->right,subRoot);//右子树与子树
}

7、二叉树的销毁

二叉树的销毁跟其他数据结构的销毁基本类似,都是通过遍历销毁。此处需要通过后序遍历进行销毁,因为只有后序遍历销毁左右子树之后还能找到根节点。

代码实现

void TreeDestroy(BTNode* root)
{if (root == NULL)return;TreeDestroy(root->left);//销毁左子树TreeDestroy(root->right);//销毁右子树free(root);//释放根结点
}

8、二叉树的深度遍历

此处的深度遍历跟上一弹的深度遍历不太一样,前面的是通过遍历将数值打印出来,此处是将二叉树的数值通过遍历存储到一个新的数组中。

思路:
1、通过计算二叉树的有效数据个数,确定新开辟的数组的大小。
2、通过遍历将数据存储到数组中。
3、返回数组。

8.1、前序遍历

代码实现

 int RootSize(struct TreeNode* root){return root==NULL?0:RootSize(root->left)+RootSize(root->right)+1;}void PervOrder(struct TreeNode* root,int* a,int* pi){if(root==NULL)return;a[(*pi)++]=root->val;PervOrder(root->left,a,pi);PervOrder(root->right,a,pi);}
int* preorderTraversal(struct TreeNode* root, int* returnSize) 
{//1.计算树的元素个数int sz=RootSize(root);//2.动态开辟一个树大小的数组int* a=(int*)malloc(sizeof(int)*sz);//3.前序遍历,将树的值赋值到数组上,但是如果对原函数进行递归遍历,//returnSize会多次返回,解决办法是构建新的递归函数int i=0;//记录数组下标和大小PervOrder(root,a,&i);*returnSize=sz;return a;//返回数组
}

8.2、中序遍历

代码实现

  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 sz=TreeSize(root);//动态开辟内存int* a=(int*)malloc(sizeof(int)*sz);//判断是否开辟成功if(a==NULL){perror("malloc fail");return NULL;}int i=0;InOrder(root,a,&i);//返回数据个数*returnSize=sz;//返回数组return a;
}

8.3、后序遍历

在这里插入图片描述

代码实现

 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 sz=TreeSize(root);int* a=(int*)malloc(sizeof(int)*sz);if(a==NULL){perror("malloc fail");return NULL;}int i=0;PostOrder(root,a,&i);*returnSize=sz;return a;
}

9、二叉树的构造和遍历

在这里插入图片描述
思路:
1、遍历字符串,如果该字符不等于’#’,则按照先序遍历构造二叉树,然后递归构造左右子树。
2、如果字符为’#’,则不再进行构造。
3、构造完之后通过中序遍历打印数据。
代码实现

#include <stdio.h>
#include <stdlib.h>typedef struct TreeNode
{struct TreeNode* left;struct TreeNode* right;char data;
}TreeNode;
//创建树
TreeNode* CreateTree(char* str, int* pi)
{if(str[*pi] == '#')//{(*pi)++;return NULL;}//不是NULL,构建结点TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));root->left = NULL;root->right = NULL;root->data = str[*pi];(*pi)++;//递归构建左子树root->left = CreateTree(str, pi);//递归构建右子树root->right = CreateTree(str, pi);return root;
}
//中序遍历
void Inorder(TreeNode* root)
{if(root == NULL)return;Inorder(root->left);printf("%c ", root->data);Inorder(root->right);
}
int main()
{char str[100];scanf("%s", str);int i = 0;TreeNode* root = CreateTree(str, &i);Inorder(root);return 0;
}

测试
在这里插入图片描述

总结

本篇博客就结束啦,谢谢大家的观看,如果公主少年们有好的建议可以留言喔,谢谢大家啦!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_926212.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Java中的JVM指令和Arthas以及Dump文件(jvisualvm和MemoryAnalyzer工具)整体分析

前言 前天线上服务器突然内存和CPU都爆掉了&#xff0c;两者都处于一种高负载的状态&#xff0c;而且还是周末的情况下&#xff0c;起初运维同事怀疑是用户数量暴增&#xff0c;但是数据面板上并没有出现很大的暴增现象&#xff0c;之前的服务器4G的内存都跑不满后面升到8G还是…

NFS网络共享服务存储

目录 一、NFS简介 1、NFS定义&#xff1a; 2、NFS的特点 3、NFS的优缺点 4、NFS的原理图示 二、服务端NFS配置文件&#xff1a;/etc/exports 三、实验&#xff1a;NFS共享存储服务配置 1、服务端安装nfs-utils与rpcbind软件包 2、服务端新建共享文件夹目录并赋予权限 …

【数据库】sql优化有哪些?从query层面和数据库层面分析

目录 归纳sql本身的优化数据库层面的优化 归纳 这类型问题可以称为&#xff1a;Query Optimization&#xff0c;从清华AI4DB的paper list中&#xff0c;该类问题大致可以分为&#xff1a; Query RewriterCardinality EstimationCost EstimationPlan Optimization 从中文的角…

排序算法9----计数排序(C)

计数排序是一种非比较排序&#xff0c;不比较大小 。 1、思想 计数排序又称为鸽巢原理&#xff0c;是对哈希直接定址法的变形应用。 2、步骤 1、统计数据&#xff1a;统计每个数据出现了多少次。&#xff08;建立一个count数组&#xff0c;范围从[MIN,MAX],MAX代表arr中…

网页屏幕适配通透了

一&#xff0c;如果设计尺寸固定 那就按照固定尺寸开发 一般都是1920*1080 二&#xff0c;需要适配多种像素屏幕&#xff08;大屏可视化&#xff09; 可使用媒体查询设置多套css样式或者使用自适应单位&#xff0c;%&#xff0c;vw&#xff0c;vh 最好解决方案rem&#xff…

Unity Shader 的模板测试效果

模板测试是渲染管线中逐片元操作的一环&#xff0c;它的作用是筛选出指定模板的片元&#xff0c;而不符合模板的片元会被舍弃&#xff0c;从而做到一个遮罩的效果。 以下是Unity中实践的一个效果&#xff1a; 场景中可以看出&#xff0c;熊模型和茶壶模型都在差不多的位置&am…

Kafka 的架构

实验过程 1.三个虚拟机中解压kafka软件包 tar -zxvf kafka_2.11-1.1.1.tgz 2.修改 3 个节点配置文件 在 zookeeper 节点&#xff0c;进入 kafka_2.11-1.1.1/config 目录下&#xff0c;编辑 server.properties 文件 [rootdb1 ~]# cd kafka_2.11-1.1.1/config [rootdb1 con…

HarmonyOS应用开发者高级认证试题库(鸿蒙)

目录 考试链接&#xff1a; 流程&#xff1a; 选择&#xff1a; 判断 单选 多选 考试链接&#xff1a; 华为开发者学堂华为开发者学堂https://developer.huawei.com/consumer/cn/training/dev-certification/a617e0d3bc144624864a04edb951f6c4 流程&#xff1a; 先进行…

【一】通信协议概述

通信协议概述 简介&#xff1a; 很早之前就思考了要写一下电力系统常用的几种通信协议&#xff0c;一直拖着也没有行动&#xff0c;这次终于下定决心来出一个《通信协议》这样的专栏。电力行业数字化方面资料较少&#xff0c;我理解主要一方面是数字化程度还不高&#xff0c;一…

使用Python操纵Word自动编写离职报告

目录 一、背景介绍 二、技术原理 三、实现步骤 1、安装python-docx库 2、创建Word文档 3、添加标题和内容 4、添加表格和图片 5、设置样式和格式化文本 6、保存文档 四、注意事项与建议 总结 随着现代社会的发展&#xff0c;自动化和智能化已经成为各行各业追求的目…

使用PyTorch实现混合专家(MoE)模型

Mixtral 8x7B 的推出在开放 AI 领域引发了广泛关注&#xff0c;特别是混合专家&#xff08;Mixture-of-Experts&#xff1a;MoEs&#xff09;这一概念被大家所认知。混合专家(MoE)概念是协作智能的象征&#xff0c;体现了“整体大于部分之和”的说法。MoE模型汇集了各种专家模型…

消息的发送与接收

消息的发送与接收 消息的发送与接收不仅仅是在于聊天功能的实现。其实还有很多种情况也算"消息的发送与接收"。而且我们还可以通过多种方法去实现。我们可以基于实际情况来选择。 WebSocket实现 node做后端。找了好多&#xff0c;前端页面总是用到了jQuery&#x…

(C语言)冒泡排序

一、运行结果&#xff1b; 二、源代码&#xff1b; # define _CRT_SECURE_NO_WARNINGS # include <stdio.h>//实现buble_sort函数&#xff1b; void buble_sort(int arr[], int sz) {//初始化变量值&#xff1b;int i 0;//嵌套循环冒泡排序&#xff1b;//外层循环&…

【REST2SQL】10 REST2SQL操作指南

【REST2SQL】01RDB关系型数据库REST初设计 【REST2SQL】02 GO连接Oracle数据库 【REST2SQL】03 GO读取JSON文件 【REST2SQL】04 REST2SQL第一版Oracle版实现 【REST2SQL】05 GO 操作 达梦 数据库 【REST2SQL】06 GO 跨包接口重构代码 【REST2SQL】07 GO 操作 Mysql 数据库 【RE…

微信小程序-----全局配置与页面配置

目录 前言 全局配置文件 一、window 1. 小程序窗口的组成部分 2. window 节点常用的配置项 3. 设置导航栏的标题 4. 设置导航栏的背景色 5. 设置导航栏的标题颜色 6. 全局开启下拉刷新功能 7. 设置下拉刷新时窗口的背景色 8. 设置下拉刷新时 loading 的样式 9. 设置…

两步解决宝塔面板无法访问(无法访问或拒绝链接)

宝塔面板&#xff0c;突然无法进入&#xff0c;显示“IP拒绝链接”。 使用SSH工具登录服务器 /etc/init.d/bt defaultbt default 命令 宝塔获取登录的默认地址、用户名和登录密码&#xff1b; 重启面板服务 sudo /etc/init.d/bt初始化宝塔选项 漏刻有时

装饰者模式:打破继承限制,实现灵活的功能扩展

欢迎来到我的博客&#xff0c;代码的世界里&#xff0c;每一行都是一个故事 装饰者模式&#xff1a;打破继承限制&#xff0c;实现灵活的功能扩展 前言装饰者模式简介装饰者模式的工作原理实际应用java代码实现结语 前言 在软件开发中&#xff0c;我们经常面临着需求的变化和新…

rsync全面讲解

rsync 是一个常用的 Linux 应用程序&#xff0c;用于文件同步。 它可以在本地计算机与远程计算机之间&#xff0c;或者两个本地目录之间同步文件&#xff08;但不支持两台远程计算机之间的同步&#xff09;。它也可以当作文件复制工具&#xff0c;替代cp和mv命令。 它名称里面…

基础面试题整理4

1.mybatis的#{}和${}区别 #{}是预编译处理&#xff0c;${}是字符串替换#{}可以防止SQL注入&#xff0c;提高安全性 2.mybatis隔离级别 读未提交 READ UNCOMMITED&#xff1a;读到了其他事务中未提交的数据&#xff0c;造成"脏读","不可重复读","幻读&…

Python进程池multiprocessing.Pool

环境&#xff1a; 鲲鹏920:192核心 内存&#xff1a;756G python&#xff1a;3.9 python单进程的耗时 在做单纯的cpu计算的场景&#xff0c;使用单进程核多进程的耗时做如下测试&#xff1a; 单进程情况下cpu的占用了如下&#xff0c;占用一半的核心数&#xff1a; 每一步…