二叉树的创建、销毁及其功能、结构

目录

一、如何理解二叉树的结构

二、构建二叉树需要的基础代码

三、代码

二叉树的遍历：前序 中序 后序

二叉树结点个数

求叶子节点的个数

求二叉树的高度:左右子树高度的最大值

 二叉树第k层(LevelK)结点个数  

查找元素，返回节点指针

二叉树的层序遍历：队列实现（非递归）

二叉树的销毁：最好用后序

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

一、如何理解二叉树的结构

对于二叉树的结构，是递归的最典型的例子。其递归过程，就是二叉树的树枝层层展开的过程。

每棵树，都可以看成根节点 和 左右子树的结合体。

对于根节点的左右子树而言，当左右子树为空树时，也就代表着 某条支路的递归完成，此时往往需要依次return。

若返回类型是不void类型，还需要额外的一次return，返回到上一次调用此函数处，作为返回值。

递归：子问题 + 终结调节

二、构建二叉树需要的基础代码

1.自由构建


typedef int BTDateType;			//int 在前

typedef struct BinaryTreeNode
{
	BTDateType date;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right; 

}BTNode;



BTNode* BuyNode(int x)			//获得树的节点:链表型
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));

	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}

							//如果前边已经有一次返回，则可保证此处代码一定不符合前面的 if 返回条件

		//找到堆上的空间，并进行修改，因此后续的函数在使用时，才能保证date、left、right是处理好的结果

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

	return newnode;

}

//建好树，返回树根


BTNode* CreatBinaryTree()			//已经有buy-node函数
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);
	BTNode* node7 = BuyNode(7);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	node5->left = node7;

	return node1;

}

需要构建树节点 、 定义date的数据类型、获得新节点的方法、根据自己的思路，自由构建一棵树。

三、代码

二叉树的遍历：前序 中序 后序


void PrevOrder(BTNode* root)
{
		//二叉树不能轻易assert空

	if (root == NULL)		//结束条件
	{
		printf("N ");
		return;
	}

	//此处root一定不为空


	printf("%d ", root->date);
	
	PrevOrder(root->left);		//子问题		。 在物理上，就是函数栈帧不断创建和销毁，销毁之后，上一层函数，继续往下执行！	
	PrevOrder(root->right);

				//不能写换行，否则每次递归都会打印换行
}
void InOrder(BTNode* root)
{
		//二叉树不能轻易assert空

	if (root == NULL)		//结束条件
	{
		printf("N ");
		return;
	}

	//此处root一定不为空


	
	InOrder(root->left);		//子问题
	printf("%d ", root->date);
	InOrder(root->right);

}


void PostOrder(BTNode* root)
{
		//二叉树不能轻易assert空

	if (root == NULL)		//结束条件
	{	
		printf("N ");
		return;			//表示本层函数栈帧销毁了
	}

	//此处root一定不为空


	
	PostOrder(root->left);		//子问题
	PostOrder(root->right);
	printf("%d ", root->date);



}


二叉树结点个数


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

	int leftsize = BTreeSize(root->left);
	int rightsize = BTreeSize(root->right);

	return leftsize + rightsize + 1;

}

需要注意的是

int leftsize = BTreeSize(root->left);
int rightsize = BTreeSize(root->right);

这就是不断调用递归的过程

并且返回类型是int类型，需要额外的一次返回

    return leftsize + rightsize + 1;

求叶子节点的个数


int BTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
			//此处root一定不为空
	if (root->left == NULL && root->right == NULL)			//不能写连等！
	{
		return 1;
	}

	return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);		//会在此处不断返回本层的结果，返回到上一层的栈帧里的函数调用处。

}

    if (root->left == NULL && root->right == NULL)            //不能写连等！
    {
        return 1;
    }

需要注意的是，递归的不断调用过程中，就是二叉树不断分叉的过程

    return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);

此段代码，可以不断使函数返回上一层

求二叉树的高度:左右子树高度的最大值


int BTreeHeight(BTNode* root)
{

	if (root == NULL)
	{
		return 0;
	}

	int left_height = BTreeHeight(root->left) + 1;		//得 + 1，根节点也是高度
	int right_height = BTreeHeight(root->right) + 1;

	return left_height > right_height ? left_height : right_height;

}

int left_height = BTreeHeight(root->left) + 1;        //得 + 1，根节点也是高度
int right_height = BTreeHeight(root->right) + 1;

应该记录返回值，防止多次递归调用。

 二叉树第k层(LevelK)结点个数  

