数据结构-二叉树

数据结构-二叉树

    • 二叉树的概念
    • 二叉树的遍历分类
  • 建立二叉树，并遍历
    • 二叉树的最小单元
    • 二叉树的最小单元初始化
    • 初始化二叉树
    • 前序遍历的实现
    • 中序遍历的实现
    • 后序遍历的实现
    • 计算节点的个数
    • 计算树的深度
    • 求第k层的个数
    • 查找二叉树的元素
    • 分层遍历
  • 全部代码如下

二叉树的概念

在这里插入图片描述

二叉树的遍历分类

有前序遍历，中序遍历，后序遍历和层序遍历
在这里插入图片描述

规则：

1.遇到根可以直接访问根
2.遇到左子树，右子树，不可以直接访问，要将其看作一颗新的二叉树，按遍历规则，再次循环，直至左子树或右子树为空，则可访问空。

前序遍历
在这里插入图片描述
中序遍历和后序遍历
中序遍历：
三者访问根的时机不同

层序遍历：一层一层的进行

1 2 4 3 5 6

建立二叉树，并遍历

二叉树的最小单元

根，左子树和右子树

typedef int BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

二叉树的最小单元初始化

BTNode* BuyNode(BTDataType x)
{
	BTNode* node=(BTNode*)malloc(sizeof(BTNode));
	if (node==NULL)
	{
		perror("malloc fail");
		return NULL;
	}

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

	return node;
}

初始化二叉树

BTNode* CreatTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);

	node1->left = node2;
	node1->right = node4;

	node2->left = node3;

	node4->left = node5;
	node4->right=node6;

	return node1;
}

前序遍历的实现

函数的回归条件为root为空，或者函数正常结束
按照顺序依次为：根，左子树，右子树

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

递归调用展开图
在这里插入图片描述

结果如下：
在这里插入图片描述

中序遍历的实现

函数的回归条件为root为空，或者函数正常结束
按照顺序依次为：左子树，根，右子树

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

后序遍历的实现

函数的回归条件为root为空，或者函数正常结束
按照顺序依次为：左子树，右子树，根

void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

计算节点的个数

利用分治法求节点的个数，只有节点存在时，才会+1，并返回下层的统计个数
在这里插入图片描述

int TreeSize(BTNode* root)
{
	if (root==NULL)
	{
		return 0;
	}
	else
	{
		return TreeSize(root->left) 
			+ TreeSize(root->right)
			+1;
	}
}

执行结果如下：
在这里插入图片描述

计算树的深度

在这里插入图片描述

int TreeHeight(BTNode* root)
{
	if (root==NULL)
	{
		return 0;
	}
	int leftHeight = TreeHeight(root->left);
	int rightHeight = TreeHeight(root->right);
	return leftHeight > rightHeight ?
		leftHeight + 1 :
		rightHeight + 1;
}

代码执行结果如下：
在这里插入图片描述

求第k层的个数

在这里插入图片描述

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

	if (k==1)
	{
		return 1;
	}

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

运行结果如下:
在这里插入图片描述

查找二叉树的元素

在这里插入图片描述

BTNode* TreeFind(BTNode* root, BTDataType x)
{
	if (root==NULL)
	{
		return NULL;
	}
	if (root->data==x)
	{
		return root;
	}
	BTNode* lret = TreeFind(root->left, x);
	if (lret)
	{
		return lret;
	}
	BTNode* rret = TreeFind(root->right, x);
	if (rret)
	{
		return rret;
	}
	return NULL;
}

结果如下：
在这里插入图片描述

分层遍历

利用队列，先将根push，进入循环，可pop，再将层子节点push，依次循环。安照队列先进先出的原则，可实现分层打印

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

	if (root)
	{
		QueuePush(&q,root);
	}

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%d ",front->data);

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

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

	QueueDestroy(&q);
}

结果如下：

在这里插入图片描述
判断是否为完全二叉树

bool TreeComplete(BTNode* root)
{
	Quene q;
	QueueInit(&q);

	if (root)
	{
		QueuePush(&q, root);
	}

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (front==NULL)
		{
			break;
		}
		else
		{
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
	}

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (front)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}

全部代码如下

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include "Queue.h"

typedef int BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

BTNode* BuyNode(BTDataType x)
{
	BTNode* node=(BTNode*)malloc(sizeof(BTNode));
	if (node==NULL)
	{
		perror("malloc fail");
		return NULL;
	}

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

	return node;
}

