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

这篇具有很好参考价值的文章主要介绍了数据结构第十四弹---链式二叉树基本操作(下)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1、翻转二叉树

如何翻转一颗二叉树?首先我们可以先观察一下翻转前后的变化。如下图。
数据结构第十四弹---链式二叉树基本操作(下),数据结构详解,数据结构,算法,c语言
画图分析
数据结构第十四弹---链式二叉树基本操作(下),数据结构详解,数据结构,算法,c语言
通过观察,可以发现:翻转后,根的左右子树的位置交换了;根的孩子的左右子树的位置也交换了;根的孩子的孩子的左右子树的位置也交换了…

思路:
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、判断两棵树是否相同

数据结构第十四弹---链式二叉树基本操作(下),数据结构详解,数据结构,算法,c语言
数据结构第十四弹---链式二叉树基本操作(下),数据结构详解,数据结构,算法,c语言
根据上图可知,相等的两棵树需要根节点数值相等,左右子树数值也相等。

因此可以将问题拆分为子问题。
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、对称二叉树

数据结构第十四弹---链式二叉树基本操作(下),数据结构详解,数据结构,算法,c语言
数据结构第十四弹---链式二叉树基本操作(下),数据结构详解,数据结构,算法,c语言
如上图所示,事例一为对称二叉树,事例二不为对称二叉树。可以得知,对称二叉树左孩子等于右孩子,左子树等于右子树。

思路:
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。
数据结构第十四弹---链式二叉树基本操作(下),数据结构详解,数据结构,算法,c语言

思路:
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、判断二叉树是否是另一棵二叉树的子树

数据结构第十四弹---链式二叉树基本操作(下),数据结构详解,数据结构,算法,c语言
判断二叉树是否是另一个棵树的子树:即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、后序遍历

数据结构第十四弹---链式二叉树基本操作(下),数据结构详解,数据结构,算法,c语言

代码实现

 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、二叉树的构造和遍历

数据结构第十四弹---链式二叉树基本操作(下),数据结构详解,数据结构,算法,c语言
思路:
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;
}

测试
数据结构第十四弹---链式二叉树基本操作(下),数据结构详解,数据结构,算法,c语言

总结

本篇博客就结束啦,谢谢大家的观看,如果公主少年们有好的建议可以留言喔,谢谢大家啦!文章来源地址https://www.toymoban.com/news/detail-808851.html

到了这里,关于数据结构第十四弹---链式二叉树基本操作(下)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】二叉树(链式)

    😛作者:日出等日落 📘 专栏:数据结构           抱怨是一件最没意义的事情。如果实在难以忍受周围的环境,那就暗自努力练好本领,然后跳出那个圈子。 目录  🎄二叉树 ✔二叉树的结构:  ✔BuyNode(创建二叉树节点): 🎄基本函数操作: ✔PreOrder(前序递归遍历):

    2024年02月01日
    浏览(46)
  • 【数据结构】二叉树之链式结构

    🔥 博客主页 : 小羊失眠啦. 🎥 系列专栏 : 《C语言》 《数据结构》 《Linux》 《Cpolar》 ❤️ 感谢大家点赞👍收藏⭐评论✍️ 在学习二叉树各种各样的操作前,我们先来回顾一下二叉树的概念: 二叉树是度不超过2的树,由根结点和左右2个子树组成,每个子树也可以看作

    2024年02月04日
    浏览(46)
  • 数据结构——二叉树的链式结构

      个人主页 : 日刷百题 系列专栏 : 〖C语言小游戏〗〖Linux〗〖数据结构〗  〖C语言〗 🌎 欢迎各位 → 点赞 👍+ 收藏 ⭐️+ 留言 📝  ​ 这里我们使用先序遍历的思想来创建二叉树,这里的内容对于刚接触二叉树的朋友可能有些难理解,不妨先看完下面的二叉树各种遍历

    2024年02月05日
    浏览(48)
  • 【数据结构】二叉树的链式结构

    学习链式二叉树要知道三种遍历方式,便于对二叉树的节点以及左子树和右子树进行操作。 前序遍历:根、左子树、右子树 中序遍历:左子树、根、右子树 后序遍历:左子树、右子树、根 以下图为例: 得到的结果: 前序遍历:1 2 3 4 5 6 中序遍历:3 2 1 5 4 6 后序遍历:3 2

    2024年02月08日
    浏览(57)
  • 数据结构:二叉树的链式结构

    朋友们、伙计们,我们又见面了,本期来给大家解读一下链式二叉树的相关知识点,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! 数据结构与算法专栏 :数据结构与算法 个  人  主  页 :stackY、 C 语 言 专 栏 :C语言:从入门到精通 目录 前言

    2024年02月07日
    浏览(59)
  • 【数据结构】二叉树 链式结构的相关问题

     本篇文章来详细介绍一下二叉树链式结构经常使用的相关函数,以及相关的的OJ题。 目录 1.前置说明 2.二叉树的遍历 2.1 前序、中序以及后序遍历 2.2 层次遍历 3.节点个数相关函数实现 3.1 二叉树节点个数 3.2 二叉树叶子节点个数 3.3 二叉树第k层节点个数 3.4 在二叉树中查找值

    2024年02月14日
    浏览(59)
  • 【数据结构—二叉树的链式结构实现】

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言 一、二叉树的存储结构 二、二叉树链式结构的实现 2.1手动构建一课树 2.2二叉树的遍历 三、二叉树链式结构的实现 3.1前序遍历(递归) 3.2中序遍历(递归) 3.3后序遍历(递归) 3.4层序遍历(非递

    2024年02月03日
    浏览(59)
  • 【数据结构 —— 二叉树的链式结构实现】

    树是一种非线性的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。 把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。 1.有一个 特殊的结点,称为根结点 ,根节点没有前驱结点 2.除根节点外, 其余结点被分成M(M0)个互不相交

    2024年02月05日
    浏览(57)
  • 【数据结构】二叉树的链式存储结构

    前序遍历,又叫先根遍历。 遍历顺序:根 - 左子树 - 右子树 代码: 中序遍历,又叫中根遍历。 遍历顺序:左子树 - 根 - 右子树 代码 : 后序遍历,又叫后根遍历。 遍历顺序:左子树 - 右子树 - 根 代码 : 除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍

    2024年02月09日
    浏览(46)
  • 【数据结构】二叉树链式结构的实现(三)

    目录 一,二叉树的链式结构 二,二叉链的接口实现         1,二叉链的创建         2,接口函数         3,动态创立新结点         4,创建二叉树         5,前序遍历         6,中序遍历         7,后序遍历 三,结点个数以及高度等      

    2024年02月08日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包