二叉树概述

目录

一、二叉树的基本结构

二、二叉树的遍历

1.前序

2.中序

3.后序 

4.层序遍历 

三.计算二叉树的相关参数

1.计算节点总个数

 2.计算叶子节点的个数

 3.计算树的高度

4.计算第k层的子树个数

 5.查找树中val为x的节点

 四.刷题

1.单值二叉树

2.检查两棵树是否相同

3.一棵树是否对称


二叉树的实现源码_gitee


一、二叉树的基本结构

 这里的二叉树比堆的定义更广泛,

heap=>完全二叉树/满二叉树

二叉树=>二叉,不成图(没有闭合圈)

二、二叉树的遍历

1.前序

NULL用‘#’表示,下面实例的val是char类型

void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}
	printf("%c ", root->_data);
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);



}

这里使用的是递归式的遍历,因为二叉树可以看作子树,而子树又可以看作根和子树

注意,这里的return 是指返回上一层的递归,下面是部分运行逻辑

2.中序

void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}
	BinaryTreeInOrder(root->_left);
	printf("%c ", root->_data);
	BinaryTreeInOrder(root->_right);

}

3.后序 

void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}
	BinaryTreePostOrder(root->_left);
	BinaryTreePostOrder(root->_right);
	printf("%c ", root->_data);
}

4.层序遍历 

这里要使用队列,先根节点入队,根节点出队后,对应的左右子树节点入队,左子树节点作为根节点出队,再有对应的左右子树节点入队,以此类推

void BinaryTreeLevelOrder(BTNode* root)
{

	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);

	while(!QueueEmpty(&q))
	{
		BTNode* cur = QueueFront(&q);
		QueuePop(&q);
		printf("%c ", cur->_data);

		if (cur->_left)
			QueuePush(&q, cur->_left);
		if(cur->_right)
			QueuePush(&q, cur->_right);
	
	}



}


这是带有换行效果的层序遍历,实现原理是需要记录每一层的个数,方便pop 完一层接一个换行

void BinaryTreeLevelOrder(BTNode* root)
{
	
	Queue Bq;
	QueueInit(&Bq);
	QueuePush(&Bq, root);
	int popnum = QueueSize(&Bq);

	while(!QueueEmpty(&Bq))
	{
	while(popnum--)
	{
		BTNode* cur = QueueFront(&Bq);
		QueuePop(&Bq);
		printf("%c ", cur->_data);
		if(cur->_left!=NULL)
		{
			QueuePush(&Bq, cur->_left);
		}
		
		if(cur->_right!=NULL)
		{
			QueuePush(&Bq, cur->_right);
		}


	}
	popnum = QueueSize(&Bq);
	printf("\n");

	}




}

三.计算二叉树的相关参数

1.计算节点总个数

思路1:遍历二叉树,不过要传入一个可以记录的参数,为了这个参数可以随遍历而变化,不能传入实参拷贝为形参这一套

解决方法:

1.使用static参数,在函数内定义,只要把static的值最后return,在全局则可以不用,直接查static的值,弊端:这个函数不能再同一个程序里重复调用,因为static的值不会再从0开始 

2.在参数列表里多传入一个int *size,每次++时就(*size)++,在进入下一个递归


 思路2:递归计数,

当root==NULL,   return 0;

当root不为NULL时,return 1+左子树的个数+右子树的个数

int BinaryTreeSize(BTNode* root)
{
if(root==NULL)
{

	return 0;
}
return 1 + BinaryTreeSize(root->_right) + BinaryTreeSize(root->_left);



}

 2.计算叶子节点的个数

思路:递归计数,叶子节点时左右子树都为NULL时,

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

 3.计算树的高度

int nummax(int p1, int p2)
{
	return p1 > p2 ? p1 : p2;

	 
}
int tree_height(BTNode* root)
{
	if(root==NULL)
	{
		return 0;
	}

return 1 + nummax(height(root->_left),height(root->_right));

}

4.计算第k层的子树个数

 思路:距离root为k,那么距离root的下一层为k-1,当k==1时,就是递归到第k层了

root==NULL,return 0

root!=NULL&&k==1,return 1;

其他情况:return knum(root->left,k-1)  +  knum(root->right,k-1)

int knum(BTNode* root,int k)
{
	if(root==NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;

	}

	return knum(root->left, k - 1) + knum(root->right, k - 1);

}

 5.查找树中val为x的节点

思路:递归遍历+比较是否为x

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->_data == x)
	{
		return root; 
	}

	BTNode* node1 = BinaryTreeFind(root->_left, x);
	if (node1) { return node1; }
	return BinaryTreeFind(root->_right, x);

}

 

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

