【数据结构】链式二叉树(超详细)

文章目录

  • 前言
  • 二叉树的链式结构
  • 二叉树的遍历方式
    • 二叉树的深度优先遍历
      • 前序遍历(先根遍历)
      • 中序遍历(中根遍历)
      • 后序遍历(后根遍历)
    • 二叉树的广度优先遍历
      • 层序遍历
  • 二叉树链式结构接口实现
    • 二叉树结点个数
    • 二叉树叶子结点个数
    • 二叉树的深度(高度)
    • 二叉树第k层结点个数
    • 二叉树查找x值的结点
    • 销毁二叉树
    • 二叉树的创建及遍历
  • 衍生题
    • 判断二叉树是否为完全二叉树
    • 判断二叉树是否为单值二叉树
    • 判断两颗二叉树是否相同
    • 判断二叉树是否为对称二叉树
    • 判断一颗二叉树是否为另一颗二叉树的子树
    • 判断二叉树是否为平衡二叉树
    • 翻转二叉树

前言

二叉树的顺序结构就是用数组来存储,而「数组」一般只适合表示「满二叉树」或「完全二叉树」,因为不是完全二叉树会有「空间的浪费」。
普通二叉树的增删查改没有意义,主要学习它的结构,要加上搜索树的规则,才有价值。

二叉树的链式结构

二叉树链式结构的实现
在学习二叉树的基本操作前,需先要创建一棵二叉树,这里手动快速创建一棵简单的二叉树

#include<stdio.h>  // perror, printf
#include<stdlib.h> // malloc




typedef char BTDataType;
// 定义二叉树的结点
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;






// 动态申请一个新结点
BTNode* BuyNode(BTDataType x)
{
	// 
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}

	newnode->data = x;
	newnode->left = newnode->right = NULL;

	return newnode;
}

// 二叉树的链式结构
BTNode* CreatBinaryTree()
{
	// 创建多个结点
	BTNode* node_A = BuyNode('A');
	BTNode* node_B = BuyNode('B');
	BTNode* node_C = BuyNode('C');
	BTNode* node_D = BuyNode('D');
	BTNode* node_E = BuyNode('E');
	BTNode* node_F = BuyNode('F');

	// 用链来指示结点间的逻辑关系
	node_A->left = node_B;
	node_A->right = node_C;
	node_B->left = node_D;
	node_C->left = node_E;
	node_C->right = node_F;

	return node_A;
}

注意:上述代码并不是创建二叉树的方式
在这里插入图片描述

二叉树的遍历方式

二叉树的深度优先遍历

由于被访问的结点必是「某子树的根」,所以N(Node)、L(Left subtree)和R(Right subtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

前序遍历(先根遍历)

遍历顺序:根->左子树->右子树

//前序遍历
void BinaryPrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	//根->左子树->右子树
	printf("%c ", root->data);
	BinaryPrevOrder(root->left);
	BinaryPrevOrder(root->right);
}

这里的访问路径是:A B D NULL NULL NULL C E NULL NULL F NULL NULL

在这里插入图片描述

接下来的两个遍历可以自己试试画一下递归图。

中序遍历(中根遍历)

遍历顺序:左子树->根->右子树

void BinaryInOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	//左子树->根->右子树
	BinaryInOrder(root->left);
	printf("%c ", root->data);
	BinaryInOrder(root->right);
}

这里的访问路径是:NULL D NULL B NULL A NULL E NULL C NULL F NULL

后序遍历(后根遍历)

遍历顺序:左子树->右子树->根

//后序遍历
void BinaryPostOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	//左子树->右子树->根
	BinaryPostOrder(root->left);
	BinaryPostOrder(root->right);
	printf("%c ", root->data);
}

这里的访问路径是:NULL NULL D NULL B NULL NULL E NULL NULL F C A

二叉树的广度优先遍历

层序遍历

层序遍历,自上而下,从左往右逐层访问树的结点的过程就是层序遍历。
在这里插入图片描述
我们借助队列来实现:
先入根结点,然后出队列,再入他的两个孩子,然后一样的出孩子,再入孩子的孩子,重复即可。(NULL不入)
在这里插入图片描述