BTNode* CreatTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	//BTNode* node6 = BuyNode(6);

	//node1->left = node2;
	//node1->right = node4;

	//node2->left = node3;

	//node4->left = node5;
	//node4->right=node6;


	node1->left = node2;
	node1->right = node3;

	node2->left = node4;

	//node4->left = node5;
	node3->right = node5;

	return node1;
}

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

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

//分治法求节点的个数
int TreeSize(BTNode* root)
{
	if (root==NULL)
	{
		return 0;
	}
	else
	{
		return TreeSize(root->left) 
			+ TreeSize(root->right)
			+1;
	}
}

int TreeHeight(BTNode* root)
{
	if (root==NULL)
	{
		return 0;
	}
	int leftHeight = TreeHeight(root->left);
	int rightHeight = TreeHeight(root->right);
	return leftHeight > rightHeight ?
		leftHeight + 1 :
		rightHeight + 1;
}

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

	if (k==1)
	{
		return 1;
	}

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

//查找元素
BTNode* TreeFind(BTNode* root, BTDataType x)
{
	if (root==NULL)
	{
		return NULL;
	}
	if (root->data==x)
	{
		return root;
	}
	BTNode* lret = TreeFind(root->left, x);
	if (lret)
	{
		return lret;
	}
	BTNode* rret = TreeFind(root->right, x);
	if (rret)
	{
		return rret;
	}
	return NULL;
}

//分层遍历
void LevelOrder(BTNode* root)
{
	Quene q;
	QueueInit(&q);

	if (root)
	{
		QueuePush(&q,root);
	}

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%d ",front->data);

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

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

	QueueDestroy(&q);
}

//判断是不是完全二叉树
bool TreeComplete(BTNode* root)
{
	Quene q;
	QueueInit(&q);

	if (root)
	{
		QueuePush(&q, root);
	}

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (front==NULL)
		{
			break;
		}
		else
		{
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
	}

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (front)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}
int main()
{
	BTNode* root = CreatTree();
	PreOrder(root);
	printf("\n");

	InOrder(root);
	printf("\n");

	PostOrder(root);
	printf("\n");

	printf("%d",TreeSize(root));
	printf("\n");

	printf("%d ", TreeHeight(root));
	printf("\n");

	printf("%d ", TreeLevel(root,3));
	printf("\n");

	printf("%p ", TreeFind(root, 5));
	printf("\n");

	printf("%p ", TreeFind(root, 60));
	printf("\n");

	LevelOrder(root);

	printf("TreeComplete: %d", TreeComplete(root));
	//二维数组

	return 0;
}

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"

void QueueInit(Quene* pq)
{
	assert(pq);

	pq->head = pq->tail = NULL;
	pq->size = 0;
}

void QueueDestroy(Quene* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while(cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}

	pq->head = pq->tail = NULL;
	pq->size = 0;
}

void QueuePush(Quene* pq, QDataType x)
{
	assert(pq);

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

	newnode->next = NULL;
	newnode->data = x;

	//需要判断队列中是否有元素
	if (pq->head==NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}

	pq->size++;
}