思路:以层序遍历对二叉树进行收集(此时NULL也收入),在每个节点开始pop时,判断是否为NULL,一旦为NULL,则跳出循环,开始判断NULL之后的队列是否全为NULL,

如果全为NULL==>是完全二叉树

如果不是==>不是

bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* cur = QueueFront(&q);
		QueuePop(&q);
		if (cur == NULL)
			break;
		

		
			QueuePush(&q, cur->_left);
		
			QueuePush(&q, cur->_right);

	}


	while (!QueueEmpty(&q))
	{
		BTNode* cur = QueueFront(&q);
		QueuePop(&q);
		if (cur != NULL)
		{
			QueueDestroy(&q);
			return false;
		}
	
	
	
	}



	QueueDestroy(&q);
	return true;


}

 

 四.刷题

1.单值二叉树

bool _isUnivalTree(struct TreeNode* root,int val)
{
if(root==NULL)
return true;

if(root->val!=val)
return false;


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

}


bool isUnivalTree(struct TreeNode* root) {
    int val=root->val;
return _isUnivalTree(root,val);


}

2.检查两棵树是否相同

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

 }

3.一棵树是否对称

bool issame(struct TreeNode* p1, struct TreeNode* p2)
{


	if (p1 == NULL && p2 == NULL)
	{

		return true;
	}
	if (p1 == NULL || p2 == NULL)
	{

		return false;
	}
	if (p1->val != p2->val) { return false; }
	
	return issame(p1->left, p2->right)&&
	issame(p1->right, p2->left);
}
bool isSymmetric(struct TreeNode* root) {

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


}


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

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

相关文章

04 创建一个属于爬虫的主虚拟环境

文章目录 回顾conda常用指令创建一个爬虫虚拟主环境Win R 调出终端查看当前conda的虚拟环境创建 spider_base 的虚拟环境安装完成查看环境是否存在 为 pycharm 配置创建的爬虫主虚拟环境选一个盘符来存储之后学习所写的爬虫文件用 pycharm 打开创建的文件夹pycharm 配置解释器…

weblogic开启https

JSK证书生成 生成密钥库和证书 使用Java的keytool命令来生成一个Java密钥库(Keystore)和证书。keytool是Java开发工具包(JDK)中用于管理密钥库和证书的命令行工具。 #创建证书存放目录 [weblogicosb1 jksHL]$ mkdir -p /home/w…

学习记录,正则表达式, 隐式转换

正则表达式 \\:表示正则表达式 W: 表示一个非字(不是一个字,例如:空格,逗号,句号) W: 多个非字 基本组成部分 1.字符字面量: 普通字符:在正则表达式中,大…

防火墙有什么作用

防火墙的作用:1. 提供网络安全防护;2. 实施访问控制和流量过滤;3. 检测和阻止恶意攻击;4. 保护内部网络免受未经授权的访问;5. 监控网络流量和安全事件;6. 支持虚拟专用网络(VPN)。防…

linux中启动oracle19c操作过程及详解

1.登录Oracle用户 su - oracle2.启动监听程序 监听器(Listener)是Oracle数据库与客户端通信的桥梁。使用以下命令启动监听器: lsnrctl start如图情况监控程序启动成功。 3.启动数据库实例 使用 sqlplus 工具以 SYSDBA 权限连接到数据库&a…

ainiworth 在分布式目标的方程中 与正常互易性可以形成的方程不同 多引入了协方差元素未知 但可解,因为此时只有一个串扰参数且已经解出来了

这个散射互易性,在不考虑AB时 方程应该只剩两个即 HVHV VHVH 和VHHV相位(虚部) 0 但是这一组方程却可以解4个参数未知数。C元素是观测的已知。 β表示真实协方差矩阵,Σ是恢复的协方差(也可以认为是真实协方差元素) 1、首先把方…

10a大电流稳压芯片_24v转3.3v稳压芯片,高效率DC-DC变换器10A输出电流芯片-AH1514

### AH1514——高性能的大电流稳压芯片 在现代电子电路设计中,对于能够满足大电流、高效率转换以及稳定电压输出的芯片需求日益增长。AH1514芯片作为一款出色的DC-DC变换器,以其独特的性能特点,在众多应用场景中展现出了卓越的优势. ### 一…

【网络篇】HTTP知识

