C学习(数据结构)-->实现链式结构二叉树

news/2024/9/18 14:46:15/ 标签: c语言, 学习, 数据结构

目录

一、链式二叉树结构

 二、实现

1、申请新结点

2、前、中、后序遍历

1)前序遍历

例:

2)中序遍历

3)后序遍历

 3、结点个数

1)二叉树结点个数

 例:​编辑

2)二叉树叶子结点个数

3)二叉树第k层结点个数

​编辑 4、二叉树深度

例: 

5、寻找值为x的结点

6、二叉树的销毁

三、其它

0、注意:

1、层序遍历

例:​编辑

当前队列初始化后为空队列

首先入队列

然后如果队列不为空则进入循环

 退出循环,层序遍历完成

2、判断是否为完全二叉树

四、总代码

队列  

链式二叉树

Tree.h

Tree.cpp

main.cpp


一、链式二叉树结构

//定义二叉树的链式结构
typedef int BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;

 二、实现

1、申请新结点

//申请二叉树结点
BTNode* BuyNode(BTDataType x)
{BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));if (newNode == NULL){perror("malloc fail!!!");exit(1);}newNode->data = x;newNode->left = newNode->right = NULL;return newNode;
}

2、前、中、后序遍历

1)前序遍历

前序遍历的遍历顺序是:根结点-->左孩子结点-->右孩子结点

//前序遍历--根左右
void PreOrder(BTNode* root)
{if (root == NULL)//判空{return;}printf("%d ", root->data);//打印根结点PreOrder(root->left);//遍历左孩子结点PreOrder(root->right);//遍历右孩子结点
}
例:

一个链式二叉树

首先 1 作为根节点,遍历根结点,且打印根节点

打印完后,再向左孩子结点遍历,即标号为 2 的结点

标号为 2 的结点作为新的根结点,遍历 2 结点,且打印

然后遍历 2 结点的左孩子结点,即标号为 4 的结点

标号为 4 的结点作为新的根结点,遍历 4 结点,且打印

 

遍历 4 结点的左孩子结点,即为为NULL

 

应为是NULL,所以返回,然后遍历4 结点的右孩子结点,也是NULL

 

 4 结点的右孩子结点,也是NULL,所以返回。

此时4结点已经遍历完,放回 2 结点,因为 4 结点是 2 结点的左孩子结点,开始遍历 2 结点的右孩子结点,即标号为 6 的结点

遍历完 6 结点,再次返回 2 结点,此时 2 结点的左右孩子结点都遍历完,所以返回 1 结点,此时 1 结点的左孩子结点已经遍历完成,则遍历1 结点的右孩子结点,即 3 结点

 此时整个链式二叉树已经遍历完成,打印顺序为:1 2 4 5 3 6

2)中序遍历

 中序遍历的顺序:是左孩子结点-->根节点-->右孩子结点

//中序遍历--左根右
void InOrder(BTNode* root)
{if (root == NULL)//判空{return;}InOrder(root->left);//遍历左孩子结点printf("%d ", root->data);//打印根结点InOrder(root->right);//遍历右孩子结点
}

以前序遍历为例,易得中序遍历的打印顺序为:4 2 5 1 6 3

3)后序遍历

后序遍历的遍历顺序为:左孩子结点-->右孩子结点-->根节点

//后序遍历--左右根
void PostOrder(BTNode* root)
{if (root == NULL)//判空{return;}PostOrder(root->left);//遍历左孩子结点PostOrder(root->right);//遍历右孩子结点printf("%d ", root->data);//打印根结点
}

 以前序遍历为例,易得后序遍历的打印顺序为:4 5 2 6 3 1

 3、结点个数

1)二叉树结点个数

//二叉树结点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL)//判空{return 0;//当结点为空时返回 0 }//该节点不是空结点,返回 1 + 递归左右孩子结点返回的个数return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
 例:

 所以二叉树的结点个数为 6 

2)二叉树叶子结点个数

//二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL)//判空{return 0;//结点为空时返回 0 }if (root->left == NULL && root->right == NULL)//判读叶子结点{return 1;//该结点是叶子结点返回 1}//当该节点既不是空结点也不是叶子结点时,返回递归左右孩子结点返回的个数return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

