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

目录

前言

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

1.数组

2.结构体数组

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;
}

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/610185.html

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

相关文章

百倍潜力股Aleo即将上线，布局正当时！牛市来时，你得有币！

百倍潜力股Aleo即将上线，布局正当时！牛市来时，你得有币！

前言 在加密货币市场&#xff0c;2024年被众多市场专家预测为迎来新一轮牛市的关键年份。这一预测背后&#xff0c;潜藏着多种可能推动牛市的因素。其中&#xff0c;下一次比特币&#xff08;BTC&#xff09;的减半事件&#xff0c;以及2024年 BTC 现货ETF的推出&#xff0c;都…
阅读更多...
二叉树-堆

二叉树-堆

树 在数据库中&#xff0c;树是一种数据结构&#xff0c;用于组织和存储数据&#xff0c;使得可以高效地进行插入、删除和查找操作。它通常用于表示层次关系或者有序集合。 基本概念 节点&#xff1a;树结构中的每个元素都称为节点。 根节点&#xff1a;树的最顶端节点。 子…
阅读更多...
智能奶柜：健康生活新风尚

智能奶柜：健康生活新风尚

智能奶柜&#xff1a;健康生活新风尚 在快节奏的都市生活中&#xff0c;健康与便利成为了现代人的双重追求。而在这两者交汇之处&#xff0c;智能奶柜应运而生&#xff0c;它不仅是科技与生活的完美融合&#xff0c;更是日常营养补给的智慧之选。 清晨的第一缕温暖 —— 新鲜…
阅读更多...
《应用现代化技术能力成熟度评估模型》介绍

《应用现代化技术能力成熟度评估模型》介绍

在中国软件行业协会、应用现代化产业联盟以及中国电子技术标准化研究院的指导下&#xff0c;产业多家企业共同支持和参与下&#xff0c;完成的《应用现代化技术能力成熟度评估模型》标准。该标准从应用敏捷、稳定可靠、安全可信、业务智能、成本优化五大维度及22个能力项来评估…
阅读更多...
【Linux系统编程】第十四弹---进度条

【Linux系统编程】第十四弹---进度条

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】【C详解】【Linux系统编程】 目录 1、回车和换行 2、观察回车换行现象 3、缓冲区 4、usleep和fflush函数 5、简单倒计时 6、进度条 6.1、版本一 6.2、版本…
阅读更多...
基于Python的数据分组技术：将数据按照1, 2, 3规则分为三个列表

基于Python的数据分组技术：将数据按照1, 2, 3规则分为三个列表

目录 一、引言 二、数据分组原理与意义 三、案例分析 四、代码实现与解释 五、对新手友好的解释 六、技术细节与扩展 七、实际应用场景 八、总结 一、引言 在数据处理和分析的广阔领域中&#xff0c;数据分组是一项基础且重要的任务。数据分组通常指的是将数据集中的元…
阅读更多...
最新版在线客服系统源码

最新版在线客服系统源码

源码介绍 首发最新在线客服系统源码&#xff0c;优化更好并且重构源码布局UI 性能不吃cpu并发快,普通1H2G都能带动最新版只要是服务器都能带动 搭建即可使用,操作简单,易懂 修复了老版本bug 内附有搭建教程 gofly.v1kf.com 运行环境 Nginx 1.20 MySQL 5.7 演示截图
阅读更多...
双筒水封式防暴器有诚信才会被信赖

双筒水封式防暴器有诚信才会被信赖

选择一款满意的产品&#xff0c;始于需求&#xff0c;终于品质&#xff0c;有品质才会热爱&#xff0c;有诚信才会被信赖 一、用途介绍&#xff1a; STFB型双筒水封式防爆器属于双罐结构的水封式防爆器&#xff0c;安装在抽放瓦斯泵吸气侧和排气端的管路上靠防爆器底部的水封保…
阅读更多...
使用Docker安装Nginx

使用Docker安装Nginx

一、Nginx介绍 Nginx 是一款高性能的开源 Web 服务器和反向代理服务器&#xff0c;具有高效能、高稳定性、低资源消耗等优点。可以处理大量并发请求&#xff0c;支持多种协议&#xff0c;还能实现负载均衡、缓存等功能&#xff0c;在互联网应用中被广泛使用。在Nginx中&#xf…
阅读更多...
ros 学习记录（二）URDF小车运动控制

ros 学习记录（二）URDF小车运动控制

URDF小车运动控制 准备工作创建 robot_xacro.launch 接上文&#xff0c;想用键盘控制小车在Gazebo中移动。 准备工作 名称版本ROSNoeticGazebo11.11.0 创建 robot_xacro.launch 通过运行这个launch文件&#xff0c;可以启动Gazebo仿真环境&#xff0c;并在仿真环境中加载和…
阅读更多...
Redis实现延迟队列（为订单超时关闭提供更多的解决方案）

