【数据结构】二叉树的相关操作以及OJ题目

这篇具有很好参考价值的文章主要介绍了【数据结构】二叉树的相关操作以及OJ题目。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


【数据结构】二叉树的相关操作以及OJ题目,数据结构,数据结构,算法

1. 二叉树

当一个树不是满二叉树或完全二叉树时,它是不适合使用数组存储的,它应该使用链式结构来存储。
再看二叉树基本操作前,再回顾下二叉树的概念,二叉树是:

  1. 空树
  2. 非空:根节点,根节点的左子树、根节点的右子树组成的。

【数据结构】二叉树的相关操作以及OJ题目,数据结构,数据结构,算法

从概念中可以看出,二叉树定义是递归式的,因此后序基本操作中基本都是按照该概念实现的。
所以可以定义成下面这种:

typedef int TNDataType;
typedef struct TreeNode
{
	TNDataType val;
	struct TreeNode* left;
	struct TreeNode* right;
}TreeNode;

2.二叉树的遍历

所谓二叉树遍历(Traversal)是按照某种特定的规则,依次对二叉树中的节点进行相应的操作,并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一,也是二叉树上进行其它运算的基础。

按照规则,二叉树的遍历有:前序/中序/后序的递归结构遍历:

  1. 前序遍历——访问根结点的操作发生在遍历其左右子树之前。 (根左右)
  2. 中序遍历——访问根结点的操作发生在遍历其左右子树之中(间)。(左根右)
  3. 后序遍历——访问根结点的操作发生在遍历其左右子树之后。(左右根)

2.1前序遍历

【数据结构】二叉树的相关操作以及OJ题目,数据结构,数据结构,算法
前序遍历:先访问树的根,然后访问左子树(左子树又被分为根、左子树、右子树,直到左子树不能拆分),然后再访问右子树(右子树又被分为根、左子树、右子树,直到右子树不能拆分)

先遍历根(有根一直根),然后左(有左一直左),最后右,拆分了以后就从头来

遍历结果	1 2 3 NULL NULL NULL 4 5 NULL NULL 6 NULL NULL
谁的NULL:      3    3    2        5    5      6    6
void PreOrder(TreeNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", root->val);//先遍历根

	PreOrder(root->left);//然后遍历左子树

	PreOrder(root->right);//最后遍历右子树
}

2.2中序遍历

【数据结构】二叉树的相关操作以及OJ题目,数据结构,数据结构,算法
中序遍历:有左子树就一直访问左子树,直到左子树不能再拆分,然后遍历根,最后遍历右子树(右子树又拆分为根、左子树、右子树。也得先访问左子树)

有左一直左,然后根,最后右,拆分了以后就从头来

遍历结果: NULL 3 NULL 2 NULL 1 NULL 5 NULL 4 NULL 6 NULL
谁的NULL: 3       3      2      5      5      6     6
void InOrder(TreeNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->left);//先遍历左子树

	printf("%d ", root->val);//再遍历根

	InOrder(root->right);//最后遍历右子树
}

2.3后序遍历

【数据结构】二叉树的相关操作以及OJ题目,数据结构,数据结构,算法
后序遍历:先遍历左子树(左子树又拆分为:根、左子树、右子树),然后遍历右子树(右子树又拆分为:根、左子树、右子树),最后遍历根。
有左一直左,然后右,最后根,拆分了以后就从头来

遍历结果: NULL NULL 3 NULL 2 NULL NULL 5 NULL NULL 6 4 1
谁的NULL:  3    3      2      5    5      6    6  
//后序遍历
void PostOrder(TreeNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	PostOrder(root->left);//先遍历左子树

	PostOrder(root->right);//再遍历右子树

	printf("%d ", root->val);//最后访问根
}

2.4层序遍历

二叉树的层序遍历需要借助队列实现。
首先需要将根入队列,然后再出队列,出队列时,需要将自己的孩子带进队列之中。由于栈先进先出的特点,只有上一层全部出完了才会出当前层,故可以实现层序遍历。

需要注意的是:链表的数值域设置为指向树节点的指针