易得该二叉树叶子结点个数为 3 

3)二叉树第k层结点个数

//二叉树第k层结点个数
int BinaryTreeLexelKSize(BTNode* root, int k)
{if (root == NULL)//判空,空结点返回 0{return 0;}if (k == 1)// k 的递归是递减的,当 k == 1 时,即到达第 k 层,返回 1{return 1;}//即不是第 k 层,也不是空结点,返回递归左右孩子结点得到的数return BinaryTreeLexelKSize(root->left, k - 1) + BinaryTreeLexelKSize(root->right, k - 1);
}

 例:求第二层结点个数

 4、二叉树深度

//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}//保存递归左右孩子结点返回的数int leftDep = BinaryTreeDepth(root->left);int rightDep = BinaryTreeDepth(root->right);//比较左右孩子结点返回的数大小,满足条件返回 1 + leftdep,否则 1 + rightDepreturn leftDep > rightDep ? 1 + leftDep : 1 + rightDep;
}

例: 

所以该二叉树的深度为 3  

5、寻找值为x的结点

//二叉树寻找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{//如果结点为空if (root == NULL){return NULL;}if (root->data == x)//找到该x值返回该结点地址{return root;}BTNode* leftFind = BinaryTreeFind(root->left, x);//保存递归返回的结点地址if (leftFind)//结点地址不为空,只有找到 x 值才不为空{return leftFind;//返回的结点地址}BTNode* rightFind = BinaryTreeFind(root->right, x);//保存递归返回的结点地址if (rightFind)//结点地址不为空,只有找到 x 值才不为空{return rightFind;//返回的结点地址}//x值找不到return NULL;
}

6、二叉树的销毁

类似后序遍历

//二叉树的销毁
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestory(&((*root)->left));BinaryTreeDestory(&((*root)->right));free(*root);*root = NULL;
}

三、其它

0、注意:

需要用到队列,具体到C学习数据结构)-->队列_cpp 队列-CSDN博客

需要将队列的

typedef int QDataType;

改为

typedef struct BinaryTreeNode* QDataType;

1、层序遍历

//层序遍历,借用队列来实现
void LevelOrder(BTNode* root)
{Qu q;//初始化QueueInit(&q);//入队列QueuePush(&q, root);while (!QueueEmpty(&q))//判空{BTNode* front = QueueFront(&q);//取队头数据printf("%d ", front->data);//打印队头数据//出队列QueuePop(&q);if (front->left)//如果该结点的左孩子结点不为空{QueuePush(&q, front->left);//入队列}if (front->right)//如果该结点的右孩子结点不为空{QueuePush(&q, front->right);//入队列}}//销毁队列QueueDestroy(&q);
}

例:

当前队列初始化后为空队列

首先入队列
	//入队列QueuePush(&q, root);

然后如果队列不为空则进入循环

while (!QueueEmpty(&q))//判空
{BTNode* front = QueueFront(&q);//取队头数据printf("%d ", front->data);//打印队头数据//出队列QueuePop(&q);if (front->left)//如果该结点的左孩子结点不为空{QueuePush(&q, front->left);//入队列}if (front->right)//如果该结点的右孩子结点不为空{QueuePush(&q, front->right);//入队列}
}

重复通过取队头数据,入队列,出队列来层序遍历二叉树

 退出循环,层序遍历完成

2、判断是否为完全二叉树

//用队列判断是否为完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Qu q;//初始化QueueInit(&q);//入队列QueuePush(&q, root);while (!QueueEmpty(&q))//判空{BTNode* front = QueueFront(&q);QueuePop(&q);//出队列if (front == NULL)//判空{break;}//入队列QueuePush(&q, front->left);QueuePush(&q, front->right);}//队列不一定为空while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front != NULL){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}

与层序遍历类似,不同的是,取消了判断左右孩子结点是否为空结点,所以就算左右孩子结点为空值结点也会入队列,所以不完全二叉树会出现这种情况

	//入队列QueuePush(&q, root);while (!QueueEmpty(&q))//判空{BTNode* front = QueueFront(&q);QueuePop(&q);//出队列if (front == NULL)//判空{break;}//入队列QueuePush(&q, front->left);QueuePush(&q, front->right);}

 当出队列的结点为空结点时退出循环,此时队列不为空,进入另一个循环

	//队列不一定为空while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front != NULL){QueueDestroy(&q);return false;}}	QueueDestroy(&q);return true;

