二叉树的实现

一、结构体声明和函数声明

#pragma once

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<stdlib.h>      
#include<assert.h>
#include<string.h>
#include<stdbool.h>

//二叉树

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

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);
// 二叉树销毁
void BinaryTreeDestory(BTNode* root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);





//队列

typedef BTNode* QDataType;  //将队列的元素类型设置为二叉树指针类型
// 链式结构:表示队列 
typedef struct QListNode
{
    struct QListNode* next;
    QDataType data;
}QNode;

// 队列的结构 
typedef struct Queue
{
    QNode* front; //指向队列的第一个结点
    QNode* rear;//指向队列的最后一个结点
    int size;//记录队列中一共有几个元素
}Queue;



// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
int QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);

二、二叉树各个函数的实现

1.二叉树构建函数: BinaryTreeCreate

利用前序遍历数组构建二叉树

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)//n为字符串长度,要使用下标i的指针,
     //这样才可以改变其的值
{
	if (*pi == n - 1)//如果字符数组的下标到达字符串长度-1 的位置,说明已经构建完成
		return NULL;

		 //如果是空节点,就不要申请空间
		if (a[*pi] == '#')
		{
			(*pi)++;
			return NULL;
		}

			//如果不是空节点,要申请一个空间存储结点的数据
			BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
			if (newnode == NULL)
			{
				perror("malloc fail");
				return NULL;
			}
			//存储当前的字符串中的数据信息
			newnode->data = a[*pi];
			(*pi)++;

		//构建左右子树
		newnode->left = BinaryTreeCreate(a,n,pi);
		newnode->right = BinaryTreeCreate(a, n, pi);

		return newnode;
}

 2.二叉树销毁函数: BinaryTreeDestory

确保能够将所有结点都删除,所有要采用后序遍历的方法来进行对每一个结点的删除

// 二叉树销毁
void BinaryTreeDestory(BTNode* root)//后序遍历销毁
{
	if (root == NULL)
		return ;

	BinaryTreeDestory(root->left);
	BinaryTreeDestory(root->right);
	free(root);//释放结点
}



3.求二叉树节点个数函数: BinaryTreeSize

结点为空,说明没有结点,否则其等于:左子树结点+右子树结点+1(自己本身)

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)//结点为空,返回0,否则返回,左子树+右子树+1
{
	if (root == NULL)  //如果该结点为空,返回0
		return 0;

	//每个结点,都是由左子树的结点个数+右子树的结点个数+1(自己本身)
	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;//左子树+右子树+1
}

 

 4.求二叉树叶子节点个数函数: BinaryTreeLeafSize

如果左右子树都为空,说明是叶子结点,如果不是,继续判断它的左右孩子结点的情况

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)//如果该结点为空,返回0
		return 0;

	if (root->left == NULL && root->right == NULL)//如果左右子树都为空,说明是叶子结点,返回1
		return 1;

	//不是叶子结点,遍历其左,右子树
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

 

5. 求二叉树第k层节点个数函数:BinaryTreeLevelKSize

 空结点返回0,第一层返回1,其他层 返回 左子树的k-1层+右子树的k-1层的 结点总和

// 二叉树第k层节点个数
//空结点返回0,第一层返回1,其他层 返回 左子树的k-1层+右子树的k-1层的 结点总和
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)//如果该结点为空,返回0
		return 0;

	if (k == 1)  //第一层只有一个结点,返回1
		return 1;
	
	//其他层 返回 左子树的k-1层+右子树的k-1层的 结点总和
	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

 


 6.二叉树查找值为x的节点函数:BinaryTreeFind

每次查找都要创建一个二叉树节点类型的临时变量,来记录每次的查找结果,并将其返回

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)//如果结点为空,返回NULL,说明没找到
		return NULL;

	if (root->data == x)  //如果该结点的值等于要寻找的值,就将该结点返回
		return root;

	BTNode* ret1 = BinaryTreeFind(root->left, x);   //保证每次都先找该结点的左孩子,后找右孩子
	if (ret1)   //如果找到的不是NULL,就将其结点返回
		return ret1;

	BTNode* ret2 = BinaryTreeFind(root->right, x);
	if (ret2)     //如果找到的不是NULL,就将其结点返回
		return ret2;

	return NULL;  //没找到返回NULL
}

 

 7.二叉树前序遍历函数:  BinaryTreePrevOrder

