【数据结构】树，二叉树，满二叉树，完全二叉树的定义和二叉树的基本操作

🎊专栏【数据结构】

🍔喜欢的诗句：更喜岷山千里雪 三军过后尽开颜。

🎆音乐分享【勋章】

大一同学小吉，欢迎并且感谢大家指出我的问题🥰

目录

⭐树

🏳️‍🌈定义

 🏳️‍🌈注意

🍔树的基本术语

⭐二叉树

🏳️‍🌈定义

🎆二叉树和树的区别

🏳️‍🌈二叉树的性质

⭐满二叉树

⭐完全二叉树

🎁遍历二叉树

🎈先序遍历二叉树

🎈中序遍历二叉树

🎈后序遍历二叉树

🎁构建二叉树

🎈算法步骤

🎈代码

🎁复制二叉树

🎈算法步骤

🎈代码

🎁计算二叉树的深度

🎈算法步骤

🎈代码

🎁统计二叉树中结点的总数

🎈算法步骤

🎈代码

🎁统计二叉树中叶子结点的个数

🎈算法步骤

🎈代码

🎊完整代码 

 

 

⭐树

🏳️‍🌈定义

树是n（n>=0）个结点的有限集

n=0：称为空树

n>0：称为非空树

✨对于非空树，有下面两个特点

(1)有且只有一个称为根的结点

(2)除根节点之外的其余结点可以分为m(m>0)个互不相交的有限集，对于每一个有限集本身又是一棵树，并且称为根的子树

树可以有多种表示方法，如下图所示 

273e13c161ae4fe5a9e83ca0fad28d64.jpeg

 🏳️‍🌈注意

如下图所示

074fafd523a24ec286e36dcbf9b11d57.png

 

🍔树的基本术语

1a28556e5f6b4b43853b7c144ce6a88a.png

结点：树的一个独立单元（比如上图的ABCD）

结点的度：结点拥有的子树（比如上图中，A的度为3，B的度为2）

树的度：树内各结点度的最大值（比如上图的树的度为3）

叶子（终端结点）：度为0的结点

层次：结点的层次从根开始定义，根为第一层，根的孩子为第二层

树的深度（高度）：树中结点的最大层次

森林：m棵互不相交的树的集合。对于树的每个结点而言，其子树的集合就是森林

⭐二叉树

🏳️‍🌈定义

树是n（n>=0）个结点的有限集

n=0：称为空树

n>0：称为非空树

✨对于非空树，有下面两个特点

(1)有且只有一个称为根的结点

(2)除根节点之外的其余结点可以分为2个互不相交的子集，分别称为T的左子树T1和右子树T2，且T1T2都是二叉树

🎆二叉树和树的区别

🚥二叉树中不存在度>2的结点🚥

二叉树的左右子树有左右之分，不能随意颠倒

二叉树也有多种表示方法，如下图所示

2a5f9e7ecd47467a8540e1a98ffd82e2.jpeg 

🏳️‍🌈二叉树的性质

🎈第i层上至多有2^(i-1)（i>=1）个结点

🎈深度为k的二叉树至多有2^k-1（k>=1）个结点

🎈对于任何一颗二叉树T，如果其终端结点树为n0，度为2的结点树为n2

那么n0=n2+1

⭐满二叉树

013275ec29f34e849d5b7ab47fe242e3.png

深度为k且有2^k-1个结点的二叉树，每一层的结点数都是最大结点数

⭐完全二叉树

9167439e57ea4a28bedb59fbad0442d6.png

 

深度为k，有n个结点的二叉树，当且仅当每一个结点都与深度为k的满二叉树 中编号从1到n的结点一一对应时，为完全二叉树

文末有完整代码

 

🎁遍历二叉树

🎆定义

typedef struct BiNode{				
    char data;
    struct BiNode *lchild,*rchild;
}BiNode,*BiTree;

🎈先序遍历二叉树

操作定义如下：若二叉树为空，则操作为空；否则
(1)访问根结点；
(2)先序遍历左子树；
(3)先序遍历右子树。

void preorder_traversal(BiTree root) {
    if (!root) {
        return;
    }

    cout << root->data << " "; // 访问根节点
    preorder_traversal(root->lchild); // 递归访问左子树
    preorder_traversal(root->rchild); // 递归访问右子树
}


🎈中序遍历二叉树

操作定义如下：若二叉树为空，则操作为空；否则
(1)中序遍历左子树；
(2)访问根结点；
(3)中序遍历右子树。