通过判断队列里是否还有空值来判断是否是完全二叉树

 

四、总代码

队列  

queue.h

queue.cpp

 具体到C学习数据结构)-->队列_cpp 队列-CSDN博客

需要将队列的

typedef int QDataType;

改为

typedef struct BinaryTreeNode* QDataType;

链式二叉树

Tree.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//定义二叉树的链式结构
typedef int BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;
//前序遍历--根左右
void PreOrder(BTNode* root);
//中序遍历--左根右
void InOrder(BTNode* root);
//后序遍历--左右根
void PostOrder(BTNode* root);
//二叉树结点个数
int BinaryTreeSize(BTNode* root);	
//二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root);
//二叉树第k层结点个数
int BinaryTreeLexelKSize(BTNode* root, int k);
//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root);
//二叉树寻找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
//二叉树的销毁
void BinaryTreeDestory(BTNode** root);
//层序遍历,借用队列来实现
void LevelOrder(BTNode* root);
//用队列判断是否为完全二叉树
bool BinaryTreeComplete(BTNode* root);
//申请二叉树结点
BTNode* BuyNode(BTDataType x);

Tree.cpp

#include"Tree.h"
#include"Queue.h"//前序遍历--根左右
void PreOrder(BTNode* root)
{if (root == NULL){return;}printf("%d ", root->data);PreOrder(root->left);PreOrder(root->right);
}//中序遍历--左根右
void InOrder(BTNode* root)
{if (root == NULL){return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}//后序遍历--左右根
void PostOrder(BTNode* root)
{if (root == NULL){return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}//二叉树结点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}//二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL){return 1;}return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}//二叉树第k层结点个数
int BinaryTreeLexelKSize(BTNode* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}return BinaryTreeLexelKSize(root->left, k - 1) + BinaryTreeLexelKSize(root->right, k - 1);
}//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}int leftDep = BinaryTreeDepth(root->left);int rightDep = BinaryTreeDepth(root->right);return leftDep > rightDep ? 1 + leftDep : 1 + rightDep;
}//二叉树寻找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{//如果结点为空if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* leftFind = BinaryTreeFind(root->left, x);if (leftFind){return leftFind;}BTNode* rightFind = BinaryTreeFind(root->right, x);if (rightFind){return rightFind;}//x值找不到return NULL;
}//二叉树的销毁
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestory(&((*root)->left));BinaryTreeDestory(&((*root)->right));free(*root);*root = NULL;
}//层序遍历,借用队列来实现
void LevelOrder(BTNode* root)
{Qu q;//初始化QueueInit(&q);//入队列QueuePush(&q, root);while (!QueueEmpty(&q))//判空{BTNode* front = QueueFront(&q);//取队头数据printf("%d ", front->data);//出队列QueuePop(&q);if (front->left){QueuePush(&q, front->left);}if (front->right){QueuePush(&q, front->right);}}//如果队列为空,就销毁队列QueueDestroy(&q);
}//用队列判断是否为完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Qu q;//初始化QueueInit(&q);//入队列QueuePush(&q, root);while (!QueueEmpty(&q))//判空{BTNode* front = QueueFront(&q);QueuePop(&q);//出队列if (front == NULL)//判空{break;}//入队列QueuePush(&q, front->left);QueuePush(&q, front->right);}//队列不一定为空while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front != NULL){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}//申请二叉树结点
BTNode* BuyNode(BTDataType x)
{BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));if (newNode == NULL){perror("malloc fail!!!");exit(1);}newNode->data = x;newNode->left = newNode->right = NULL;return newNode;
}

main.cpp

