初识二叉树

文章目录

  • 一.什么是树
  • 二.什么是二叉树
  • 三.二叉树的访问次序
  • 四.特殊的二叉树
  • 五.求结点个数
  • 六.平衡二叉树
  • 总结

一.什么是树

树是由一个集合以及在该集合上定义的一种关系构成的。 集合中的元素称为树的节点,所定义的关系称为父子关系。 父子关系在树的节点之间建立了一个层次结构。 在这种层次结构中有一个节点具有特殊的地位,这个节点称为该树的根节点,或称为树根。

结点

结点是数据结构中的基础,是构成复杂数据结构的基本组成单位。

结点的度

结点拥有的子树数目称为结点的度。

二.什么是二叉树

二叉树是n(n>=0)个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。

特点

1.每一个节点最多有两棵子数,及二叉树不存在度大于二的节点

2.二叉树的子树有左右之分,其子树的次序不能够颠倒

3.任何一个二叉树都有三部分,根节点左子树右子树

结构

typedef int	BTDataType;
typedef struct Binary TreeNode
{
	struct Binary TreeNode* left;//左孩子
	struct Binary TreeNode* right;//右孩子
	BTDataType data;//数据
}BTNode;

三.二叉树的访问次序

3.1前序遍历 (根结点 > 左子树 > 右子树)

主要是利用了函数递归的方法去遍历,先根节点左子树右子树不断地去调用自己

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

3.2中序遍历和后序遍历

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

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

3.3层序遍历

前中后序遍历其实也叫深度优化遍历,序遍历叫广度优化遍历

我们利用队列来实现层序遍历

核心思路:上一层带下一层的

先创造一个队列,如果跟节点不为空的话,把根节点放入这个队列中,循环的判断条件被列中没有元素就停下来,有元素就继续去队列投元素,放入树的头,然后再删去队列这个元素,然后把删去元素所对应的左子树和右子树放入,一层一层的遍历

void LeveOrder(BTNode* root)
{
	//创建队列
	Queue q;
	Queue Init(&q);
	//如果根节点不为空,在队列里放入
	if (root != NULL)
	{
		QueuePush(&q, root);
	}

	while (!QueueEmpty(&q))
	{
		//删去元素所对应的左子树和右子树放入一层一层的遍历
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%c", front->data);
		if (front->left != NULL)
		{
			QueuePush(&q, front->left);
		}
		if (front->right != NULL)
		{
			QueuePush(&q, front->right);
		}
	}
	printf("\n");
	QueueDestory(&q);
}

四.特殊的二叉树

4.1满二叉树

假设一个满二叉树的高为h,则它的总结点个数为N,则高为2^0+2^1+....+2^(h-1)=N,h=log2(N+1)

4.2完全二叉树

特征:1.前n-1层是满的。2.最后一层不满,但最后一层从左往右都是连续的

特别公式:对于任何一颗二叉树,如果度为零的叶子节点个数为n0,度为二的分支节点个数为n2则n0=n2+1

例:存在一个2n个结点的完全二叉树,则它的叶子结点大小的个数为__

完全二叉树度为1的结点个数要么是1个,要么没有。设度为0的结点为x0,度为1的为x1,度为二的为x2,所以说套入两个公式,x0+x1+x2=2n,x0=x2+1.可以算出2x0+x1-1=2n,又因为完全二叉树所以x1为0或者1,带入可得n或者2n+1/2

五.求结点个数

其实二叉树还有一个平衡结构,叫做平衡二叉树,需要非常灵活的掌握函数递归和分治的思想,所以我们先来利用递归和分治思想来求一下结点

5.1求叶子结点的个数

利用递归和分治的思想

int TreeLeafsize(BTNode* root)
{
	if (root == NULL)
		return 0;
	//如果左子树和右子树都为空说明找到了一个叶子结点,返回1
	if (root->left == NULL && root->right == NULL)
	   return 1;
	//利用函数递归的思路,先左子树在右
	return TreeLeafsize(root->left) + TreeLeafsize(root->right);
}

5.2求总结点个数

void Treesize(BTNode* root, int* psize)
{
	if (root == NULL)
	{
		return;
	}
	//是结点就加加
	else
	{
		(*psize++);
	}
	//也是递归,分治先左子树在右子树
	Treesize(root->left,psize);
	Treesize(root->right,psize);
}

六.平衡二叉树

定义:平衡二叉树也叫AVL树,它或者是一颗空树,或者具有以下性质的二叉排序树:它的左子树和左子树的高度之差(平衡因子)的绝对值不超过1,且它的左子树和右子树都是一颗平衡二叉树。