先访问根结点,再访问左子树和右子树

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}

	printf("%c", root->data);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
}

 

 8.二叉树中序遍历函数:BinaryTreeInOrder

先访问左子树,再是根节点,最后是右子树

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}

	BinaryTreeInOrder(root->left);
	printf("%c", root->data);
	BinaryTreeInOrder(root->right);
}


 9.二叉树后序遍历函数:BinaryTreePostOrder

先访问左子树和右子树,最后访问根结点

// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreePostOrder(root->left);
	BinaryTreePostOrder(root->right);
	printf("%c", root->data);
}

 


 10.层序遍历函数:BinaryTreeLevelOrder

(1)思路方法

使用队列的性质,先进先出,出元素在队头,入元素在队尾。

首先将树的根节点入队列,然后将队头元素出队列,这时还要将这个刚出队列的队头结点的左右孩子结点入队列,(如果非空入队列,空结点不要入队列)。

使用循环,直至队列为空,循环停止。按层次依次输出所有值

因为队头元素每出队一次,都在更新,所以所有的结点都是按照层次顺序依次进入队列,然后依次出队列

(2)队列的实现代码:
// 初始化队列 
void QueueInit(Queue* q)
{
    assert(q);
    q->front = NULL;  //初始化为NULL
    q->rear = NULL;//初始化为NULL
    q->size = 0;  //初始化个数为0
}

// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
    assert(q);

    QNode* newnode = (QNode*)malloc(sizeof(QNode));//申请新的结点
    if (newnode == NULL)
    {
        perror("malloc fail");
        return;
    }
    else
    {
        newnode->data = data;
        newnode->next = NULL;

        if (q->front == NULL)  //如果front指针指向的是NULL,说明插入前队列是空队列
        {
            q->front = newnode;
            q->rear = newnode;
        }
        else        //front指向的不是NULL,说明不是空队列
        {
            q->rear->next = newnode;
            q->rear = newnode;
        }
        q->size++;  //插入完,个数加1
    }
}

// 队头出队列 
void QueuePop(Queue* q)//出队就是头删
{
    assert(q);
    assert(q->size != 0);//队列不为空

    QNode* head = q->front;  //找到头结点
    if (head->next == NULL)//如果出队之前,前队列只有一个结点  
    {
        free(head);   //释放头结点,后front 和rear都要指向NULL,表示现在是空队列
        head = NULL;
        q->front = q->rear = NULL;
        q->size = 0;     //个数置为0
        return;
    }
    else   //出队前,队列有两个及其以上的结点数
    {
        QNode* del = head;
        head = head->next; //更新头结点
        free(del);
        del = NULL;
        q->front = head;   //将front 指向更新后的头结点
        q->size--;//个数减1
    }
}

// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
    assert(q);

    return q->front->data;
}

// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
    assert(q);

    return q->rear->data;
}

// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
    assert(q);

    return q->size;
}

// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
int QueueEmpty(Queue* q)
{
    assert(q);

    if (q->front == NULL)//队列为空,返回1
        return 1;
    else
        return 0;
}

// 销毁队列 
void QueueDestroy(Queue* q)
{
    assert(q);

    QNode* del = q->front;  //如果是空队列,就直接返回NULL,不要释放结点
    if (del == NULL)
    {
        ;
    }
    else
    {
        QNode* cur = del->next;
        while (del != NULL)    //逐个释放结点
        {

            free(del);
            del = cur;
            if (cur != NULL)
                cur = cur->next;
        }
    }
    //队头指针和队尾指针都是要置NULL的,size都是要置为0
    q->front = q->rear = NULL;
    q->size = 0;
}

 