//层序遍历
void BinaryLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);//初始化队列
	if (root != NULL)
		QueuePush(&q, root);

	int levelSize = 1;
	while (!QueueEmpty(&q))//当队列不为空时,循环继续
	{
		//一层一层出
		while (levelSize--)
		{
			BTNode* front = QueueFront(&q);//读取队头元素
			QueuePop(&q);//删除队头元素
			printf("%c ", front->data);//打印出队的元素
			if (front->left)
			{
				QueuePush(&q, front->left);//出队元素的左孩子入队列
			}
			if (front->right)
			{
				QueuePush(&q, front->right);//出队元素的右孩子入队列
			}
		}
			printf("\n");
			levelSize = QueueSize(&q);
	}
	printf("\n");
	QueueDestroy(&q);//销毁队列
}

二叉树链式结构接口实现

二叉树结点个数

子问题拆解:
 1.若为空,则结点个数为0。
 2.若不为空,则结点个数 = 左子树结点个数 + 右子树结点个数 + 1(自己)。

//结点的个数
int BinaryTreeSize(BTNode* root)
{
	//结点个数 = 左子树的结点个数 + 右子树的结点个数 + 自己
	return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

在这里插入图片描述

二叉树叶子结点个数

子问题拆解:
 1.若为空,则叶子结点个数为0。
 2.若结点的左指针和右指针均为空,则叶子结点个数为1。
 3.除上述两种情况外,说明该树存在子树,其叶子结点个数 = 左子树的叶子结点个数 + 右子树的叶子结点个数。

//叶子结点的个数
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);
}

在这里插入图片描述

二叉树的深度(高度)

子问题拆解:

  1. 先判断当前树的根结点是否为空
  2. 当前树的根结点不为空,分别计算其左右子树的深度
  3. 比较当前树左右子树的深度,最大的那个+1 就是当前树的深度
// 二叉树的深度(高度)
int BinaryTreeMaxDepth(BTNode* root)
{
	// 先判断当前树的根结点是否为空
	if (root == NULL)
	{
		return 0;
	}

	// 当前树的根结点不为空,分别计算其左右子树的深度
	int leftDepth = BinaryTreeMaxDepth(root->left);
	int rightDepth = BinaryTreeMaxDepth(root->right);

	// 比较当前树左右子树的深度,最大的那个+1 就是当前树的深度
	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

在这里插入图片描述

二叉树第k层结点个数

//第k层结点的个数O(N)
int BinaryTreeKLevelSize(BTNode* root, int k)
{
	assert(k > 0);
	if (root == NULL)
		return 0;
	if (k == 1)//第一层结点个数
		return 1;
	//相对于父结点的第k层的结点个数 = 相对于两个孩子结点的第k-1层的结点个数之和
	return BinaryTreeKLevelSize(root->left, k - 1) 
		+ BinaryTreeKLevelSize(root->right, k - 1);
}

在这里插入图片描述

二叉树查找x值的结点

//查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)//空树
		return NULL;
	if (root->data == x)//先判断根结点
		return root;
	BTNode* leftret = BinaryTreeFind(root->left, x);//在左子树中找
	if (leftret)
		return leftret;
	BTNode* rightret = BinaryTreeFind(root->right, x);//在右子树中找
	if (rightret)
		return rightret;
	return NULL;//根结点和左右子树中均没有找到
}

在这里插入图片描述

销毁二叉树

这里要用后序遍历来销毁,左子树->右子树->根

//销毁二叉树
void BinaryTreeDestroy(BTNode* root)
{
	if (root == NULL)
		return;
	BinaryTreeDestroy(root->left);
	BinaryTreeDestroy(root->right);
	free(root);//没有用二级指针,这里只是实参的拷贝,需要用完主动置空再函数外置空
	
}

二叉树的创建及遍历

编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以指针方式存储)。
例如如下的先序遍历字符串: ABC##DE#G##F### 其中“#”表示的是空格,空格字符代表空树。建立起此二叉树以后,再对二叉树进行中序遍历,输出遍历结果。

在这里插入图片描述

依次读取字符,拆分成子问题:
1.如果不是#,创建结点,存值,然后递归其左子树和右子树;
2.如果是#,说明不能构建结点了,直接返回NULL;

#include <stdio.h>

typedef char  BTDataType;
typedef struct BinaryTreeNode{
    BTDataType data;
    struct BinaryTreeNode*left;
    struct BinaryTreeNode*right;

}BTNode;