6.1二叉树的深度

分治思路:如果为空高度直接为零,非空就分解子问题,先求左右指数的深度,我的深度等于左右,质数深度大的大小,加1。

int maxDepth(BTNode* root)
{
	if (root == NULL)
		return 0;
	int leftDepth = maxDepth(root->left);
	int rightDepth= maxDepth(root->right);
	//左边的深度如果大于右边的话,就加1反之右边加1
	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

6.2平衡树的判断

bool isBalaned(BTNode* root)
{
	//第一种情况,如果为空的话就是的
	if (root == NULL)
		return true;
	//利用深度函数来求出左右子树的深度
	int leftDepth = maxDepth(root->left);
	int rightDepth = maxDepth(root->right);
	//利用递归判断高度差的绝对值不超过1,左右都要是平衡二叉(递归)
	return abs(leftDepth - rightDepth) < 2 && isBalaned(root->left) && isBalaned(root->right);
}


总结

这只是初次学习二叉树,它的内容可不只有这些,还要深度的还需要不断的学习积累才可实现

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

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

相关文章

【C++ leetcode】双指针问题

1. 611. 有效三角形的个数 题目 给定一个包含非负整数的数组 nums &#xff0c;返回其中可以组成三角形三条边的三元组个数。 题目链接 . - 力扣&#xff08;LeetCode&#xff09; 画图 和 文字 分析 判断是否是三角形要得到三边&#xff0c;由于遍历三边要套三层循环&#x…

LeetCode每日一题【24. 两两交换链表中的节点】

思路&#xff1a;先创建虚拟头结点&#xff0c;再用双指针&#xff0c;两两交换 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr…

推荐几个自动化测试实战练习项目

学习自动化测试最难的是没有合适的项目练习。 测试本身既要讲究科学&#xff0c;又有艺术成分&#xff0c;单单学几个 API 的调用很难应付工作中具体的问题。 你得知道什么场景下需要添加显性等待&#xff0c;什么时候元素定位需要写得更加优雅&#xff0c;为什么需要断言这个…

js处理数组分类

const obj [{"groupingType": "1","remark": "梨花带雨","totalRmbMoney": 7,"kyeGroupingType": "广州一组"},{"groupingType": "2","remark": "99","…

权限管理系统-0.6.0

七、员工端审批 员工端审批的大致流程如下图&#xff1a; 这个模块目的是实现员工在微信端的审批提交和处理功能&#xff0c;为了与之前的管理系统区分开&#xff0c;新建一个controller完成这些功能。 7.1 查询审批分类和审批模板 7.1.1 后端接口 //controller Api(tags …

【论文速读】| 视觉对抗样本:突破对齐的大语言模型

本次分享论文为&#xff1a;Visual Adversarial Examples: Jailbreak Aligned Large Language Models 基本信息 原文作者&#xff1a;Xiangyu Qi, Peter Henderson, Kaixuan Huang, Ashwinee Panda, Mengdi Wang, Prateek Mittal 作者单位&#xff1a;普林斯顿大学、斯坦福大…

使用npm创建一个全局的cli命令,就像vue-cli一样

我们用过vue-cli等工具包&#xff0c;全局安装之后&#xff0c;我们可以直接使用vue create等命令&#xff0c;实际上能够这样使用的原因&#xff0c;就是使用了package.json里面的bin字段注册命令。接下来就以一个脚本文件为例子为大家演示一下bin是如何发挥作用的。 创建项目…

数据库引论:2.SQL简介

SQL(Structured Query Language,结构化查询语言) 2.1 SQL查询语言概览 SQL语言包含 数据定义语言(Data-Definition Language,DDL)。SQL DDL提供定义关系模式、删除关系以及修改关系模式的命令。数据操纵语言(Data-Manipulation Language,DML)。SQL DML提供从数据库中查询信息…

PLC通过智能网关采用HTTP协议JSON文件对接MES等服务系统平台

智能网关IGT-DSER集成了多种PLC的原厂协议&#xff0c;方便实现各种PLC、智能仪表通过HTTP协议与MES等各种系统平台通讯对接。PLC内不用编写程序&#xff0c;通过网关的参数配置软件(下载地址)绑定JSON文件的字段与PLC寄存器地址&#xff0c;配置URL即可。支持POST/GET/PUT等多…

基于YOLOv5s的电动车入梯识别系统(数据集+权重+登录界面+GUI界面+mysql)

本人训练的yolov5s模型&#xff0c;准确率在98.6%左右&#xff0c;可准确完成电梯内检测电动车任务&#xff0c;并搭配了GUI检测界面&#xff0c;支持权重选择、图片检测、视频检测、摄像头检测、识别结果拍照和在线标注数据集等功能。 并且为用户提供了登录注册功能&#xff0…

python版:使用TotalSegmentator工具可在1分钟内自动分割全身117个器官,附批量技巧

TotalSegmentator用于对 CT 图像中超过 117 个类别进行分割的工具。它接受了各种不同 CT 图像&#xff08;不同扫描仪、机构、协议等&#xff09;的训练&#xff0c;因此应该适用于大多数图像。大部分训练数据集可以从Zenodo下载&#xff08;1228 个主题&#xff09;。您还可以…

由浅到深认识Java语言(7):方法(函数)

该文章Github地址&#xff1a;https://github.com/AntonyCheng/java-notes 在此介绍一下作者开源的SpringBoot项目初始化模板&#xff08;Github仓库地址&#xff1a;https://github.com/AntonyCheng/spring-boot-init-template & CSDN文章地址&#xff1a;https://blog.c…

ZYNQ EMIO MIO

1 概述 先来了解GPIO的BANK分布&#xff0c;在UG585文档GPIO一章中可以看到GPIO是有4个BANK&#xff0c; 注意与MIO的BANK区分。 BANK0 控制32个信号&#xff0c;BANK1控制22个信号&#xff0c;总共是MIO的54个引脚&#xff0c;也就是诸如 SPI,I2C,USB,SD 等 PS 端外设接口&am…

【二进制求公约数】【数学】【数论】2543. 判断一个点是否可以到达

本文涉及知识点 二进制求公约数 LeetCode2543. 判断一个点是否可以到达 给你一个无穷大的网格图。一开始你在 (1, 1) &#xff0c;你需要通过有限步移动到达点 (targetX, targetY) 。 每一步 &#xff0c;你可以从点 (x, y) 移动到以下点之一&#xff1a; (x, y - x) (x - y…

基于python+vue灾害应急救援平台flask-django-php-nodejs

灾害应急救援平台的目的是让使用者可以更方便的将人、设备和场景更立体的连接在一起。能让用户以更科幻的方式使用产品&#xff0c;体验高科技时代带给人们的方便&#xff0c;同时也能让用户体会到与以往常规产品不同的体验风格。 与安卓&#xff0c;iOS相比较起来&#xff0c;…

(二)RabbitMQ实战——rabbitmq高可用集群搭建

前言 本节内容是关于rabbitmq高可用集群的部署搭建&#xff0c;使用的是centos7系统&#xff0c;我们准备三台服务器作为rabbitmq的高可用服务器&#xff0c;rabbitmq集群本身不是天然支持高可用的&#xff0c;我们通过配置rabbitmq服务器的镜像队列&#xff0c;以确保消息可以…

突然发现!原来微信批量自动加好友这么简单!

你知道如何更好地管理和利用微信资源&#xff0c;实现客户拓展和沟通吗&#xff1f;下面就教大家一招&#xff0c;帮助大家实现统一管理多个微信号以及批量自动加好友。 想要统一管理多个微信号&#xff0c;不妨试试微信管理系统&#xff0c;不仅可以多个微信号同时登录&#…

无插件网页视频播放器,支持图像绘制(包含方格子、方框等),支持音视频播放、支持录像截图,提供源码下载

前言 本播放器内部采用jessibuca插件接口&#xff0c;支持录像、截图、音视频播放等功能。播放器播放基于ws流&#xff0c;图像绘制操作&#xff1a;1&#xff09;支持绘制方格子&#xff0c;用于监控移动检测画框&#xff1b;2&#xff09;支持绘制不透明方框&#xff0c;用于…

如何进行设备的非对称性能测试

非对称性能测试介绍 RFC2544是RFC组织提出的用于评测网络互联设备&#xff08;防火墙、IDS、Switch等&#xff09;的国际标准。主要是对RFC1242中定义的性能评测参数的具体测试方法、结果的提交形式作了较详细的规定。标准中定义了4个重要的参数&#xff1a;吞吐量&#xff08…

【No.12】蓝桥杯可撤销并查集|查找|合并|撤销(C++)

前置知识 蓝桥杯并查集|路径压缩|合并优化|按秩合并|合根植物(C)-CSDN博客 可撤销并查集 关键注意 可撤销并查集的撤销功能如何实现可撤销并查集能不能用路径压缩 可撤销并查集(Reversible Union-Find)是一种扩展了标准并查集(Union-Find)数据结构的数据结构&#xff0c;它允…