void QueuePop(Quene* pq)
{
	assert(pq);//确保有队列
	assert(pq->head != NULL);//确保队列不为空

	if (pq->head->next==NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	pq->size--;
}

int QueueSize(Quene* pq)
{
	assert(pq);

	return pq->size;
}

bool QueueEmpty(Quene* pq)
{
	assert(pq);

	return pq->size==0;
}

QDataType QueueFront(Quene* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->head->data;
}

QDataType QueueBack(Quene* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->data;
}

Queue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

typedef struct BinaryTreeNode* QDataType;

//单个节点
typedef struct QueneNode
{
	struct QueneNode* next;
	QDataType data;
}QNode;

//整个队列
typedef struct Quene
{
	QNode* head;
	QNode* tail;
	int size;
}Quene;

//初始化
void QueueInit(Quene* pq);
//销毁
void QueueDestroy(Quene* pq);


//入队
void QueuePush(Quene* pq, QDataType x);
//出队
void QueuePop(Quene* pq);

//计算队列中元素的个数
int QueueSize(Quene* pq);
//判断队列是否为空
bool QueueEmpty(Quene* pq);

//队列中的队头元素
QDataType QueueFront(Quene* pq);
//队列中的队尾元素
QDataType QueueBack(Quene* pq);

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

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

相关文章

康冠医疗2021笔试题

康冠医疗2021笔试题

笔试时间：2020.09.24。 岗位：嵌入式软件工程师。 题型：13道题，40分钟。 6道填空，2道简答，5道编程，时间紧任务重。 1、填空 4、考察extern关键字。 6、const可以用来代替define ，define 只是简单的代替，但是const还会进行类型检查。 怎么避免头文件重复包含： #…
阅读更多...
Android 13(T) - Media框架（2）- libmedia

Android 13(T) - Media框架（2）- libmedia

这一节学习有两个目标&#xff1a; 1 熟悉Android Media API的源码路径与调用层次 2 从MediaPlayer的创建与销毁了解与native的串接 1、源码路径 Media相关的API位于&#xff1a;frameworks/base/media/java/android/media&#xff0c;里面提供有MediaPlayer MediaCodecList M…
阅读更多...
基于SpringBoot+Vue的MOBA类游戏攻略分享平台设计与实现（源码+LW+部署文档等）

基于SpringBoot+Vue的MOBA类游戏攻略分享平台设计与实现（源码+LW+部署文档等）

博主介绍&#xff1a; 大家好&#xff0c;我是一名在Java圈混迹十余年的程序员&#xff0c;精通Java编程语言&#xff0c;同时也熟练掌握微信小程序、Python和Android等技术&#xff0c;能够为大家提供全方位的技术支持和交流。 我擅长在JavaWeb、SSH、SSM、SpringBoot等框架…
阅读更多...
C++初阶引用

C++初阶引用

目录 引用引用的特性使用输出型参数作返回值小总结引用的权限引用和指针 引用 引用不是新定义一个变量&#xff0c;而是给已存在变量取了一个别名&#xff0c;编译器不会为引用变量开辟内存空间&#xff0c;它和它引用的变量共用同一块内存空间。 比如周树人&#xff0c;在外…
阅读更多...
spring.config.location 手动指定配置文件文件

spring.config.location 手动指定配置文件文件

–spring.config.locationD:\javaproject\bangsun\ds-admin\ds-oper-mgr\src\main\resources\application.yml
阅读更多...
网络安全/黑客-自学经验

网络安全/黑客-自学经验

一、为什么选择网络安全&#xff1f; 这几年随着我国《国家网络空间安全战略》《网络安全法》《网络安全等级保护2.0》等一系列政策/法规/标准的持续落地&#xff0c;网络安全行业地位、薪资随之水涨船高。 未来3-5年&#xff0c;是安全行业的黄金发展期&#xff0c;提前踏入…
阅读更多...
2023华数杯数学建模C题母亲对婴儿影响论文完整讲解

2023华数杯数学建模C题母亲对婴儿影响论文完整讲解

大家好呀&#xff0c;从昨天发布赛题一直到现在&#xff0c;总算完成了华数杯数学建模C题完整的成品论文。 本论文可以保证原创&#xff0c;保证高质量。绝不是随便引用一大堆模型和代码复制粘贴进来完全没有应用糊弄人的垃圾半成品论文。 C题论文共72页&#xff0c;一些修改说…
阅读更多...
css实现,正常情况下div从左到右一次排列,宽度超出时,右侧最后一个div固定住,左侧其他div滚动

css实现,正常情况下div从左到右一次排列,宽度超出时,右侧最后一个div固定住,左侧其他div滚动

需求:正常情况下 宽度超出时: 实现: <templete><div class"jieduanbox"><div v-for"(item, index) in stageList" :key"index" style"display: inline-block">.......</div><div class"rightBtn&q…
阅读更多...
STM32CUBUMX配置RS485 modbus STM32（从机）亲测可用

STM32CUBUMX配置RS485 modbus STM32（从机）亲测可用

———————————————————————————————————— ⏩ 大家好哇&#xff01;我是小光&#xff0c;嵌入式爱好者&#xff0c;一个想要成为系统架构师的大三学生。 ⏩最近在开发一个STM32H723ZGT6的板子&#xff0c;使用STM32CUBEMX做了很多驱动&#x…
阅读更多...
RVC实时变声器最新版

RVC实时变声器最新版

文章目录 一、前言二、变声器下载使用下载解压声音设置模型下载模型使用 一、前言 上次写的RVC变声器更新了&#xff0c;可能是用户的激增&#xff0c;原作者也更新的比较勤&#xff0c;本文只对变声器客户端更新使用教程&#xff0c;其他训练等等与上次一样。旧版教程 二、变…
阅读更多...
【c++】VSCode配置 c++ 环境（重新制作）

【c++】VSCode配置 c++ 环境（重新制作）

上一篇帖子【c】VSCode配置 c 环境&#xff08;小白教程&#xff09;_vscode配置c/c环境_StudyWinter的博客-CSDN博客 大火&#xff0c;但是依旧有很多小伙伴反应没有配好环境&#xff0c;今天打算重新写一个教程&#xff0c;希望对大家有帮助。 1 MinGW下载安装 在CSDN上传了…
阅读更多...
27 使用Arrays.asList生成的集合无法使用add、addAll方法及解决方法。

27 使用Arrays.asList生成的集合无法使用add、addAll方法及解决方法。

27.1 原因 使用 Array.asList方法生成的ArrayList继承的是AbstractList抽象类 &#xff0c;如下图所示。 AbstractList又继承了AbstractCollection抽象类&#xff0c;实现了List接口的方法&#xff0c;如下图所示。 如下图所示。可以发现&#xff0c; AbstractionCollection实现…
阅读更多...
神码ai火车头标题伪原创【php源码】

神码ai火车头标题伪原创【php源码】

这篇文章主要介绍了如何把python 代码打包成可执行软件&#xff0c;具有一定借鉴价值&#xff0c;需要的朋友可以参考下。希望大家阅读完这篇文章后大有收获&#xff0c;下面让小编带着大家一起了解一下。 火车头采集ai伪原创插件截图&#xff1a; Python 程序封装-打包成exe程…
阅读更多...
公文写作技巧：“三面镜子”写作提纲60例

公文写作技巧：“三面镜子”写作提纲60例

写作技巧&#xff1a;“三面镜子”写作提纲60例 1. 用好“三面镜子” 推深做实警示教育 勤用“反光镜”以案为鉴。 善用“显微镜”以案明纪。 巧用“聚光镜”以案促改。 2. 年轻干部要用好“三面镜子” 用好“反光镜”&#xff0c;照亮基层中的“暗点” 用好“显微镜”&am…
阅读更多...
【Kubernetes】Kubernetes之二进制部署

【Kubernetes】Kubernetes之二进制部署

kubernetes 一、Kubernetes 的安装部署1. 常见的安装部署方式1.1 Minikube1.2 Kubeadm1.3 二进制安装部署2. K8S 部署 二进制与高可用的区别2.1 二进制部署2.2 kubeadm 部署二、Kubernetes 二进制部署过程1. 服务器相关设置以及架构2. 操作系统初始化配置3. 部署 etcd 集群4. 部…
阅读更多...
Visual Studio在Debug模式下，MFC工程中包含Eigen库时的定义冲突的问题

Visual Studio在Debug模式下，MFC工程中包含Eigen库时的定义冲突的问题

Visual Studio在Debug模式下&#xff0c;MFC工程中包含Eigen库时的定义冲突的问题 报错信息 Eigen\src\Core\PlainObjectBase.h(143,5): error C2061: 语法错误: 标识符“THIS_FILE” Eigen\src\Core\PlainObjectBase.h(143,1): error C2333: “Eigen::PlainObjectBase::opera…
阅读更多...
45.ubuntu Linux系统安装教程

45.ubuntu Linux系统安装教程

目录 一、安装Vmware 二、Linux系统的安装 今天开始了新的学习&#xff0c;Linux,下面是今天学习的内容。 一、安装Vmware 这里是在 Vmware 虚拟机中安装 linux 系统&#xff0c;所以需要先安装 vmware 软件&#xff0c;然 后再安装 Linux 系统。 所需安装文件&#xff1a;…
阅读更多...
JavaEE 面试常见问题

JavaEE 面试常见问题

一、常见的 ORM 框架有哪些&#xff1f; 1.Mybatis Mybatis 是一种典型的半自动的 ORM 框架&#xff0c;所谓的半自动&#xff0c;是因为还需要手动的写 SQL 语句&#xff0c;再由框架根据 SQL 及 传入数据来组装为要执行的 SQL 。其优点为&#xff1a; 1. 因为由程序员…
阅读更多...
W5100S-EVB-PICO做DNS Client进行域名解析（四）

W5100S-EVB-PICO做DNS Client进行域名解析（四）

前言 在上一章节中我们用W5100S-EVB-PICO通过dhcp获取ip地址&#xff08;网关&#xff0c;子网掩码&#xff0c;dns服务器&#xff09;等信息&#xff0c;给我们的开发板配置网络信息&#xff0c;成功的接入网络中&#xff0c;那么本章将教大家如何让我们的开发板进行DNS域名解…
阅读更多...
ARM微架构

ARM微架构

一、流水线 二、指令流水线 指令流水线 指令流水线 指令流水线 ARM指令流水线 ARM7采用3级流水线 ARM9采用5级流水线 Cortex-A9采用8级流水线 注1&#xff1a;虽然流水线级数越来越多&#xff0c;但都是在三级流水线的基础上进行了细分 PC的作用&#xff08;取指&#xff09; …
阅读更多...
最新文章

Copyright @ 2022~2023