void inorder_traversal(BiTree root) {
    if (!root) {
        return;
    }

    inorder_traversal(root->lchild); // 递归访问左子树
    cout << root->data << " "; // 访问根节点
    inorder_traversal(root->rchild); // 递归访问右子树
}

🎈后序遍历二叉树

操作定义如下：若二叉树为空，则操作为空；否则
(1)后序遍历左子树；
(2)后序遍历右子树；
(3)访问根结点；

void postorder_traversal(BiTree root) {
    if (!root) {
        return;
    }

    postorder_traversal(root->lchild); // 递归访问左子树
    postorder_traversal(root->rchild); // 递归访问右子树
    cout << root->data << " "; // 访问根节点
}

🎁构建二叉树

法一：

比如根据  ABC##DE#G##F###  这一段来构建

🎈算法步骤

1.读取字符序列，读入字符ch

2.如果ch是“#”，表明该二叉树为空树，即T为NULL，否则执行下面的操作

（1）申请一个内存空间T

（2）将ch赋给T->data

（3）递归创建T的左子树

（4）递归创建T的右子树

🎈代码

void CreateBiTree(BiTree &T){	
	
	char ch;
	cin >> ch;
	if(ch=='#')  T=NULL;			
	else{							
		T=new BiTNode;
		T->data=ch;					//生成根结点
		CreateBiTree(T->lchild);	//递归创建左子树
		CreateBiTree(T->rchild);	//递归创建右子树
	}								
}

法二：

 // 构建二叉树
    BiTree root = new BiNode{'A', nullptr, nullptr};
    root->lchild = new BiNode{'B', nullptr, nullptr};
    root->lchild->lchild = new BiNode{'C', nullptr, nullptr};
    root->lchild->rchild = new BiNode{'D', nullptr, nullptr};
    root->lchild->rchild->lchild = new BiNode{'E', nullptr, nullptr};
    root->lchild->rchild->lchild->rchild = new BiNode{'G', nullptr, nullptr};
    root->lchild->rchild->rchild = new BiNode{'F', nullptr, nullptr};

🎁复制二叉树

🎈算法步骤

1.为空树，递归结束

2.不为空树，那么执行下面的操作

（1）申请一个新结点空间，复制根节点

（2）递归复制左子树

（3）递归复制右子树

🎈代码

void Copy(BiTree T,BiTree &NewT)
{
	if(T==NULL){
		NweT=NULL;
		return;
	}else{
		NewT=new BiTree;		//复制根节点
		NewT->data=T->data;
		Copy(T->lchild,NewT->lchild);
		Copy(T->rchild,NewT->rchild);
	}
}

🎁计算二叉树的深度

🎈算法步骤

1.为空树，递归结束

2.不为空树，那么执行下面的操作

（1）递归计算左子树的深度为m

（2）递归计算右子树的深度为n

（3）如果m>n，那么二叉树深度为m+1，否则为n+1

🎈代码

int Depth(BiTree T)
{ 
	int m,n;
	if(T == NULL ) return 0;        //如果是空树，深度为0，递归结束
	else 
	{							
		m=Depth(T->lchild);			//递归计算左子树的深度记为m
		n=Depth(T->rchild);			//递归计算右子树的深度记为n
		if(m>n) return(m+1);		//二叉树的深度为m 与n的较大者加1
		else return (n+1);
		//+1，所以可以计算出来
	}
}

🎁统计二叉树中结点的总数

🎈算法步骤

如果是空树，那么结点个数为0，递归结束

否则，结点个数=左子树结点个数+右子树结点个数+1

🎈代码

int NodeCount(BiTree T)
{
     if(T==NULL) return 0;  			// 如果是空树，则结点个数为0，递归结束
     else return NodeCount(T->lchild)+ NodeCount(T->rchild) +1;
     //否则结点个数为左子树的结点个数+右子树的结点个数+1
     
     //+1，所以可以计算出来//
}

🎁统计二叉树中叶子结点的个数

🎈算法步骤

如果是空树，那么结点个数为0，递归结束

否则，遍历到NULL，即叶子节点

🎈代码

int LeafCount(BiTree T){
 	if(T==NULL) 	//如果是空树返回0
		return 0;
	if (T->lchild == NULL && T->rchild == NULL)
		return 1; //如果是叶子结点返回1
		
		// 1，所以可以计算出来
		
	else return LeafCount(T->lchild) + LeafCount(T->rchild);
}

🎊完整代码 

#include<iostream>
using namespace std;
typedef struct BiNode{				
	char data;
	struct BiNode *lchild,*rchild;
}BiTNode,*BiTree;