//树的结构
typedef int TNDataType;
typedef struct TreeNode
{
	TNDataType val;
	struct TreeNode* left;
	struct TreeNode* right;
}TreeNode;


//链表的节点
typedef TreeNode* QNodeDataType;//将链表的数值域设置为指向树节点的指针
typedef struct QueueNode
{
	QNodeDataType data;
	struct QueueNode* next;
}QNode;
//层序遍历
void TreeLevelOrder(TreeNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		//出数据
		TreeNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front)
		{
			printf("%d ", front->val);
			//出的数据将其孩子带进队列中(带下一层)
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
		else
		{
			printf("N ");
		}
	}
	printf("\n");
	QueueDestroy(&q);
}

3.树的节点个数

方法:当前节点只加自己,然后再加上左子树和右子树中节点的个数

int TreeSize(TreeNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 1 + TreeSize(root->left) + TreeSize(root->right);
}

4.树的高度

当前层加上子树中高度大的一个

int  TreeHeight(TreeNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int left = TreeHeight(root->left);
	int right = TreeHeight(root->right);
	return  left > right ? left + 1 : right + 1;
}

5.叶子节点的个数

是叶子,返回1;不是叶子,继续遍历左右子树,空树返回0
【数据结构】二叉树的相关操作以及OJ题目,数据结构,数据结构,算法

int BinaryTreeLeafSize(TreeNode* root)
{
	//空树,返回空
	if (root == NULL)
	{
		return 0;
	}
	//叶子,返回1
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	//继续遍历左右子树
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

6.第k层节点的个数

不是第k层就继续遍历左右子树,空树返回0;第k层就返回1。
假设K等于3
【数据结构】二叉树的相关操作以及OJ题目,数据结构,数据结构,算法

int TreeKLevel(TreeNode* root, int k)
{
	//空树
	if (root == NULL)
	{
		return 0;
	}
	//到第k层
	if (k == 1)
	{
		return 1;
	}
	//未到第k层,继续在左右子树中寻找
	//层数减少
	return TreeKLevel(root->left,k-1) + TreeKLevel(root->right,k-1);
}

7.查找x所在的节点

当前节点为空数,返回NULL,当前节点是x,返回x的地址;当前节点不是x,先在左子树中找,左子树找不到,再到右子树中找。

TreeNode* TreeFind(TreeNode* root, int x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->val == x)
	{
		return root;
	}
	//先在左子树中找
	TreeNode* left = TreeFind(root->left,x);
	if (left)//找到了返回
	{
		return left;
	}
	//左子树找不到。那就在右子树中找
	TreeNode* right = TreeFind(root->right, x);
	if (right)
	{
		return right;//找到了,返回
	}
	//左右都找不到,整棵树都找不到
	return NULL;
}

【数据结构】二叉树的相关操作以及OJ题目,数据结构,数据结构,算法

8.树的销毁

//树的销毁,采用后序遍历销毁
void TreeDestroy(TreeNode* root)
{
	if (root == NULL)
		return;

	TreeDestroy(root->left);
	TreeDestroy(root->right);

	free(root);
}

9.相关题目

9.1相同的树

【数据结构】二叉树的相关操作以及OJ题目,数据结构,数据结构,算法
题目链接
先比较两树的根是否相等,若相等,在比较子树是都对应相等;若不相等,直接返回false。

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;
    //两根相等,检查左、右子树相不相同
    return isSameTree(p->left,q->left) && isSameTree(q->right,p->right);
}

9.2单值二叉树

【数据结构】二叉树的相关操作以及OJ题目,数据结构,数据结构,算法
题目链接
若当前节点的值不等于根的值,直接false;若当前节点为NULL,则返回true,当前节点不是空,则检查它左树与右数的值等不等于根的值。

bool UnivalTree(struct TreeNode* root ,int val)
{
    if(root == NULL)
    {
        return true;
    }
    if(root->val != val)
    {
        return false;
    }

    return UnivalTree(root->left,val) && UnivalTree(root->right,val);
}

