数据结构与算法学习笔记十二-二叉树的顺序存储表示法和实现(C语言)

目录

前言

1.数组和结构体相关的一些知识

1.数组

2.结构体数组

3.递归遍历数组

2.二叉树的顺序存储表示法和实现

1.定义

2.初始化

3.先序遍历二叉树

4.中序遍历二叉树

5.后序遍历二叉树

6.完整代码

前言

        二叉树的非递归的表示和实现。

1.数组和结构体相关的一些知识

1.数组

        在C语言中，可以将数组作为参数传递给函数。当数组作为参数传递时，实际上传递给函数的是数组的地址，而不是数组的副本。这意味着，在函数内部对数组进行的修改会影响到原始数组。

        例如在下面的代码中，我们把数组名作为参数传递给modifyArray函数，在函数中修改数组的值，main函数打印原来的数组，会发现原来的数组也被修改。

#include <stdio.h>
#include <stdlib.h>

void modifyArray(int *s,int size){
    for (int i = 0; i < size; i++) {
        s[i] = s[i] * 10;
    }
    printf("\n");
}

int main(int argc, const char *argv[]) {
    int arr[5] = {1,2,3,4,5};
    int length = sizeof(arr) / sizeof(arr[0]);
    printf("修改之前的数组:\n");
    for (int i =  0; i < length;i++) {
        printf("%d\t",arr[i]);
    }
    modifyArray(arr,length);
    printf("\n修改之前的数组:\n");
    for (int i =  0; i < length;i++) {
        printf("%d\t",arr[i]);
    }
    printf("\n");
    return 0;
}

        当然上述的函数我们还可以写成数组的形式。

void modifyArray(int s[],int size){
    for (int i = 0; i < size; i++) {
        s[i] = s[i] * 10;
    }
    printf("\n");
}

2.结构体数组

        在上述的代码中，我们使用数组操作基本数据类型非常的方便。当时当我们需要自定义数据类型的时候，上述的代码就不满足我们的需求了。例如我们需要表示学生数组的时候，因为每个学生都有自己的属性，姓名，年龄等等，这个时候我们就需要使用结构体数组。

        在数据结构中，我们有时候需要使用数组表示一些数据类型，因此有时候我们需要把数组声明为全局函数。代码实例如下：

#include <stdio.h>
#include <stdlib.h>

// 学生结构体
typedef struct {
    char name[50]; // 姓名
    int age;       // 年龄
} Student;

int main() {
    // 创建一个包含3个学生对象的数组并初始化
    Student students[3] = {
        {"张三", 20},
        {"李四", 21},
        {"王五", 22}
    };

    // 输出学生信息
    printf("学生信息如下：\n");
    for (int i = 0; i < 3; i++) {
        printf("学生姓名：%s\n", students[i].name);
        printf("学生年龄：%d\n", students[i].age);
    }

    return 0;
}

3.递归遍历数组

        在我们使用数组表示二叉树的时候，需要递归遍历数组，这里需要您了解数组递归的写法。

        在这个示例中以下面的代码为例，，recursivePrint 函数用于递归地遍历数组并打印数组中的元素。它接受三个参数：arr 表示数组，size 表示数组的大小，index表示当前遍历的索引位置。函数首先检查索引是否超出数组范围，如果是，则递归终止。否则，它打印当前索引处的数组元素，然后递归调用自身，传入下一个索引位置。在 main函数中，我们创建一个数组并调recursivePrint 函数来遍历打印数组元素。

#include <stdio.h>

// 递归遍历数组并打印数组中的元素
void recursivePrint(int arr[], int size, int index) {
    // 递归终止条件：当索引超出数组范围时，结束递归
    if (index >= size) {
        return;
    }
    
    // 打印当前索引处的数组元素
    printf("%d ", arr[index]);
    
    // 递归调用，遍历下一个元素
    recursivePrint(arr, size, index + 1);
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    printf("数组元素为：");
    recursivePrint(arr, size, 0);
    printf("\n");
    
    return 0;
}