#include"Tree.h"
#include"Queue.h"void test01()
{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 = node3;node2->left = node4;node2->right = node5;node3->left = node6;printf("前序遍历:");PreOrder(node1);printf("\n");printf("中序遍历:");InOrder(node1);printf("\n");printf("后序遍历:");PostOrder(node1);printf("\n");printf("二叉树结点个数:%d\n", BinaryTreeSize(node1));printf("二叉树叶子结点个数:%d\n", BinaryTreeLeafSize(node1));printf("二叉树第k层结点个数:%d\n", BinaryTreeLexelKSize(node1, 2));printf("二叉树的深度/高度:%d\n", BinaryTreeDepth(node1));BTNode* find = BinaryTreeFind(node1, 5);printf("二叉树寻找值为x的结点:%d\n", find->data);printf("层序遍历:");LevelOrder(node1);printf("\n");//判断是否为完全二叉树printf("%s\n", BinaryTreeComplete(node1) == true ? "是完全二叉树" : "不是完全二叉树");//二叉树的销毁BinaryTreeDestory(&node1);
}int main()
{test01();return 0;
}


http://www.ppmy.cn/news/1516735.html

相关文章

网络排名变差算法在充电桩计量可信度评价中的应用AcrelCloud-9000安科瑞充电柱收费运营云平台

摘要&#xff1a;网络排名变差算法是指根据充电交易流水数据构造桩车网络&#xff0c;利用复杂网络的投票智慧而非传统的物理实验来获得对量值的信心。将排名变差算法用于桩车网络计算中&#xff0c;旨在检定合格的充电桩对其他充电桩排名变化的影响&#xff0c;这种影响以电动…

计算机毕业设计选题推荐-OA办公管理系统-Java/Python项目实战

✨作者主页&#xff1a;IT毕设梦工厂✨ 个人简介&#xff1a;曾从事计算机专业培训教学&#xff0c;擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Py…

Git提交错误代码如何回退代码

1&#xff0c;找到需要回退的提交行&#xff0c;点击右键&#xff0c;点击重置当前分支到此次提交 2,选择强行合并 3&#xff0c;执行git pull -f 强行推送 4&#xff0c;如果当前账号没有开启本分支强推权限 需要去git开启 5&#xff0c;如果没有推送&#xff0c;处于待推…

深度学习学习经验——长短期记忆网络(LSTM)

长短期记忆网络&#xff08;LSTM&#xff09; 长短期记忆网络&#xff08;LSTM&#xff0c;Long Short-Term Memory&#xff09;是一种特殊的循环神经网络&#xff08;RNN&#xff09;&#xff0c;专为解决 RNN 中长期依赖问题而设计。LSTM 引入了三个门和一个细胞状态&#x…

Spring DI 数据类型——构造注入

首先新建项目&#xff0c;可参考 初识 IDEA 、模拟三层--控制层、业务层和数据访问层 一、spring 环境搭建 &#xff08;一&#xff09;pom.xml 导相关坐标 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.…

FPGA时序约束

FPGA时序约束 目录 FPGA时序约束 前言1、建立和保持时间1.1 建立时间1.2 保持时间 2 时序路径2 具体约束2.1 IO约束2.1.1 管脚约束2.1.2 延迟约束2.1.3 虚拟时钟 2.2周期约束&#xff0c;FPGA内部的时序路径2.2.1 主时钟2.2.2 衍生时钟2.2.3 主时钟之间的相互关系2.2.4 使用BUF…

S3协议分片上传(minio)

文章目录 前言一、minio 为例二、使用步骤1.引入库2.读入数据总结前言 目前文件存储一般采用obs存储,也就是对象存储 比较流行的有: minio 阿里云 华为云 阿里云 腾讯云 七牛云 百度云 ,对于贫穷的我来说,当然选择免费开源的minio了,但是他们有一个统一的标准也就是S3协议,相…

一文读懂 DDD领域驱动设计

DDD&#xff08;Domain-Driven Design&#xff0c;领域驱动设计&#xff09;是一种软件开发方法&#xff0c;它强调软件系统设计应该以问题领域为中心&#xff0c;而不是技术实现为主导。DDD通过一系列手段如统一语言、业务抽象、领域划分和领域建模等来控制软件复杂度&#xf…

【Rust光年纪】Rust多媒体处理库全面比较:探索安全高效的多媒体处理利器

多媒体处理不再困扰&#xff1a;解锁Rust语言下的六大多媒体利器 前言 随着Rust语言的快速发展&#xff0c;越来越多的多媒体处理库和工具集开始出现&#xff0c;为开发人员提供了丰富的选择。本文将对几个用于Rust语言的多媒体处理库进行介绍&#xff0c;并对它们的核心功能…