void CreateBiTree(BiTree &T){	
	
	char ch;
	cin >> ch;
	if(ch=='#')  T=NULL;			
	else{							
		T=new BiTNode;
		T->data=ch;					//生成根结点
		CreateBiTree(T->lchild);	//递归创建左子树
		CreateBiTree(T->rchild);	//递归创建右子树
	}								
}									


void PreOrderTraverse(BiTree T)
{  
   if (T) {
      cout<<T->data;            // 访问结点
      PreOrderTraverse(T->lchild); // 遍历左子树
      PreOrderTraverse(T->rchild);// 遍历右子树  
   }
}



void InOrderTraverse(BiTree T){  
	
	if(T){
		InOrderTraverse(T->lchild);
		cout << T->data;
		InOrderTraverse(T->rchild);
	}
}


void PostOrderTraverse(BiTree T)
{ 
   if (T) {
      PostOrderTraverse(T->lchild); // 遍历左子树
      PostOrderTraverse(T->rchild);// 遍历右子树
      cout << T->data;           // 访问结点
    }
}



int NodeCount(BiTree T)
{
     if(T==NULL) return 0;  			// 如果是空树，则结点个数为0，递归结束
     else return NodeCount(T->lchild)+ NodeCount(T->rchild) +1;
     //否则结点个数为左子树的结点个数+右子树的结点个数+1
     
     //+1，所以可以计算出来//
} 


//计算二叉树中叶子结点的个数
int LeafCount(BiTree T){
 	if(T==NULL) 	//如果是空树返回0
		return 0;
	if (T->lchild == NULL && T->rchild == NULL)
		return 1; //如果是叶子结点返回1
		
		// 1，所以可以计算出来
		
	else return LeafCount(T->lchild) + LeafCount(T->rchild);
}


//计算二叉树的深度	
int Depth(BiTree T)
{ 
	int m,n;
	if(T == NULL ) return 0;        //如果是空树，深度为0，递归结束
	else 
	{							
		m=Depth(T->lchild);			//递归计算左子树的深度记为m
		n=Depth(T->rchild);			//递归计算右子树的深度记为n
		if(m>n) return(m+1);		//二叉树的深度为m 与n的较大者加1
		else return (n+1);
		//+1，所以可以计算出来
	}
}

int main(){
	BiTree tree;
	int nodecount=0,leafcount=0,depth=0;
	cout<<"请输入建立二叉链表的序列：\n";
	CreateBiTree(tree);
	cout<<endl;
	cout<<"先序遍历的结果为：\n";
	PreOrderTraverse(tree);
	cout<<endl;
	cout<<"中序遍历的结果为：\n";
	InOrderTraverse(tree);
	cout<<endl;
	cout<<"后序遍历的结果为：\n";
	PostOrderTraverse(tree);
	cout<<endl;
	cout<<"该二叉树中结点总数为：";
	cout<<NodeCount(tree)<<endl;
	cout<<"该二叉树中叶子结点总数为：";
	cout<<LeafCount(tree)<<endl;
	cout<<"该二叉树的深度为：";
	cout<<Depth(tree)<<endl;
	return 0;
}

🥰如果大家有不明白的地方，或者文章有问题，欢迎大家在评论区讨论，指正🥰 

 

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

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

相关文章

【Maven篇】解锁 Maven 的智慧：依赖冲突纷争下的版本调停者

【Maven篇】解锁 Maven 的智慧：依赖冲突纷争下的版本调停者

缘起 软件开发世界是一个充满无限可能的领域&#xff0c;但同时也伴随着诸多挑战。其中之一&#xff0c;就是依赖冲突的问题。在这篇文章中&#xff0c;我们将揭开 Maven 这位“版本调停者”的神秘面纱&#xff0c;深入探讨如何在版本纠纷的盛宴中解决依赖问题。 Maven&#…
阅读更多...
如何选择合适的数据可视化工具？

如何选择合适的数据可视化工具？

如果是入门级的数据可视化工具&#xff0c;使用Excel插件就足够了&#xff01; Excel插件&#xff0c;tusimpleBI 是一款 Excel 图表插件&#xff0c;提供超过120项图表功能&#xff0c;帮助用户制作各种 Excel 所没有的高级图表&#xff0c;轻轻松松一键出图。 它能够制作10…
阅读更多...
FPGA——DDR3的IP核

FPGA——DDR3的IP核