BTNode*BinaryTreeCreat(char*arr,int*pi)
{
    if(arr[*pi]=='#')
    {
        (*pi)++;
        return NULL;
    }
    BTNode*node=(BTNode*)malloc(sizeof(BTNode));
    node->data=arr[*pi];
    (*pi)++;
    node->left=NULL;
    node->right=NULL;
node->left=BinaryTreeCreat(arr,pi);//递归构建左子树
node->right=BinaryTreeCreat(arr,pi);//递归构建右子树
return node;
}

//中序遍历
void BinaryInOrder(BTNode*root)
{
    if(root==NULL)
    return;
    
    BinaryInOrder(root->left);
    printf("%c ",root->data);
    BinaryInOrder(root->right);
}




int main() {
char ret[100];
scanf("%s",&ret );
int i=0;
BTNode*root= BinaryTreeCreat(ret,&i);
BinaryInOrder(root);
printf("\n");



    return 0;
}

衍生题

判断二叉树是否为完全二叉树

用一个队列来判断
将根从队尾入列,然后从队头出数据,出根的时候入它的左孩子和右孩子,NULL也入列。重复次操作,当出数据第一次遇到NULL时,停止入队列并且检查队列中是否还有数据,如果全部为NULL则此树时完全二叉树
如果队列中还有数据,则不是完全二叉树。

// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);//初始化队列
	if (root != NULL)
		QueuePush(&q, root);
	while (!QueueEmpty(&q))//当队列不为空时,循环继续
	{
		BTNode* front = QueueFront(&q);//读取队头元素
		QueuePop(&q);//删除队头元素
		//遇到第一个NULL结点直接跳出循环
		if (front == NULL)
			break;
		QueuePush(&q, front->left);//出队元素的左孩子入队列(NULL也入)
		QueuePush(&q, front->right);//出队元素的右孩子入队列(NULL也入)
	}

	//前面遇到空以后,后面还有非空就不是完全二叉树
	while (!QueueEmpty(&q))//当队列不为空时,循环继续
	{
		BTNode* front = QueueFront(&q);//读取队头元素
		QueuePop(&q);//删除队头元素
		if (front)
		{
			QueueDestroy(&q);//销毁队列
			return false;
		}

	}
	//没有遇到说明是完全二叉树
	QueueDestroy(&q);//销毁队列
	return true;
}

判断二叉树是否为单值二叉树

单值二叉树,所有结点的值都相同的二叉树即为单值二叉树,判断某一棵二叉树是否是单值二叉树的一般步骤如下:
 1.判断根的左孩子的值与根结点是否相同。
 2.判断根的右孩子的值与根结点是否相同。
 3.判断以根的左孩子为根的二叉树是否是单值二叉树。
 4.判断以根的右孩子为根的二叉树是否是单值二叉树。
若满足以上情况,则是单值二叉树。

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);
}

判断两颗二叉树是否相同

拆分成子问题:
先判断根是否为空
再比较根的左子树是否相同
再比较跟根的右子树是否相同

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(p->right,q->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;
   return  isSameTree(p->left,q->right)&&isSameTree(p->right,q->left);
 }


   
bool isSymmetric(struct TreeNode* root) {

 if(root==NULL)
 return true;
 return isSameTree(root->left,root->right);
    
}

判断一颗二叉树是否为另一颗二叉树的子树

两个树都是空树,返回true
如果两个树一个是空,一个不是空,不包含
两个树都是非空,比较根节点的值是不是相等,如果相等的话,比较一下p和q是不是相同的树
递归的判定一下,p是否被q的左子树包含
递归的判定一下,p是否被q的右子树包含。

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(p->right,q->right);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    if(root==NULL)
    return false;
    if(isSameTree(root->left,subRoot))
    return true;
    return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);


}

判断二叉树是否为平衡二叉树

如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。
子问题:
求出左子树的深度。
求出右子树的深度。
若左子树与右子树的深度差的绝对值不超过1,并且左右子树也是平衡二叉树,则该树是平衡二叉树。

int max(int x,  int y)
{
    return x>y?x:y;
}
int height(struct TreeNode* root)
{
    if (root == NULL) 
        return 0;
        return max(height(root->left), height(root->right)) + 1;
}