bool isUnivalTree(struct TreeNode* root) {
    if(root == NULL)
    {
        return true;
    }
    int val = root->val;

    return UnivalTree(root,val);
}
bool isUnivalTree(struct TreeNode* root) {
    if(root == NULL)
        return true;
    if(root->left && root->left->val != root->val)
        return false;
    if(root->right && root->right->val != root->val)
        return false;
    return isUnivalTree(root->left) 
        && isUnivalTree(root->right);
}

9.3对称二叉树

【数据结构】二叉树的相关操作以及OJ题目,数据结构,数据结构,算法
题目链接

bool check(struct TreeNode* left,struct TreeNode* right)
{
    if(left == NULL && right == NULL)
    {
        return true;
    }

    if(left == NULL || right == NULL)
    {
        return false;
    }
    //当前节点相等,遍历左右子树
    return left->val == right->val
        && check(left->left,right->right)
        && check(left->right,right->left);
}

bool isSymmetric(struct TreeNode* root) {
    if(root == NULL)
    {
        return true;
    }
    return check(root->left,root->right);
}

9.4二叉树的构建

【数据结构】二叉树的相关操作以及OJ题目,数据结构,数据结构,算法

题目链接

//前序遍历,构建二叉树
TreeNode* CreatTree(char* a, int* pi)
{
	if (a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}
	//先构建根
	TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
	root->val = a[(*pi)++];
	//然后构建左右子树
	root->left = CreatTree(a, pi);
	root->right = CreatTree(a, pi);
	return root;
}

9.5翻转二叉树

【数据结构】二叉树的相关操作以及OJ题目,数据结构,数据结构,算法
题目链接
思路:将根的子树依次进行交换
【数据结构】二叉树的相关操作以及OJ题目,数据结构,数据结构,算法

struct TreeNode* invertTree(struct TreeNode* root) {
    if(root == NULL)
        return NULL;

    //交换当前树的左右子树
    struct TreeNode* tmp = root->left;
    root->left = root->right;
    root->right = tmp;

    //递归交换左右子树
    invertTree(root->left);
    invertTree(root->right);

    return root;
}

9.6另一颗树的子树

【数据结构】二叉树的相关操作以及OJ题目,数据结构,数据结构,算法
题目链接
其实这一题就是9.1的变种,本质上还是找两棵相同的树。

  • 若当前根节点与另一棵树相等,那就从当前节点开始,依次比较子树,检查是否相等。
  • 若子树为空或与另一棵树不相等,则返回false.
bool isSameTree(struct TreeNode* root, struct TreeNode* subRoot)
{
    if(root == NULL && subRoot == NULL)
        return true;
    if(root == NULL || subRoot == NULL)
        return false;
    if(root->val != subRoot->val)
        return false;
    return isSameTree(root->left,subRoot->left)
        && isSameTree(root->right,subRoot->right);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    if(root == NULL)
        return false;//此处是false
    if(root->val == subRoot->val && isSameTree(root,subRoot))
        return true;
    return isSubtree(root->left,subRoot)
        || isSubtree(root->right,subRoot);
}

10.判断二叉树是否是完全二叉树

思路:与层序遍历类似,依然使用入队出队的方式。‘
如果当前出队元素为NULL,则队中的剩余元素必须全部为空,否则就不是一棵完全二叉树。文章来源地址https://www.toymoban.com/news/detail-841403.html

// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(TreeNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		TreeNode* front = QueueFront(&q);
		QueuePop(&q);
		//若当前出队元素不是空,则该元素出队,将它的孩子进队
		if (front)
		{
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
		else
		{
			//当前出的元素是空,停止出
			break;
		}
	}
	//继续出,检查有无非空节点
	while (!QueueEmpty(&q))
	{
		TreeNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front != NULL)
		{
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}