(3)层次遍历算法代码
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)//利用队列实现
{
	Queue Q;
	QueueInit(&Q);//初始化队列

	if(root!=NULL)
	QueuePush(&Q, root);//根结点入队列

	while (!QueueEmpty(&Q))
	{
		BTNode* temp = QueueFront(&Q);//取队头元素  
		printf("%c", temp->data);//打印队头结点 所对应的数据元素
		QueuePop(&Q);//队头元素出队

		//队头元素出队后,将其左右两个孩子结点入队 (孩子结点为空,没有进入队列)
		if(temp->left!=NULL)    //左孩子不为空,入队列
		QueuePush(&Q, temp->left);

		if (temp->right != NULL) //右孩子不为空,入队列
		QueuePush(&Q, temp->right);
	}
	QueueDestroy(&Q);//最后销毁队列
}

 

 


11. 判断二叉树是否是完全二叉树函数: BinaryTreeComplete

(1)思路方法

使用队列的性质,先进先出,出元素在队头,入元素在队尾。

首先将树的根节点入队列,然后将队头元素出队列,这时还要将这个刚出队列的队头结点的左右孩子结点入队列,(空与非空结点都入队列)。

先使用一个循环,队列为非空为循环条件,元素依次人队和出队

如果队头元素出队时,遇到空结点,就跳出循环。说明找到了一个空节点
现在要再次使用循环,判断在空节点之后是否有出现非空结点,有说明不是完全二叉树,没有说明是完全二叉树

(2)算法代码
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue Q;
	QueueInit(&Q);//初始化队列

	if (root != NULL)
		QueuePush(&Q, root);//根结点入队列

	while (!QueueEmpty(&Q))
	{
		BTNode* temp = QueueFront(&Q);//取队头结点元素
		QueuePop(&Q);//队头元素出队
		if (temp == NULL)  //如果出队的队头元素为NULL,就跳出循环,
			                    //寻找接下来有没有非空结点
		{
			break;
		}

		//队头元素出队后,将其左右两个孩子结点入队 (孩子结点为空,也进入了队列)
			QueuePush(&Q, temp->left);//左孩子入队列
			QueuePush(&Q, temp->right); //右孩子入队列
	}

	//再次使用循环,判断在空节点之后是否有出现非空结点,有说明不是完全二叉树,没有说明是完全二叉树
	while (!QueueEmpty(&Q))
	{
		QDataType temp = QueueFront(&Q);//取队头元素  (QDataType是QNode*的类型)
		QueuePop(&Q);//队头元素出队

		if (temp != NULL)  //如果找到队头元素不是空,说明不是完全二叉树,返回false
		{
			QueueDestroy(&Q);//最后销毁队列
			return false;
		}
	}

	QueueDestroy(&Q);//最后销毁队列
	return true;    //是完全二叉树,返回true
}

 

 

三、测试 

int main()
{
	char arr[] = "ABD##E#H##CF##G##";
	int len = strlen(arr);
	int i = 0;
	//构建二叉树
	BTNode* root = BinaryTreeCreate(arr, len, &i);

	//水平遍历
	BinaryTreeLevelOrder(root);
	printf("\n");

	int cur = BinaryTreeComplete(root);
	if (cur == 1)
		printf("是完全二叉树\n");
	else
		printf("不是完全二叉树\n");


	//前序遍历
	printf("前序遍历结点:");
	BinaryTreePrevOrder(root);
	printf("\n");
	//中序遍历
	printf("中序遍历结点:");
	BinaryTreeInOrder(root);
	printf("\n");
	//后序遍历
	printf("后序遍历结点:");
	BinaryTreePostOrder(root);
	printf("\n");


	int a=BinaryTreeLevelKSize(root, 4);
	printf("该层有%d个\n", a);

	int b=BinaryTreeLeafSize(root);
	printf("叶子结点有%d个\n", b);

	 int c=	BinaryTreeSize(root);
	 printf("总结点有%d个\n", c);

	int d=BinaryTreeDepth(root);
	printf("树深为%d\n", d);

	BinaryTreeDestory(root);//销毁二叉树
	return 0;
}

 