//子问题：转化成左子树的第 K - 1层 和 右子树的第 K - 1层
//结束条件（所有的返回条件）： K == 1    且节点不为空  或者节点为空


int BTreeLevelKSize(BTNode* root, int k)
{

	assert(k != 0);

	//if (!root)		//不能这么写，  ！ 操作符 是逻辑操作符，只能对bool类型进行操作

	if (root == NULL)
		return 0;

	if (k == 1)
		return 1;

	int left_k_size = BTreeLevelKSize(root->left, k - 1);		//不断递归调用就是不断分叉，最后直到 子树变成空
	int right_k_size = BTreeLevelKSize(root->right, k - 1);

	return left_k_size + right_k_size;

}

查找元素，返回节点指针

        //查找：本质是遍历        选前序查找！！！

//查找：左树找到，就返回左树，不用去查找右树


BTNode* BTreeFind(BTNode* root, BTDateType x)
{
	if (root == NULL)		//走到尾
		return NULL;

	if (root->date == x)
		return root;

				//root一定不为空

	BTNode* left = BTreeFind(root->left, x);

	if (left)		//如果左树不为空（为root）		//左边找到就直接返回left，之前每一层就都不去右边找了，效率更高！
		return left;

	BTNode* right = BTreeFind(root->right, x);

	if (right)
		return right;



			//到此处之后，一定两者都为空！即没找到。

	return NULL;		
}

左树找到之后，直接返回左树的指针，不去右树查找

二叉树的层序遍历：队列实现（非递归）

首先应该实现一个队列。

对于队列的DateType类型，应该是tree节点的指针，而不是节点的date。（以便找到left和right树）


void LevelOrder(BTNode* root)
{
	Q q;
	QueueInit(&q);

	if (root)	
		QueuePush(&q, root);			//往队列插入根节点的指针	，队列存储的date是指针！！！

	while (!QueueEmpty(&q)) 	//队列不为空
	{

		//出数据

		BTNode* front = QueueFront(&q);			//front是数据，first是节点

		QueuePop(&q);	//只是pop掉了队列的一个指针变量，front指针仍然可以找到root节点

		printf("%d ", front->date);

		//出完一个数据之后，将左右孩子push到队列中。

		if (front->left)		
			QueuePush(&q, front->left);		//Push时，push的是指针类型！！！ （以便父找子）

		if (front->right)
			QueuePush(&q, front->right);

	}

	putchar(10);

	QueueDestroy(&q);

}

思想：

利用队列的先进先出 

二叉树的父节点出队列pop时，将父节点的孩子节点带入push队列。先pop父节点，再push子树。

        if (front->left)        
            QueuePush(&q, front->left);        //Push时，push的是指针类型！！！ （以便父找子）

        if (front->right)
            QueuePush(&q, front->right);

当将二叉树的所有有效数据都push到队列之后，此时不push空指针，只进行pop操作。

二叉树的销毁：最好用后序


void BTreeDestroy(BTNode* root)
{

	if (root == NULL)
		return;

	//后续遍历

	BTreeDestroy(root->left);		//递归过程	在销毁左子树时，就会在递归中不断用到free过程
	BTreeDestroy(root->right);

	free(root->right);				//销毁过程	无需置空
}

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

利用队列先进先出 及 完全二叉树数据连续（数据连续）的性质

步骤：

1.导入所有节点指针，不断出数据

2.数据出到空时，停止出数据。

3.再次出数据，当遇到非空指针时，则为false；若出完没有遇到，则为true。

4.return之前，应该先destroy。


bool BinaryTreeComplete(BTNode* root)
{
	Q q;
	QueueInit(&q);
	
	if (root != NULL)
		QueuePush(&q, root);	//存储的是节点的指针

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);		//出数据  如果是完全二叉树，则可以出掉所有数据。
		QueuePop(&q);

		if (front)
		{
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}

		else	//front为空时，此时队列（若为完全二叉树）一定只剩下NULL
			break;

	}


	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);		//继续出数据
		QueuePop(&q);

		if (front != NULL)
		{
			QueueDestroy(&q);
			return false;	//返回之前先销毁
		}

	}

	QueueDestroy(&q);
	return true;	



	QueueDestroy(&q);
}

需要注意的是，当第 i 层pop掉之后，队列中的元素是 第 i + 1 层的数据。

如果是完全二叉树，当第一次循环停止时，此时一定只剩下NULL

第一层循环：

首先将树的节点，导入到队列中

在导入数据时，不同于层序遍历 

层序遍历不会导入空节点