到了这里,关于【数据结构】二叉树的相关操作以及OJ题目的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 深入理解数据结构第三弹——二叉树(3)——二叉树的基本结构与操作

    二叉树(1): 深入理解数据结构第一弹——二叉树(1)——堆-CSDN博客 二叉树(2): 深入理解数据结构第二弹——二叉树(2)——堆排序及其时间复杂度-CSDN博客 前言: 在前面我们讲了堆及其应用,帮助我们初步了解了二叉树的一些原理,但那与真正的二叉树仍有不同,

    2024年04月09日
    浏览(48)
  • 数据结构实验4:二叉树的基本操作

    一、问题描述 运用二叉链表实现二叉树的基本操作,包括:创建二叉树的存储结构、复制已有的二叉树、计算已有的二叉树的深度、先根序序列、中根序序列、后根序序列等。 输入格式:AB#C##D## 二、实验目的 掌握二叉链表及二叉树的基本操作。 三、实验内容及要求 1、构造

    2024年01月23日
    浏览(42)
  • 【数据结构】二叉树的构建与基本操作实现

    👀 樊梓慕: 个人主页   🎥 个人专栏: 《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言 1.前序建立二叉树 2.销毁二叉树 3.统计 4.查找值为x的节点 5.前中后序遍历 6.层序遍历 7.判断二叉树是否

    2024年02月07日
    浏览(44)
  • 数据结构:二叉树的基本操作(用递归实现)

             本文将通过完成以下内容来展示二叉树的基本操作,代码解释标注全面而且清晰,代码书写也十分规范,适合初学者进行学习,本篇文章算是本人的一些学习记录分享,希望对有需要的小伙伴提供一些帮助~ 本文的内容为: 用递归的方法实现以下算法: 1.以二叉

    2024年02月06日
    浏览(49)
  • 【数据结构】二叉树的存储与基本操作的实现

    二叉树的存储结构分为: 顺序存储 和类似于 链表的链式存储 这里博主讲一下链式存储 二叉树的链式存储是通过一个一个的节点引用起来的,常见的表示方式有 二叉和三叉 表示方式 二叉表示: 三叉表示: 这里博主主要讲解一下孩子表示法 在学习二叉树的基本操作前,需

    2024年02月04日
    浏览(47)
  • 数据结构实验报告,二叉树的基本操作(C语言)

    作者:命运之光 专栏:数据结构 实验六 二叉树的基本操作 实验环境:Visual C++或Dev C++ 实验目的: 1、掌握二叉树创建; 2、掌握二叉树的遍历及常用算法。 实验内容: 通过完全前序序列创建一棵二叉树,完成如下功能: 1)输出二叉树的前序遍历序列; 2)输出二叉树的中序遍

    2024年02月09日
    浏览(37)
  • 二叉树的基本操作-C语言实现-数据结构作业

    目录  (1)二叉树的创建; (2)二叉树的先序、中序和后序遍历输出; (3)输出二叉树的叶子节点和度为2的节点的数量; (4)输出二叉树的深度; (5)将二叉树所有节点的左右子树互换(左子树变右子树,右子树变左子树); (6)参考书上,二叉树按层次输出(一行输出一层); (7)删除二

    2024年02月04日
    浏览(47)
  • 数据结构:二叉树及相关操作

    在实现二叉树前,我们要先对树产生一些基本的认识,才可以去实现它。树的用途非常广泛,向文件系统的目录树结构等。 树是一种 非线性的数据结构 ,它是由n(n=0)个有限结点组成一个具有层次关系的集合。 有一个特殊的结点,称为根结点,根节点没有前驱结点。 除根

    2024年02月11日
    浏览(45)
  • 数据结构和算法学习记录——初识二叉树(定义、五种基本形态、几种特殊的二叉树、二叉树的重要性质、初识基本操作函数)

    目录 二叉树的定义 二叉树具体的五种基本形态 1.空树 2.只有一个节点 3.有左子树,但右子树为空 4.有右子树,但左子树为空  5.左右两子树都不为空 特殊二叉树 斜二叉树 满二叉树  完全二叉树 二叉树的几个重要性质 初识二叉树的几个操作函数  二叉树T: 一个有穷的节点

    2024年02月03日
    浏览(60)
  • 【数据结构】树、二叉树的概念和二叉树的顺序结构及实现

    之前我们学习了顺序表、链表以及栈和队列这些数据结构,但这些数据结构都是线性的(一对一)。接下来要学习 非线性的数据结构——树(二叉树) ,相比前面的,树的结构更加复杂,话不多说,直接进入正题吧。 树是一种 非线性的数据结构 ,它是 一对多(也有可能是

    2024年02月07日
    浏览(41)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包