结果:

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

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

相关文章

最新淘宝死店全自动采集私信筛选脚本,号称日赚500+【采集软件+使用教程】

原理&#xff1a; 利用脚本自动采集长时间未登录店铺&#xff0c;然后脚本自动私信对应的店铺&#xff0c;看看商家是不是不回消息来判断是否是死店&#xff0c;再下单购买死店的产品&#xff0c;超过48小时不发货就可以联系客服获得赔付&#xff0c;一单利润百分之5%-30%&…

STP19NF20 丝印 19NF20 场效应管19A 200V 直插 TO-220

STP19NF20 功率MOSFET的应用领域相当广泛&#xff0c;主要包括&#xff1a; 1. 电源管理&#xff1a;用于高效率电源管理电路&#xff0c;如直流-直流转换器和交流-直流电源适配器。 2. 开关模式电源&#xff08;SMPS&#xff09;&#xff1a;在需要高效能和紧凑型尺寸的开关…

【数据结构】二叉树的链式结构

目录 一.二叉树的遍历 1.前序遍历 2.中序遍历 3.后序遍历 4.层序遍历 二.二叉树查询的基本操作 1.二叉树节点的个数 2.二叉树叶子节点的个数 3.二叉树的高度 4.二叉树第k层节点的个数 5.二叉树查询值为x的节点 6.判断二叉树是否为完全二叉树 7.二叉树基础oj练习 三…

【Python编程实践2/3】Python图像处理模块(上)

目录 引言 目标 安装模块 Windows系统 macOS系统 路径 Windows路径 ​编辑macOS路径 windows路径报错 windows路径前的r 示例代码 windows快速查看路径 macOS快速查看路径 打开图片 展示图片 下节预告 总结 引言 欢迎各位大佬垂阅本篇Python实践博客&a…

一文读懂python同级目录的调用附Demo(详细解读)

目录 前言1. 问题所示2. 原理分析3. 解决方法3.1 添加父目录3.2 相对路径3.3 添加init 前言 通过制作简易的Demo&#xff0c;让其更加深入的了解如何使用 1. 问题所示 发现python的同级目录相互调用会出Bug E:\software\anaconda3\envs\py3.10\python.exe F:\python_project…

python之生成xmind

今天为啥要说这个呢&#xff0c;因为前几天做接口测试&#xff0c;还要写测试用例&#xff0c;我觉得麻烦&#xff0c;所以我就用了python里面xmind的插件。自动生成了测试用例&#xff0c;数据来源是json。 &#x1f366; 第一步安装 pip install xmind &#x1f366; 第二…

01_Spring Ioc(详解) + 思维导图

文章目录 思维导图一.概念实操Maven父子工程 二. IOC和DI入门案例【重点】1 IOC入门案例【重点】问题导入1.1 门案例思路分析1.2 实现步骤2.1 DI入门案例思路分析2.2 实现步骤2.3 实现代码2.4 图解演示 三、Bean的基础配置问题导入问题导入1 Bean是如何创建的【理解】2 实例化B…

【408真题】2009-26

“接”是针对题目进行必要的分析&#xff0c;比较简略&#xff1b; “化”是对题目中所涉及到的知识点进行详细解释&#xff1b; “发”是对此题型的解题套路总结&#xff0c;并结合历年真题或者典型例题进行运用。 涉及到的知识全部来源于王道各科教材&#xff08;2025版&…

Camunda BPM主要组件

Camunda BPM是使用java开发的,核心流程引擎运行在JVM里,纯java库,不依赖其他库或者底层操作系统。可以完美地与其他java框架融合,比如Spring。除了核心流程引擎外,还提供了一系列的管理,操作和监控工具。 1,工作流引擎 既适用于服务或者微服务编排,也适用于人工任务管…

VBA技术资料MF159:实现某个区域内的数据滚动

我给VBA的定义&#xff1a;VBA是个人小型自动化处理的有效工具。利用好了&#xff0c;可以大大提高自己的工作效率&#xff0c;而且可以提高数据的准确度。“VBA语言専攻”提供的教程一共九套&#xff0c;分为初级、中级、高级三大部分&#xff0c;教程是对VBA的系统讲解&#…