2.二叉树的顺序存储表示法和实现

     图1.完全二叉树

               图2.普通二叉树

        我们使用一组连续的存储空间表示树的结构。按照从上到下、从左到右的顺序存储完全二叉树的的节点，对于一般二叉树上的点，我们使用0表示不存在该节点。

        对于图1来说，内存中的存储结构如下图3所示。

        图3.完全二叉树的存储结构

        如果不是二叉树，假如我们使用0表示结点不存在，图2所示的存储结构如图4所示。

图4.普通二叉树

        下面我们看看如果使用代码来实现。

1.定义

        我们使用数组实现二叉树的顺序存储

#define MAX_TREE_SIZE 100

typedef char TElemType;
typedef int Status;

typedef TElemType SqBiTree[MAX_TREE_SIZE];

2.初始化

        初始化时候，将数组中的元素全部设为"\0"

// 初始化二叉树
Status initSqBiTree(SqBiTree tree) {
    for (int i = 0; i< MAX_TREE_SIZE; i++) {
        tree[i] = '\0';
    }
    // 将二叉树所有元素初始化为空
    return 1; // 初始化成功
}

3.先序遍历二叉树

        遍历二叉树之前我们观察下根节点、左子树节点、右子树节点的规律。

        根节点的下标为a[0].左子树上的节点的下标依次为1,3，...2*i+1，右子树上的节点的下标依次为2,4，...2*i+2

// 前序遍历二叉树
void preOrderTraverse(SqBiTree tree, int node_index) {
    if (node_index < MAX_TREE_SIZE && tree[node_index] != '\0') {
        // 访问根节点
        printf("%c ", tree[node_index]);
        // 递归遍历左子树
        preOrderTraverse(tree, 2 * node_index + 1);
        // 递归遍历右子树
        preOrderTraverse(tree, 2 * node_index + 2);
    }
}

4.中序遍历二叉树

// 中序遍历二叉树
void inOrderTraverse(SqBiTree tree, int node_index) {
    if (node_index < MAX_TREE_SIZE && tree[node_index] != '\0') {
        // 递归遍历左子树
        inOrderTraverse(tree, 2 * node_index + 1);
        // 访问根节点
        printf("%c ", tree[node_index]);
        // 递归遍历右子树
        inOrderTraverse(tree, 2 * node_index + 2);
    }
}

5.后序遍历二叉树

// 后序遍历二叉树
void postOrderTraverse(SqBiTree tree, int node_index) {
    if (node_index < MAX_TREE_SIZE && tree[node_index] != '\0') {
        // 递归遍历左子树
        postOrderTraverse(tree, 2 * node_index + 1);
        // 递归遍历右子树
        postOrderTraverse(tree, 2 * node_index + 2);
        // 访问根节点
        printf("%c ", tree[node_index]);
    }
}

6.完整代码

#include <stdio.h>

#define MAX_TREE_SIZE 100

typedef char TElemType;
typedef int Status;

typedef TElemType SqBiTree[MAX_TREE_SIZE];

// 初始化二叉树
Status initSqBiTree(SqBiTree tree) {
    for (int i = 0; i< MAX_TREE_SIZE; i++) {
        tree[i] = '\0';
    }
    // 将二叉树所有元素初始化为空
    return 1; // 初始化成功
}

// 前序遍历二叉树
void preOrderTraverse(SqBiTree tree, int node_index) {
    if (node_index < MAX_TREE_SIZE && tree[node_index] != '\0') {
        // 访问根节点
        printf("%c ", tree[node_index]);
        // 递归遍历左子树
        preOrderTraverse(tree, 2 * node_index + 1);
        // 递归遍历右子树
        preOrderTraverse(tree, 2 * node_index + 2);
    }
}

// 中序遍历二叉树
void inOrderTraverse(SqBiTree tree, int node_index) {
    if (node_index < MAX_TREE_SIZE && tree[node_index] != '\0') {
        // 递归遍历左子树
        inOrderTraverse(tree, 2 * node_index + 1);
        // 访问根节点
        printf("%c ", tree[node_index]);
        // 递归遍历右子树
        inOrderTraverse(tree, 2 * node_index + 2);
    }
}