if (front->left)        
            QueuePush(&q, front->left);        //Push时，push的是指针类型！！！ （以便父找子）

        if (front->right)
            QueuePush(&q, front->right);

但是判断是否是完全二叉树时，应该导入空节点

    if (front)
        {
            QueuePush(&q, front->left);
            QueuePush(&q, front->right);
        }


        else    //所有数据全部弹出
            break;

当所有非空数据pop掉之后，循环结束

第二层循环：

不断pop空指针，当出现非空指针时，销毁、return false。

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

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

相关文章

Golang入门基础

Golang入门基础

文章目录 Golang的背景知识Golang的发展历程Golang的特点Golang的应用领域 开发环境搭建下载并安装SDK包设置环境变量Go项目目录结构 注释变量标识符命名输入和输出运算符算术运算符关系运算符逻辑运算符赋值运算符位运算符其他运算符 Golang的背景知识 Golang的发展历程 Gola…
阅读更多...
高仿小米商城用户端

高仿小米商城用户端

高仿小米商城用户端(分为商城前端（tongyimall-vue)和商城后端(tongyimall-api)两部分)，是Vue SpringBoot的前后端分离项目，用户端包括首页门户、商品分类、首页轮播、商品展示、商品推荐、购物车、地址管理、下订单、扫码支付等功能模块。 …
阅读更多...
Docker Volume (存储卷)

Docker Volume (存储卷)

什么是存储卷? 存储卷就是将宿主机的本地文件系统中存在的某个目录直接与容器内部的文件系统上的某一目录建立绑定关系。这就意味着，当我们在容器中的这个目录下写入数据时，容器会将其内容直接写入到宿主机上与此容器建立了绑定关系的目录。在宿主机上…
阅读更多...
「51媒体」权重高新闻源央级媒体邀约资料有哪些？

「51媒体」权重高新闻源央级媒体邀约资料有哪些？

传媒如春雨，润物细无声，大家好，我是51媒体网胡老师。 权重高的央级媒体邀约资源包括了中国一些最具影响力和权威性的新闻机构。具体如下： 人民日报：作为中国共产党中央委员会的机关报，人民日报具有极高的权…
阅读更多...
openEuler-23.03下载

openEuler-23.03下载

下载地址：openEuler下载 | 欧拉系统ISO镜像 | openEuler社区官网 下载版本：openEuler-23.03-x86_64-dvd.iso
阅读更多...
生产者，消费者，队列缓冲区，线程

生产者，消费者，队列缓冲区，线程