详解 Spark 的运行架构

一、核心组件 1. Driver Spark 驱动器节点&#xff0c;用于执行 Spark 任务中的 main 方法&#xff0c;负责实际代码的执行工作主要负责&#xff1a; 将用户程序转化为作业 (job)在 Executor 之间调度任务 (task)跟踪 Executor 的执行情况通过 UI 展示查询运行情况 2. Exec…

Springboot 实战运用

一&#xff0c;基本配置 1&#xff0c;pom文件配置介绍 1.1继承 <parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId><version>2.5.2</version><relativePath/> <…

MATLAB分类与判别模型算法:基于模糊神经网络的嘉陵江水质评价【含Matlab源码 MX_004期】

算法思路介绍&#xff1a; 基于模糊神经网络的水质预测系统&#xff0c;整体思路分为以下几个模块&#xff1a; 1. 数据准备模块 加载数据&#xff1a;从文件中加载训练和测试数据&#xff0c;包括输入数据和输出数据。数据归一化&#xff1a;对加载的数据进行归一化处理&am…

第十九节:带你梳理Vue2: 父组件向子组件传参(props传参)

1. 组件嵌套 1.1 组件的嵌套使用 之前有说过,Vue组件跟Vue实例是一样的,因此在Vue中一个组件中也可以定义并使用自己的局部组件,这就是组件的嵌套使用 例如:示例代码如下: <div id"app"><!-- 3. 使用组件 --><my-component></my-component&…

教学基本功包括什么技能有哪些

教师的工作不仅仅是传授知识&#xff0c;更多是引导学生探索&#xff0c;激发他们的创造力。要做到这一点&#xff0c;需要具备一些基本技能。 扎实的专业知识。这是教师的根基&#xff0c;如果教师自己对所教的科目都不熟悉&#xff0c;那么教学就会失去方向。不断学习更新自己…

告别虚拟机,在Windows10启动Linux子系统

背景 如果要在自己的windows电脑安装一个Linux系统,一般是用虚拟机软件例如VMware软件来创建。但是这种方式显得非常的笨重。而Windows10自带的Linux子系统则非常的方便。 分析 在Windows10中启用子系统的方式来安装Linux,用于学习和开发是非常方便的。子系统的实用就和一个…

基于深度学习的中文情感分析系统python flask

基于python的毕业设计 基于深度学习的中文情感分析系统(flask)(源码说明文档演示) 毕业设计课程设计期末大作业、课程设计、高分必看&#xff0c;下载下来&#xff0c;简单部署&#xff0c;就可以使用。 包含&#xff1a;项目源码、数据库脚本、软件工具等&#xff0c;该项目…

3D模型三角面转四角面操作指南---模大狮模型网

在3D建模的过程中&#xff0c;三角面(Triangles)和四角面(Quads)是两种常见的多边形类型。虽然三角面在渲染速度和计算效率上有其优势&#xff0c;但四角面在模型编辑和纹理映射上通常更为方便。因此&#xff0c;将三角面转换为四角面是建模过程中常见的需求。 一、选择合适的建…

py黑帽子学习笔记_scapy

简介 代码简洁&#xff1a;相比于前两个博客总结&#xff0c;很多socket操作&#xff0c;如果使用scapy仅需几行代码即可实现 获取邮箱身份凭证 编写基础嗅探器&#xff0c;脚本可显示任何收到的一个包的详细情况 直接运行 尝试监听邮件收发&#xff0c;监听指定端口&#x…

高性价比、超强功能的开源工单解决方案

在企业日常运营中&#xff0c;工单管理系统是不可或缺的工具。高效的工单管理不仅能提升工作效率&#xff0c;还能显著提高客户满意度。今天&#xff0c;我们为您推荐搭贝工单派单系统——一款超高性价比、功能齐全的开源工单管理系统。 &#x1f50d; 为什么选择搭贝工单派单…