bool isBalanced(struct TreeNode* root)
{
    if (root == NULL) 
        return true;
        //左右子树高度差的绝对值不超过1 && 其左子树是平衡二叉树 && 其右子树是平衡二叉树
        return fabs(height(root->left) - height(root->right)) <= 1 && 
        isBalanced(root->left) &&
         isBalanced(root->right);//fabs取绝对值,要用要包含头文件#include<math.h>
}

翻转二叉树

子问题:
 翻转左子树。
 翻转右子树。
 交换左右子树的位置。

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

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

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

相关文章

植物大战僵尸杂交版下载链接

前言 植物大战僵尸杂交版是 潜艇伟伟迷 制作并免费向大家开放畅玩并且持续更新关卡。 下载教程 1.打开作者主页&#xff1a;https://space.bilibili.com/97213827/dynamic 2.作者置顶发布的是最新版&#xff0c;直接打开链接安装就好了 3.下载链接&#xff1a;https://pan.qu…

DL-33G电流继电器 新型导轨安装 JOSEF约瑟

用途 DL-30系列电流继电器&#xff0c;用于电机、变压器和输电线的过负荷和短路保护线路中&#xff0c;作为起动元件。 技术参数 按整定值的范围来分:每整定值的动作误差不大于6% 继电器刻度极限误差不大于6%。 动作值的变差不大于6% 对于DL-31、32、33、34电流继电器的返…

【第3章】SpringBoot实战篇之登录接口(含JWT和拦截器)

文章目录 前言一、JWT1. 什么是JWT2. 使用场景3. 结构3.1 Header3.2 Payload3.3 Signature 4. 使用 二、案例1.引入库2.JwtUtils3. UserController14. ArticleController 三、拦截器1. 定义拦截器2. 注册拦截器 四、测试1. 登录2. 无token3. 有token4. 全局配置 总结 前言 前面…

vscode怎么点击路径直接跳转对应文件

在vue项目中经常要引入工具类、组件、模版等&#xff0c;想要直接去看对应文件&#xff0c;只能自己找到对应路径再去打开。 我们可用在js项目中创建一个 jsconfig.json文件&#xff0c;TS项目可以创建tsconfig.json 文件代码 {"compilerOptions": {"baseUrl&…

批量归一化(BN)和层归一化(LN)的区别

批量归一化&#xff08;Batch Normalization, BN&#xff09;和层归一化&#xff08;Layer Normalization, LN&#xff09;是深度学习中常用的两种归一化技术&#xff0c;它们主要用于解决训练过程中的内部协变量偏移问题&#xff0c;加速模型收敛和提高稳定性。 1. 为什么需要…

智能工厂生产设备实时监控技术的UI设计

智能工厂生产设备实时监控技术的UI设计

Java面试八股之死锁和饥饿的区别

死锁和饥饿的区别 定义与现象&#xff1a; 死锁&#xff08;Deadlock&#xff09;是指两个或多个线程互相等待对方持有的资源而无法继续执行的情况。每个线程至少持有一个资源&#xff0c;并尝试获取另一个由其他线程持有的资源&#xff0c;从而形成一个循环等待的僵局&#…

QAnything-1.4.01.4.1版本更新!使用指北!

久等了各位&#xff01;时隔一个多月&#xff0c;我们在4月26日和5月20日接连发布了v1.4.0和v1.4.1两个版本&#xff0c;带来了问答性能&#xff0c;解析效果等多方面的改进&#xff0c;并新增了大量的新功能和新特性 详见&#xff1a;releases 以及 使用说明 最新特性表 开发…

Android 调试桥_ADB命令

Android 调试桥 ADB全称 【Android Debug Bridge】 是Android SDK中的一个命令行工具&#xff0c;adb命令可以直接操作管理Android模拟器或真实的Android设备&#xff08;手机&#xff09; ADB的工作原理 启动一个 adb 客户端时&#xff0c;此客户端首先检查是否有已运行的 …

1961. 检查字符串是否为数组前缀 - 力扣

1. 题目 给你一个字符串 s 和一个字符串数组 words &#xff0c;请你判断 s 是否为 words 的 前缀字符串 。 字符串 s 要成为 words 的 前缀字符串 &#xff0c;需要满足&#xff1a;s 可以由 words 中的前 k&#xff08;k 为 正数 &#xff09;个字符串按顺序相连得到&#xf…