// 后序遍历二叉树
void postOrderTraverse(SqBiTree tree, int node_index) {
    if (node_index < MAX_TREE_SIZE && tree[node_index] != '\0') {
        // 递归遍历左子树
        postOrderTraverse(tree, 2 * node_index + 1);
        // 递归遍历右子树
        postOrderTraverse(tree, 2 * node_index + 2);
        // 访问根节点
        printf("%c ", tree[node_index]);
    }
}

int main(int argc, const char *argv[]) {
    SqBiTree tree;
    
    // 初始化二叉树
    initSqBiTree(tree);

    // 构造一个简单的二叉树，根节点为'A'，左子树为'B'，右子树为'C'
    tree[0] = 'A';
    tree[1] = 'B';
    tree[2] = 'C';
    tree[3] = 'D';
    tree[4] = 'E';
    tree[5] = '\0';
    tree[6] = '\0';
    // 输出初始化后的二叉树
    printf("前序遍历结果为：");
    preOrderTraverse(tree, 0);
    printf("\n");

    printf("中序遍历结果为：");
    inOrderTraverse(tree, 0);
    printf("\n");

    printf("后序遍历结果为：");
    postOrderTraverse(tree, 0);
    printf("\n");

    return 0;
}


// 后序遍历二叉树
void postOrderTraverse(SqBiTree tree, int node_index) {
    if (node_index < MAX_TREE_SIZE && tree[node_index] != '\0') {
        // 递归遍历左子树
        postOrderTraverse(tree, 2 * node_index + 1);
        // 递归遍历右子树
        postOrderTraverse(tree, 2 * node_index + 2);
        // 访问根节点
        printf("%c ", tree[node_index]);
    }
}

int main(int argc, const char *argv[]) {
    SqBiTree tree;
    
    // 初始化二叉树
    initSqBiTree(tree);

    // 构造一个简单的二叉树，根节点为'A'，左子树为'B'，右子树为'C'
    tree[0] = 'A';
    tree[1] = 'B';
    tree[2] = 'C';
    tree[3] = 'D';
    tree[4] = 'E';
    tree[5] = '\0';
    tree[6] = '\0';
    // 输出初始化后的二叉树
    printf("前序遍历结果为：");
    preOrderTraverse(tree, 0);
    printf("\n");

    printf("中序遍历结果为：");
    inOrderTraverse(tree, 0);
    printf("\n");

    printf("后序遍历结果为：");
    postOrderTraverse(tree, 0);
    printf("\n");

    return 0;
}

        在main函数中，我们构建了一个图2所示的二叉树，控制台打印信息如下：

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

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

相关文章

第五课，输入函数、布尔类型、比较运算和if判断

第五课，输入函数、布尔类型、比较运算和if判断

一&#xff0c;输入函数input() 与输出函数print()相对应的&#xff0c;是输入函数input()&#xff0c;前者是把程序中的数据展示给外界&#xff08;比如电脑屏幕上&#xff09;&#xff0c;而后者是把外界&#xff08;比如键盘&#xff09;的数据输入进程序中 input()函数可…
阅读更多...
秋招算法——背包模型——423采药问题——模板：背包问题

秋招算法——背包模型——423采药问题——模板：背包问题

文章目录 题目描述思路分析实现代码分析总结 题目描述 思路分析 这里明显是使用背包问题&#xff0c;所以这里参考一下背包这个模板题的内容这个是朴素版的模板&#xff0c;没有经过代码的优化 #include <iostream> #include <algorithm>using namespace std;con…
阅读更多...
字符串函数（二）：strlen(求长度)，strstr(查找子串)，strtok(分割)，strerror(打印错误信息)

字符串函数（二）：strlen(求长度)，strstr(查找子串)，strtok(分割)，strerror(打印错误信息)

字符串函数 一.strlen&#xff08;求字符串长度&#xff09;1.函数使用2.模拟实现&#xff08;三种方法&#xff09; 二.strstr&#xff08;字符串查找子串&#xff09;1.函数使用2.模拟实现 三.strtok&#xff08;字符串分割&#xff09;四.strerror&#xff0c;perror&#x…
阅读更多...
24点游戏679

24点游戏679