键入网址到网页显示,期间发生了什么? 浏览器第一步是解析URL,这样就得到了服务器名称和文件的路径名,然后根据这些信息生成http请求,通过DNS查询得到我们要请求的服务器地址,然后添加TCP头、IP头以及MAC头&…

pdf转word/markdown等格式——MinerU的部署:2024最新的智能数据提取工具

一、简介 MinerU是开源、高质量的数据提取工具,支持多源数据、深度挖掘、自定义规则、快速提取等。含数据采集、处理、存储模块及用户界面,适用于学术、商业、金融、法律等多领域,提高数据获取效率。一站式、开源、高质量的数据提取工具&…

github使用SSH进行克隆仓库

SSH 密钥拉取git 查询密钥是否存在 s -al ~/.ssh这个文件夹下 known_hosts 就是存在的密钥文件 创建密钥文件 ssh-keygen -t rsa -b 4096 -C "testtt.com"-t rsa 是 rsa 算法加密 -b 是指定密钥的长度(以位为单位)。 -C 是用于给密钥添加注…

【MARL】MAT论文阅读笔记

文章目录 前言一、如何产生这个想法(TRPO -> ) PPO -> MAPPO -> HAPPO -> MAT 二、多智能体优势值分解定理三、transformer 在MAT的应用四、伪代码简述五、实验效果 前言 正好有节课让我们调研最新的自己的方向的新论文,找到一篇自己觉得比较可行&…

代码随想录32 动态规划理论基础,509. 斐波那契数,70. 爬楼梯,746. 使用最小花费爬楼梯。

1.动态规划理论基础 动态规划刷题大纲 什么是动态规划 动态规划,英文:Dynamic Programming,简称DP,如果某一问题有很多重叠子问题,使用动态规划是最有效的。 所以动态规划中每一个状态一定是由上一个状态推导出来的…

基于SpringBoot的社区医院管理系统(代码+论文)

🎉博主介绍:Java领域优质创作者,阿里云博客专家,计算机毕设实战导师。专注Java项目实战、毕设定制/协助 📢主要服务内容:选题定题、开题报告、任务书、程序开发、项目定制、论文辅导 💖精彩专栏…

Leetcode 每日一题 49.字母异位词分组

目录 问题描述 示例 示例 1 示例 2 示例 3 约束条件 解决方案 思路 算法步骤 过题图片 代码实现 复杂度分析 题目链接 结论 问题描述 给定一个字符串数组,需要将其中的字母异位词分组。字母异位词是指通过重新排列源单词的所有字母得到的新单词。要求…

进程控制(下)

进程控制(下) 进程程序替换 fork() 之后,⽗⼦各⾃执⾏⽗进程代码的⼀部分如果⼦进程就想执⾏⼀个全新的程序呢?进程的程序 替换来完成这个功能! 程序替换是通过特定的接⼝,加载磁盘上的⼀个全新的程序(代码和数据)&am…

安全关系型数据库查询新选择:Rust 语言的 rust-query 库深度解析

在当今这个数据驱动的时代,数据库作为信息存储和检索的核心组件,其重要性不言而喻。然而,对于开发者而言,如何在保证数据安全的前提下,高效地进行数据库操作却是一项挑战。传统的 SQL 查询虽然强大,但存在诸…

读取电视剧MP4视频的每一帧,检测出现的每一个人脸并保存

检测效果还不错,就是追踪有点难做 import cv2 import mediapipe as mp import os from collections import defaultdict# pip install msvc-runtime# 初始化OpenCV的MultiTracker # multi_tracker = cv2.MultiTracker_create() # multi_tracker = cv2.legacy.MultiTracker_cre…

【AI系统】Transformer 模型小型化

Transformer 模型小型化 自 Vision Transformer 出现之后,人们发现 Transformer 也可以应用在计算机视觉领域,并且效果还是非常不错的。但是基于 Transformer 的网络模型通常具有数十亿或数百亿个参数,这使得它们的模型文件非常大&#xff0…

hhdb数据库介绍(10-43)

安全 密码安全管理 密码安全管理为用户提供了对计算节点数据库用户与存储节点的连接用户、备份用户的密码有效期监控提醒。到期后自动提示用户修改密码以提升系统的安全性。 数据库用户密码 (一)密码修改 用户可以在“安全->密码安全管理->数据…

MagicAnimate 技术浅析(五):视频融合策略浅析

视频融合策略(Video Fusion Strategy)是 MagicAnimate 中用于处理长视频动画生成的关键组件。它通过将长视频分解为多个重叠的片段,并在推理过程中对重叠帧的预测结果进行融合,确保生成的长视频动画在时间上平滑过渡,避…