Redis实现延迟队列（为订单超时关闭提供更多的解决方案）

电商场景中的问题向来很受面试官的青睐&#xff0c;因为业务场景大家都相对更熟悉&#xff0c;相关的问题也很有深度&#xff0c;也有代表性&#xff0c;能更方便地考察候选人的技术水平。 比如商品购买下单支付的流程&#xff0c;在买家购买商品后会先生成订单&#xff0c;之后…
阅读更多...
Vue开发中Element UI/Plus使用指南：常见问题（如Missing required prop: “value“）及中文全局组件配置解决方案

Vue开发中Element UI/Plus使用指南：常见问题（如Missing required prop: “value“）及中文全局组件配置解决方案

文章目录 一、vue中使用el-table的typeindex有时不显示序号Table 表格显示索引自定义索引报错信息解决方案 二、vue中Missing required prop: “value” 报错报错原因解决方案 三、el-table的索引值index在翻页的时候可以连续显示方法一方法二 四、vue3中Element Plus全局组件配…
阅读更多...
微信小程序流量主如何自定义广告组件后台控制广告显示方式附源码[收藏]

微信小程序流量主如何自定义广告组件后台控制广告显示方式附源码[收藏]

最近开发了一个微信小程序&#xff0c;开通了流量主&#xff0c;引用广告显示。本教程干货满满&#xff0c;附上代码&#xff0c;建议**【收藏点赞】** 微信小程序广告有以下几种&#xff1a;Banner广告、激励广告、插屏广告、视频广告、视频贴片广告、封面广告。 为了增加广告…
阅读更多...
数字工厂管理系统如何助力企业数据采集与分析

数字工厂管理系统如何助力企业数据采集与分析

随着科技的不断进步&#xff0c;数字化已成为企业发展的重要趋势。在制造业领域&#xff0c;数字工厂管理系统的应用日益广泛&#xff0c;它不仅提升了生产效率&#xff0c;更在数据采集与分析方面发挥着举足轻重的作用。本文旨在探讨数字工厂管理系统如何助力企业数据采集与分…
阅读更多...
Java数组（如果想知道Java中有关数组的知识点，那么只看这一篇就足够了！）

Java数组（如果想知道Java中有关数组的知识点，那么只看这一篇就足够了！）

前言&#xff1a;数组对于每一门编程语言来说都是重要的数据结构之一&#xff0c;当然不同语言对数组的实现及处理也不尽相同,Java 语言中提供的数组是用来存储固定大小的同类型元素。 ✨✨✨这里是秋刀鱼不做梦的BLOG ✨✨✨想要了解更多内容可以访问我的主页秋刀鱼不做梦-CSD…
阅读更多...
Kafka从0到消费者开发

Kafka从0到消费者开发

安装ZK Index of /zookeeper/zookeeper-3.9.2 下载安装包 一定要下载-bin的&#xff0c;不带bin的是源码&#xff0c;没有编译的&#xff0c;无法执行。-bin的才可以执行。 解压 tar -zxvf apache-zookeeper-3.9.2-bin.tar.gz 备份配置 cp zoo_sample.cfg zoo_sample.cfg-b…
阅读更多...
Chronos：学习时间序列的大语言模型（论文解读）

Chronos：学习时间序列的大语言模型（论文解读）

前言 《Chronos: Learning the Language of Time Series》原文地址GitHub项目地址Some-Paper-CN。本项目是译者在学习长时间序列预测、CV、NLP和机器学习过程中精读的一些论文&#xff0c;并对其进行了中文翻译。还有部分最佳示例教程。如果有帮助到大家&#xff0c;请帮忙点亮…
阅读更多...
RAG技术简介

RAG技术简介

相关文档&#xff1a; 论文链接&#xff1a; https://arxiv.org/abs/2005.11401 课程链接&#xff1a; Tutorial/huixiangdou at camp2 InternLM/Tutorial GitHub 视频链接&#xff1a; 茴香豆&#xff1a;搭建你的 RAG 智能助理_哔哩哔哩_bilibili RAG是一种在LLM中广泛使…
阅读更多...
echarts指标盘属性概括

echarts指标盘属性概括

echarts指标盘属性概括 代码 有模拟数据可以直接使用const options {animation: true,title: {top: "35%",left: "center",// text: "单元测试覆盖度", // 主标题itemGap: 15,textStyle: {// 主标题样式color: "#666666",fontSize:…
阅读更多...
Spring MVC分页示例

Spring MVC分页示例

Spring MVC分页示例 分页用于在不同部分显示大量记录。在这种情况下&#xff0c;我们将在一页中显示10、20或50条记录。对于其余记录&#xff0c;我们提供链接。 我们可以在Spring MVC中简单地创建分页示例。在此分页示例中&#xff0c;我们使用MySQL数据库来获取记录。 创建…
阅读更多...
最新文章

Copyright @ 2022~2023