题目描述&#xff1a; 给定一个长度为4的整数数组 cards 。你有 4 张卡片&#xff0c;每张卡片上都包含一个范围在 [1,9] 的 数字。您应该使用运算符 [, -, *, /] 和括号 ( 和 ) 将这些卡片上的数字排 列成数学表达式&#xff0c;以获得值24。你须遵守以下规则: &#xff08;1&…
阅读更多...
AI大模型日报#0514：OpenAI GPT-4o震撼发布、我是如何赢得GPT-4提示工程大赛冠军的

AI大模型日报#0514：OpenAI GPT-4o震撼发布、我是如何赢得GPT-4提示工程大赛冠军的

导读&#xff1a;欢迎阅读《AI大模型日报》&#xff0c;内容基于Python爬虫和LLM自动生成。目前采用“文心一言”生成了今日要点以及每条资讯的摘要。《AI大模型日报》今日要点&#xff1a;OpenAI在春季新品发布会上推出全能模型GPT-4o及桌面App&#xff0c;颠覆科技界。GPT-4o…
阅读更多...
Pytorch学习-引言

Pytorch学习-引言

Pytorch相关链接 Pytorch官方网站 https://pytorch.org/ Pytorch的Github仓库 https://github.com/pytorch/pytorch Pytorch论坛 https://discuss.pytorch.org/ Pytorch离线下载包链接 https://download.pytorch.org/whl/torch_stable.html Pytorch学习视频推荐链接 http://【…
阅读更多...
C++类与对象基础探秘系列（二）

C++类与对象基础探秘系列（二）

目录 类的6个默认成员函数 构造函数 构造函数的概念 构造函数的特性 析构函数 析构函数的概念 析构函数的特性 拷贝构造函数 拷贝构造函数的概念 拷贝构造函数的特性 赋值运算符重载 运算符重载 赋值运算符重载 const成员 const修饰类的成员函数 取地址及const取地址操作…
阅读更多...
STM32单片机看门狗：独立看门狗和窗口看门狗有什么区别？

STM32单片机看门狗：独立看门狗和窗口看门狗有什么区别？

阅读更多...
C++系统编程篇——Linux初识（系统安装、权限管理，权限设置）

C++系统编程篇——Linux初识（系统安装、权限管理，权限设置）

(1)linux系统的安装 双系统---不推荐虚拟机centos镜像&#xff08;可以使用&#xff09;云服务器/轻量级云服务器&#xff08;强烈推荐&#xff09; ①云服务器&#xff08;用xshell连接&#xff09; ssh root公网IP 然后输入password ①添加用户&#xff1a; addus…
阅读更多...
如何去掉试卷答案,并打印出来

如何去掉试卷答案,并打印出来

实际上&#xff0c;针对试卷答案的问题&#xff0c;一个简单而高效的方法是使用图片编辑软件中的“消除笔”功能。只需将试卷拍摄成照片&#xff0c;然后通过这一功能&#xff0c;就可以轻松擦除答案。虽然这种方法可能需要一些时间和耐心&#xff0c;但它确实为我们提供了一个…
阅读更多...
增程SUV价格即将崩盘？买车一定要再等等！

增程SUV价格即将崩盘？买车一定要再等等！

文 | AUTO芯球 作者 | 雷歌​ 真是“离谱”啊&#xff0c;车圈真是逗比欢乐多&#xff0c; 我这两天看一个博主连续40多小时开车直播&#xff0c;充电口、油箱盖全部封死&#xff0c;全程视频直播没断过&#xff0c; 就为了测试这两天刚上市的星际元ET续航有多远。 另一个…
阅读更多...
深入解析RedisJSON：在Redis中直接处理JSON数据

深入解析RedisJSON：在Redis中直接处理JSON数据

码到三十五 &#xff1a; 个人主页 JSON已经成为现代应用程序之间数据传输的通用格式。然而&#xff0c;传统的关系型数据库在处理JSON数据时可能会遇到性能瓶颈。为了解决这一问题&#xff0c;Redis推出了RedisJSON模块&#xff0c;它允许开发者在Redis数据库中直接存储、查询…
阅读更多...
Flink最全文档