public class CustomQueue {private BlockingQueue<Integer> queue;public CustomQueue() {// 初始化一个容量为1的阻塞队列queue new LinkedBlockingQueue<>(1);}public void put(int num) throws InterruptedException {// 将数字放入队列queue.put(num);}publi…
阅读更多...
给一个新项目配置conda环境的完整流程

给一个新项目配置conda环境的完整流程

创建环境&#xff0c;并指定python的版本&#xff0c;我这边指定为3.7&#xff1a; conda create --name [自定义的环境名] python3.7我这边假定我的环境名为grand&#xff1a; conda create --name grand python3.7创建成功后&#xff0c;初始化一下conda&#xff1a; source …
阅读更多...
Google DeepMind: Many-Shot vs. Few-Shot

Google DeepMind: Many-Shot vs. Few-Shot

本文介绍了如何通过增大上下文窗口&#xff0c;利用大型语言模型&#xff08;LLMs&#xff09;进行多实例上下文学习&#xff08;Many-Shot In-Context Learning&#xff0c;ICL&#xff09;的方法。主要描述了现有的几实例上下文学习方法虽然在推理时能够通过少量例子学习&…
阅读更多...
基于Java+SpringBoot+vue动物救助平台设计和实现

基于Java+SpringBoot+vue动物救助平台设计和实现

基于JavaSpringBootvue动物救助平台设计和实现 &#x1f345; 作者主页 央顺技术团队 &#x1f345; 欢迎点赞 &#x1f44d; 收藏 ⭐留言 &#x1f4dd; &#x1f345; 文末获取源码联系方式 &#x1f4dd; &#x1f345; 查看下方微信号获取联系方式 承接各种定制系统 &#…
阅读更多...
树莓派使用总结

树莓派使用总结

手上拿到了一块Raspberry Pi 4B板子。研究一下怎么用。 安装系统 直接到官网【Raspberry Pi 】下载在线安装助手 安装好后&#xff0c;打开软件&#xff0c;选择好板子型号、系统、TF卡&#xff0c;一路下一步就行。 树莓派接口 直接查看官方的资料【Raspberry Pi hardwar…
阅读更多...
基础算法之二分算法

基础算法之二分算法

前言 本次博客&#xff0c;将要介绍二分算法的基本原理以及如何使用&#xff0c;深入浅出 二分可以针对整型以及浮点型接下来对其讲解希望对小白有所帮助吧 整型的二分法 一般要在一个数组中猜出一个数是否存在我们可以遍历一遍整个数组&#xff0c;判断是否存在&#xff0…
阅读更多...
Java面向对象编程

Java面向对象编程

标题&#xff1a;Java面向对象编程 文章目录 标题&#xff1a;Java面向对象编程前言&#xff1a;面向对象的三条主线一、面向对象编程概述1.1 程序设计思路1.2 Java语言的基本元素&#xff1a;类和对象1.3 对象的内存解析 二、类的成员1—成员变量2.1 “变量”定义&分类2.2…
阅读更多...
蓝桥杯备赛

蓝桥杯备赛

关闭同步流&#xff1a; ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); 注意数据范围&#xff1a;数据范围较大时干脆所有变量类型都定义成longlong等。 stl&#xff1a; sort函数 时间复杂度为nlog(n); sort(数组指针&#xff0c;从指针开始多少个数&#xff0c;great…
阅读更多...
如何辨别：DNS污染or DNS劫持？

如何辨别：DNS污染or DNS劫持？

DNS劫持和DNS污染的情况在互联网中并不少见&#xff0c;到底是出现了DNS污染还是DNS劫持。什么是DNS污染&#xff1f;什么是DNS劫持&#xff1f;我们该如何辨别DNS污染和DNS劫持&#xff1f; DNS劫持&#xff1a; DNS 劫持是指恶意攻击者通过非法手段篡改了网络中的 DNS 服务…
阅读更多...
HTML快速入门

HTML快速入门

HTML简介 HTML&#xff08;超文本标记语言&#xff09;是一种用于创建网页和Web应用程序的标记语言。它由一系列标签组成&#xff0c;每个标签通过尖括号来定义&#xff0c;并用于标记文本、图像、链接和其他内容。HTML标签描述了网页中的信息结构和布局&#xff0c;并定义了文…
阅读更多...
[MySQL数据库] 索引与事务

[MySQL数据库] 索引与事务

1. 索引 1.1 概念 索引是一种特殊的文件&#xff0c;包含着对数据表里所有记录的引用指针.可以对表中的一列或多列创建索引,并指定索引的类型&#xff0c;各类索引有各自的数据结构实现. 1.2 作用 数据库中的表、数据、索引之间的关系&#xff0c;类似于书架上的图书、书籍…
阅读更多...
【Redis】面试题汇总

【Redis】面试题汇总

Redis什么是Redis、使用场景有哪些Redis 为什么这么快&#xff1f;Redis 数据类型及使用场景五种常见的 Redis 数据类型是怎么实现&#xff1f;Redis是单线程吗Redis 采用单线程为什么还这么快&#xff1f;Redis 如何实现数据不丢失&#xff1f;Redis 如何实现服务高可用&#…
阅读更多...
【复习笔记】FreeRTOS(六) 队列操作

【复习笔记】FreeRTOS(六) 队列操作

本文是FreeRTOS复习笔记的第六节&#xff0c;队列操作。 上一篇文章&#xff1a; 【复习笔记】FreeRTOS(五)时间片调度 文章目录 1.队列操作1.1.队列操作过程1.2.队列操作常用的API函数 二、实验设计三、测试例程四、实验效果 1.队列操作 队列是为了任务与任务、任务与中断之间…
阅读更多...
极狐GitLab x LigaAI，AI 时代研发提效新范式

极狐GitLab x LigaAI，AI 时代研发提效新范式

GitLab 是一个全球知名的一体化 DevOps 平台&#xff0c;很多人都通过私有化部署 GitLab 来进行源代码托管。极狐GitLab 是 GitLab 在中国的发行版&#xff0c;专门为中国程序员服务。可以一键式部署极狐GitLab。 近日&#xff0c;极狐GitLab 和 LigaAI 宣布合作&#xff0c;双…
阅读更多...
分布式锁设计

分布式锁设计

一、为什么需要分布式锁 1.1 单体项目同步实现 在单进程&#xff08;启动一个jvm&#xff09;的系统中&#xff0c;当存在多个线程可以同时改变某个变量&#xff08;可变共享变量&#xff09;时&#xff0c;就需要对变量或代码块做同步&#xff0c;使其在修改这种变量时能够线…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站