FPGA——DDR3的ip核 IP核配置基于MIG核代码基于AXI接口的DDR3 IP核配置 1 2 3 4 5 6 基于MIG核代码 控制MIG核的信号进行读写 module MIG_APP_Drive(input i_ui_clk ,input i_ui_rst ,input init_calib_…
阅读更多...
Django templates 存放html目录

Django templates 存放html目录

模板 一概述 模板由两部分组成&#xff0c;一部分是HTML代码&#xff0c;一部分是逻辑控制代码&#xff08;变量&#xff0c;标签&#xff0c;过滤器&#xff09; 作用&#xff1a;可以通过一些逻辑控制代码减少一些重复的操作更快速的生成HTML代码&#xff0c;并且实现简单的…
阅读更多...
VSCode下使用github初步

VSCode下使用github初步

由于各种需要&#xff0c;现在需要统一将一些代码提交搞github&#xff0c;于是有了在VSCode下使用github的需求。之前只是简单的使用git clone&#xff0c;代码提交这些用的是其他源代码工具&#xff0c;于是得学习实操下&#xff0c;并做一记录以备后用。 安装 VSCode安装 …
阅读更多...
K8S POD 启动探针 startupProbe 的使用

K8S POD 启动探针 startupProbe 的使用

当我们启动一个POD 时&#xff0c; 当k8s detect 里面的容器启动成功时&#xff0c; 就会认为这个POD 启动完成了&#xff0c; 通常就会在状态里表示 ready 1/1 … 例如 rootk8s-master:~# kubectl get pods NAME READY STATUS RESTARTS AGE bq-api-demo 1…
阅读更多...
部署Zabbix Agents添加使能监测服务器_Windows平台_MSI/Archive模式

部署Zabbix Agents添加使能监测服务器_Windows平台_MSI/Archive模式

Windows平台 一、从MSI安装Windows代理，添加Windows Servers/PC 概述 可以从Windows MSI安装包（32位或64位） 安装Zabbix agent 32位包不能安装在64位Windows中 所有软件包都支持TLS，配置TLS可选 支持UI和命令行的安装。 1、下载Agent代理程序，使用Agent2升级版，官网链接如…
阅读更多...
首次突破1000量子比特！德国TU Darmstadt发布全新量子处理架构

首次突破1000量子比特！德国TU Darmstadt发布全新量子处理架构

内容来源&#xff1a;量子前哨&#xff08;ID&#xff1a;Qforepost&#xff09; 编辑丨慕一 编译/排版丨沛贤 深度好文&#xff1a;1200字丨8分钟阅读 量子计算机能否进一步发展&#xff0c;关键在于量子系统如何更具有可扩展性。随着量子系统规模的扩大&#xff0c;其算力优…
阅读更多...
【接口防重复提交】⭐️基于RedisLockRegistry 分布式锁管理器实现

【接口防重复提交】⭐️基于RedisLockRegistry 分布式锁管理器实现

目录 前言 思路 实现方式 实践 1.引入相关依赖 2.aop注解 3.切面类代码 4.由于启动时报错找不到对应的RedisLockRegistry bean&#xff0c;选择通过配置类手动注入&#xff0c;配置类代码如下 测试 章末 前言 项目中有个用户根据二维码绑定身份的接口&#xff0c;由于用户在…
阅读更多...
Python aiohttp 使用指南：快速入门教程

Python aiohttp 使用指南：快速入门教程

aiohttp 就是 Python 中一款优秀的异步 Web 框架&#xff0c;它能够帮助我们构建高效的异步 Web 应用和异步 HTTP 客户端。在本文中&#xff0c;我们将深入探讨 aiohttp 是什么以及如何使用它&#xff0c;通过简单易懂的案例带领你理解异步编程&#xff0c;以及如何处理异步请求…
阅读更多...
基于C语言的“贪吃蛇”游戏设计理念

基于C语言的“贪吃蛇”游戏设计理念

3.功能描述&#xff1a;本游戏主要实现以下几种功能 图1.游戏功能模块 3.1. 贪吃蛇的控制功能&#xff1a;通过各种条件的判断&#xff0c;实现对游戏蛇的左移、右移、下移、上移、自由移动&#xff0c;贪吃蛇的加长功能。 3.2. 游戏显示更新功能&#xff1a;当贪吃蛇左右移动、…
阅读更多...
信息系统项目管理师018：计算机网络（2信息技术发展—2.1信息技术及其发展—2.1.2计算机网络）

信息系统项目管理师018：计算机网络（2信息技术发展—2.1信息技术及其发展—2.1.2计算机网络）

文章目录 2.1.2 计算机网络1.网络标准协议2.软件定义网络3.第五代移动通信技术 记忆要点总结 2.1.2 计算机网络 在计算机领域中&#xff0c;网络就是用物理链路将各个孤立的工作站或主机相连在一起&#xff0c;组成数据链路&#xff0c;从而达到资源共享和通信的目的。凡将地理…
阅读更多...
DEYOv2: Rank Feature with Greedy Matchingfor End-to-End Object Detection

DEYOv2: Rank Feature with Greedy Matchingfor End-to-End Object Detection

摘要 与前代类似&#xff0c; DEYOv2 采用渐进式推理方法 来加速模型训练并提高性能。该研究深入探讨了一对一匹配在优化器中的局限性&#xff0c;并提出了有效解决该问题的解决方案&#xff0c;如Rank 特征和贪婪匹配 。这种方法使DEYOv2的第三阶段能够最大限度地从第一和第二…
阅读更多...
Day68：WEB攻防-Java安全原生反序列化SpringBoot攻防heapdump提取CVE

Day68：WEB攻防-Java安全原生反序列化SpringBoot攻防heapdump提取CVE

目录 Java安全-反序列化-原生序列化类函数 原生序列化类函数 SnakeYaml XMLDecoder ObjectInputStream.readObject 工具利用 ysoserial Yakit SerializedPayloadGenerator Java安全-SpringBoot框架-泄漏&CVE SpringBoot Actuator-黑白盒发现 人工识别 BurpSui…
阅读更多...
华为配置WAPI-PSK安全策略实验

华为配置WAPI-PSK安全策略实验

配置WAPI-PSK安全策略示例 组网图形 图1 配置WAPI-PSK安全策略组网图 配置流程组网需求配置思路配置注意事项操作步骤配置文件 配置流程 WLAN不同的特性和功能需要在不同类型的模板下进行配置和维护&#xff0c;这些模板统称为WLAN模板&#xff0c;如域管理模板、射频模板、VAP…
阅读更多...
MATLAB的使用（二)