kaggle竞赛系列基于图像对水稻分类代码案例

目录 依赖环境 代码 导入依赖包 定义数据集路径&#xff1a; 创建训练集、验证集和测试集的文件夹&#xff1a; 代码的作用&#xff1a; 设置新的数据集路径与类别名称 代码的作用&#xff1a; 定义数据预处理和增强变换&#xff1a; 代码的作用&#xff1a; 定义数…

Appium自动化环境搭建保姆级教程

APP自动化测试运行环境比较复杂&#xff0c;稍微不注意安装就会失败。我见过不少朋友&#xff0c;装了1个星期&#xff0c;Appium 的运行环境还没有搭好的。 搭建环境本身不是一个有难度的工作&#xff0c;但是 Appium 安装过程中确实存在不少隐藏的比较深的坑&#xff0c;如果…

kafka-集群搭建(在docker中搭建)

文章目录 1、kafka集群搭建1.1、下载镜像文件1.2、创建zookeeper容器并运行1.3、创建3个kafka容器并运行1.3.1、9095端口1.3.2、9096端口1.3.3、9097端口 1.4、重启kafka-eagle1.5、查看 efak1.5.1、查看 brokers1.5.2、查看 zookeeper 1、kafka集群搭建 1.1、下载镜像文件 d…

Vuforia AR篇(五)— 地平面检测

目录 前言一、什么是地平面识别&#xff1f;二、使用步骤三、示例代码四、效果五、总结 前言 在增强现实&#xff08;AR&#xff09;应用程序的开发中&#xff0c;地平面识别是一项关键技术&#xff0c;它允许虚拟对象与现实世界的地面进行互动。Vuforia 是一个功能强大的 AR …

javacv ffmpeg使用笔记 (补充中...)

javacv ffmpeg使用笔记 一、maven依赖二、示例代码1. 获取视频时长 三、小技巧 一、maven依赖 使用javacv ffmpeg并指定classifier之后&#xff0c;就不需要额外安装ffmpeg软件&#xff08;jar包中已经内置&#xff09;了。 全量依赖包&#xff08;不推荐&#xff09;安装包总大…

6、架构-服务端缓存

为系统引入缓存之前&#xff0c;第一件事情是确认系统是否真的需要缓 存。从开发角度来说&#xff0c;引入缓存会提 高系统复杂度&#xff0c;因为你要考虑缓存的失效、更新、一致性等问题&#xff1b;从运维角度来说&#xff0c;缓存会掩盖一些缺 陷&#xff0c;让问题在更久的…

HashMap的get和put方法

在 JDK 1.8 中&#xff0c;HashMap 是一个常用的实现了 Map 接口的哈希表&#xff0c;它允许存储键值对&#xff0c;并且键和值都可以为 null。HashMap 的主要特点是其基于哈希表的实现&#xff0c;提供了快速的查找和插入操作。以下是 HashMap 中 get 和 put 方法的介绍及其实…

Flink状态State | 大数据技术

⭐简单说两句⭐ ✨ 正在努力的小叮当~ &#x1f496; 超级爱分享&#xff0c;分享各种有趣干货&#xff01; &#x1f469;‍&#x1f4bb; 提供&#xff1a;模拟面试 | 简历诊断 | 独家简历模板 &#x1f308; 感谢关注&#xff0c;关注了你就是我的超级粉丝啦&#xff01; &a…

使用J-LINK COMMANDER检查极海APM32F072烧录

键入 connect: 此时会显示默认设备&#xff0c;如果之前设置过会有&#xff0c;为了演示&#xff0c;我不选 键入 &#xff1f; 然后会弹出设备选择界面&#xff1a; 根据自己的设备搜索型号&#xff1a; 我这里搜索“APM32F072VB”,点击OK: 选择接口类型&#xff1a; 如果要…

用Python优雅地写LaTeX

latexify用于生成 LaTeX 数学公式的 Python 库。LaTeX 是一种基于 ΤΕΧ 的排版系统&#xff0c;对于展示复杂的数学公式表现极为出色。该项目可以用 Python 函数&#xff0c;轻松生成复杂的 LaTeX 数学公式描述。 安装库 查看版本号 0.4.2 案例演示 我们需要以装饰器的形式…