【算法】希尔排序、计数排序、桶排序、基数排序

1 希尔排序 2 计数排序 3 桶排序 4 基数排序 1 希尔排序 """ 希尔排序&#xff08;Shell Sort&#xff09;是一种插入排序算法的改进版本&#xff0c;得名于其发明者Donald Shell。 它通过比较一定间隔的元素来进行排序&#xff0c;以减少数据移动的次数&#…

Jmeter进行http接口测试

&#x1f345; 点击文末小卡片&#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 1、jmeter-http接口测试脚本 jmeter进行http接口测试的主要步骤&#xff08;1.添加线程组 2.添加http请求 3.在http请求中写入接口的URL&#xff0c;路径&#xf…

【HarmonyOS NEXT星河版开发实战】天气查询APP

目录 前言 界面效果展示 首页 添加和删除 界面构建讲解 1. 获取所需数据 2. 在编译器中准备数据 3. index页面代码讲解 3.1 导入模块&#xff1a; 3.2 定义组件&#xff1a; 3.3 定义状态变量: 3.4 定义Tabs控制器: 3.5 定义按钮样式&#xff1a; 3.6 页面显示时触发…

Java核心API——Collection集合的工具类Collections

集合的排序 int类型的排序 * 集合的排序 * java.util.Collections是集合的工具类&#xff0c;提供了很多static方法用于操作集合 * 其中提供了一个名为sort的方法&#xff0c;可以对List集合进行自然排序(从小到大) List<Integer> list new ArrayList<>();Rand…

96页PPT集团战略解码会工具与操作流程

德勤集团在战略解码过程中通常会用到以下一些具体工具&#xff1a; 一、平衡计分卡&#xff08;Balanced Scorecard&#xff09; 财务维度&#xff1a; 明确关键财务指标&#xff0c;如营业收入、利润、投资回报率等。你可以通过分析历史财务数据和行业趋势&#xff0c;确定…

设计模式24-命令模式

设计模式24-命令模式 写在前面行为变化模式 命令模式的动机定义与结构定义结构 C 代码推导优缺点应用场景总结补充函数对象&#xff08;Functors&#xff09;定义具体例子示例&#xff1a;使用函数对象进行自定义排序代码说明输出结果具体应用 优缺点应用场景 命令模式&#xf…

鸿蒙位置服务

位置服务 1、首先申请权限 在module.json5文件下申请位置权限 "requestPermissions": [{"name": "ohos.permission.LOCATION", // 权限名称,为系统已定义的权限"reason": "$string:location_reason", // 申请权限的原因,…

windows 核心编程第五章:演示作业的使用及获取统计信息

演示作业的使用及获取统计信息 演示作业的使用及获取统计信息 文章目录 演示作业的使用及获取统计信息演示作业的使用及获取统计信息 演示作业的使用及获取统计信息 /* 演示作业的使用及获取统计信息 */#include <stdio.h> #include <Windows.h> #include <tc…

HBase原理和操作

目录 一、HBase在Zookeeper中的存储元数据信息集群状态信息 二、HBase的操作Web Console命令行操作 三、HBase中数据的保存过程 一、HBase在Zookeeper中的存储 元数据信息 HBase的元数据信息是HBase集群运行所必需的关键数据&#xff0c;它存储在Zookeeper的"/hbase&quo…

ARM32开发——(七)GD32F4串口引脚_复用功能_查询

1. GD32F4串口引脚查询 TX RX CK CTS RTS USART0 PA9,PA15,PB6 PA10,PB3,PB7 PA8 PA11 PA12 USART1 PA2,PD5 PA3,PD6 PA4,PD7 PA0,PD3 PA1,PD4 USART2 PB10,PC10,PD8 PB11,PC5,PD9 PB12,PC12,PD10 PB13,PD11 PB14,PD12 UART3 PA0,PC10 PA1,PC11 …

kafka 入门

kafka 有分区和副本的概念&#xff0c;partition 3 表示有3个分区&#xff0c;replication 2 表示有2个副本 通过 --describe --topic test命令可以知道 test这个 主题的分区和副本情况&#xff0c;途中的replicas 表示 其他副本分区的情况&#xff0c;如第一条&#xff0c;t…