MATLAB的使用（二)

一&#xff0c;算法需求 算法五特性(1)有穷性。有穷性是指算法需在有穷步骤、有穷时间内结束。 (2)确定性。确定性是指每个步骤都有确切的意义&#xff0c;相同的输入有相同的输出。 (3)有效性。有效性是指可通过已实现的运算在有限次完成&#xff0c;或叫可行性。 (4)输入。…
阅读更多...
信息学奥赛一本通之MAC端VSCode C++环境配置

信息学奥赛一本通之MAC端VSCode C++环境配置

前提 安装 Visual Studio CodeVSCode 中安装 C/C扩展确保 Clang 已经安装&#xff08;在终端中输入命令&#xff1a;clang --version 来确认是否安装&#xff09;未安装&#xff0c;在命令行执行xcode-select --install 命令&#xff0c;会自行安装&#xff0c;安装文件有点大…
阅读更多...
超越传统的极限：解密B树与B+树的数据结构之美！

超越传统的极限：解密B树与B+树的数据结构之美！

超越传统的极限&#xff1a;解密B树与B树的数据结构之美&#xff01; B树和B树是在计算机科学中常用的平衡查找树数据结构&#xff0c;它们在处理大规模数据和磁盘存储方面具有重要的优势。本文将深入介绍B树和B树的基本概念、特点以及它们在数据库和文件系统中的应用&#xff…
阅读更多...
AR/MR产品设计（二）：如何用一双手完成与虚拟对象的自然交互

AR/MR产品设计（二）：如何用一双手完成与虚拟对象的自然交互

AR/MR产品设计&#xff08;二&#xff09;&#xff1a;如何用一双手完成与虚拟对象的自然交互 - 知乎 手是我们与现实世界交互最重要的方式&#xff0c;同样在虚实混合的世界中是最重要的交互方式 在AR/MR/VR的交互中&#xff0c;手势交互会作为XR的重要交互动作&#xff0c;因…
阅读更多...
强缓存和协商缓存

强缓存和协商缓存

前言 计算机网络模型从底到上&#xff1a;物理层&#xff08;光纤、网线&#xff09;、链路层&#xff08;MAC地址&#xff09;、网络层&#xff08;IP协议&#xff09;、传输层&#xff08;TCP\UDP&#xff09;、应用层&#xff08;HTTP\FTP\DNS&#xff09;。HTTP协议是作用…
阅读更多...
最新文章

Copyright @ 2022~2023