Flink最全文档

Flink架构&#xff1a; 分布式系统Flink&#xff0c;需要有效分配和管理计算资源才能执行流应用程序。它集成了所有常见的集群资源管理器&#xff0c;例如Hadoop Yarn&#xff0c;Apache Mesos&#xff0c;Kubernetes&#xff0c;但是也可以设置作为独立集群甚至库来运行。 分…
阅读更多...
3ds Max与Maya不同之处？两者哪个更适合云渲染？

3ds Max与Maya不同之处？两者哪个更适合云渲染？

3ds Max 和 Maya 都是知名的3D软件&#xff0c;各有其特色。3ds Max 以直观的建模和丰富的插件生态闻名&#xff1b;Maya 则在动画和角色创作方面更为出色。两者都支持云渲染技术&#xff0c;能帮助用户在云端高效完成项目。 一、3ds Max和Maya之间的主要区别&#xff1a; 3ds…
阅读更多...
如何在控制台应用程序里面托管ASP.NET Core WebApi + swashbuckle生成接口文档

如何在控制台应用程序里面托管ASP.NET Core WebApi + swashbuckle生成接口文档

目录 介绍项目结构运行效果新增引用新增文件介绍 本文讲解如何在控制台应用程序里面托管ASP.NET Core WebApi + swashbuckle生成接口文档 本文是上一篇文章的延续，如果你对这部分内容还不了解，建议先读上一篇文章：如何在控制台应用程序里面托管ASP.NET Core网站 项目结构 …
阅读更多...
原子学习笔记3——点亮 LED

原子学习笔记3——点亮 LED

一、应用层操控设备的两种方式 应用层如何操控底层硬件&#xff0c;同样也是通过文件 I/O 的方式来实现&#xff0c;设备文件便是各种硬件设备向应用层提供的一个接口&#xff0c;应用层通过对设备文件的 I/O 操作来操控硬件设备&#xff0c;譬如 LCD 显示屏、串口、按键、摄像…
阅读更多...
MVC 过滤器

MVC 过滤器

MVC 过滤器常用有4种 Action过滤器&#xff08;IActionFilter&#xff09; 》 行为过滤器Result过滤器 &#xff08;IResultFilter&#xff09;》 视图过滤器 或 结果过滤器Exception过滤器&#xff08;IExceptionFilter&#xff09;》 异常过滤器Authorization过滤器&#xf…
阅读更多...
OpenAI 发布了免费的 GPT-4o，国内大模型还有哪些机会？

OpenAI 发布了免费的 GPT-4o，国内大模型还有哪些机会？

大家好&#xff0c;我是程序员X小鹿&#xff0c;前互联网大厂程序员&#xff0c;自由职业2年&#xff0c;也一名 AIGC 爱好者&#xff0c;持续分享更多前沿的「AI 工具」和「AI副业玩法」&#xff0c;欢迎一起交流~ 这是今天在某乎看到一个问题&#xff1a;OpenAI 发完 GPT-4o&…
阅读更多...
涨点神器：即插即用特征融合模块！超低参数，性能依旧SOTA

涨点神器：即插即用特征融合模块！超低参数，性能依旧SOTA

在写论文时&#xff0c;一些通用性模块可以在不同的网络结构中重复使用&#xff0c;这简化了模型设计的过程&#xff0c;帮助我们加快了实验的迭代速度。 比如在视觉任务中&#xff0c;即插即用的特征融合模块可以无缝集成到现有网络中&#xff0c;以灵活、简单的方式提升神经…
阅读更多...
AIGC数字人视频创作平台，赋能企业常态化制作数字内容营销

AIGC数字人视频创作平台，赋能企业常态化制作数字内容营销

随着数字人技术不断发展&#xff0c;AIGC、元宇宙等相关产业迅速发展&#xff0c;企业通过3D虚拟数字人定制&#xff0c;打造出专属的数字人作为企业与用户沟通的新桥梁。 作为3D、AI数字人技术服务商及方案提供商&#xff0c;广州虚拟动力一直致力于为各领域企业通过3D虚拟数字…
阅读更多...
最新文章

Copyright @ 2022~2023