数据结构与算法学习笔记六-二叉树的顺序存储表示法和实现(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 100typedef 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 100typedef 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所示的二叉树，控制台打印信息如下：

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

【React】React-redux多组件间的状态传递

【React】React-redux多组件间的状态传递

效果&#xff08;部分完整代码在最底部&#xff09;&#xff1a; 编写 Person 组件 上面的 Count 组件&#xff0c;已经在前面几篇写过了&#xff0c;也可以直接翻到最底部看 首先我们需要在 containers 文件夹下编写 Person 组件的容器组件 首先我们需要编写 index.jsx 文件…
阅读更多...
基于VOLOPV2的自动驾驶环境感知系统

基于VOLOPV2的自动驾驶环境感知系统

基于VOLOPV2的自动驾驶环境感知系统是一个复杂的系统&#xff0c;它主要负责实时检测并识别周围环境中的各种物体和信息&#xff0c;为自动驾驶车辆提供必要的感知数据。以下是对该系统的一个简要介绍&#xff1a; 环境感知是自动驾驶系统中的一个关键部分&#xff0c;它依赖于…
阅读更多...
AI代理和AgentOps生态系统的剖析

AI代理和AgentOps生态系统的剖析

1、AI代理的构成&#xff1a;AI代理能够根据用户的一般性指令自行做出决策和采取行动。 主要包含四个部分&#xff1a; &#xff08;1&#xff09;大模型&#xff08;LLM&#xff09; &#xff08;2&#xff09;工具&#xff1a;如网络搜索、代码执行等 &#xff08;3&#x…
阅读更多...
C++学习第二十九课：C++ 输入输出流详解：从基础到高级应用

C++学习第二十九课：C++ 输入输出流详解：从基础到高级应用

在 C 中&#xff0c;流&#xff08;stream&#xff09;是一种用于实现输入输出操作的抽象概念。流可以看作是字节的流动&#xff0c;这些字节可以从一个地方流向另一个地方&#xff0c;例如从键盘输入到程序中&#xff0c;或者从程序输出到屏幕。C 提供了一套完整的流库来处理各…
阅读更多...
区块链（打新）如何被割韭菜

区块链（打新）如何被割韭菜

看上去&#xff0c;像我只要去每个都买一遍新发行的代币&#xff0c;一定可以成功的 但是好像没有想象中这么简单&#xff0c;因为这些山寨币&#xff0c;庄家可以自己控盘的&#xff0c;看上去好像有跌宕起伏的买卖&#xff0c;但是一单掀桌子&#xff0c;庄家他自己都不玩了…
阅读更多...
mac 讨厌百度网盘怎么办

mac 讨厌百度网盘怎么办

一、别拦我 首先请允许我泄个愤&#xff0c;tmd百度网盘下个1g的文件下载速度竟然超不过200k&#xff0c;只要不放在所有已打开软件的最前面&#xff0c;它就给你降到10k以内&#xff0c;关键是你慢就慢了&#xff0c;我也不是很着急&#xff0c;关键是你日常下载失败并且总是…
阅读更多...
Ubuntu18.04--虚拟机配置Samba并从Windows登录

Ubuntu18.04--虚拟机配置Samba并从Windows登录

前言&#xff1a; 本文记录我自己在Windows上安装 Virtualbox &#xff0c;并在Virtualbox中安装 Ubuntu-18.04 虚拟机&#xff0c;在Ubuntu-18.04虚拟机里安装配置Smaba服务器&#xff0c;从 Windows 宿主系统上访问虚拟机共享samba目录的配置命令。 引用: N/A 正文 虚拟…
阅读更多...
鸿蒙OpenHarmony开发板解析：【特性配置规则】

鸿蒙OpenHarmony开发板解析：【特性配置规则】

特性 特性配置规则 下面介绍feature的声明、定义以及使用方法。 feature的声明 开发前请熟悉鸿蒙开发指导文档&#xff1a;gitee.com/li-shizhen-skin/harmony-os/blob/master/README.md点击或者复制转到。 在部件的bundle.json文件中通过feature_list来声明部件的feature列…
阅读更多...
【栈】Leetcode 验证栈序列

【栈】Leetcode 验证栈序列

题目讲解 946. 验证栈序列 算法讲解 在这里就只需要模拟一下这个栈的出栈顺序即可&#xff1a;使用一个stack&#xff0c;每次让pushed里面的元素入栈&#xff0c;如果当前栈顶的元素等于poped容器中的当前元素&#xff0c;因此就需要让栈顶元素出栈&#xff0c;poped的遍历…
阅读更多...
W801学习笔记二十二：英语背单词学习应用——下

W801学习笔记二十二：英语背单词学习应用——下

续上篇&#xff1a; W801学习笔记二十一&#xff1a;英语背单词学习应用——上 五、处理用户交互 由于英语也是采用了和唐诗一样的《三分钟限时挑战》《五十题竞速挑战》《零错误闯关挑战》&#xff0c;所以用户交互的逻辑和唐诗是一样的。所以&#xff0c;我们抽一个基类&a…
阅读更多...
Java入门基础学习笔记7——Intellij IDEA开发工具概述、安装

Java入门基础学习笔记7——Intellij IDEA开发工具概述、安装

之前的开发工具存在一些问题&#xff1a; 文本编辑工具&#xff1a;记事本、NotePad、EditPlus、Sublime...编写代码的时候没有错误提醒、没有智能代码提示、需要自己进行编译、执行、功能不够强大。 集成开发环境&#xff08;IDE&#xff1a;Integrated Development Environm…
阅读更多...
SQL注入（sqli-labs第一关）

SQL注入（sqli-labs第一关）

sqli-labs第一关 方法一&#xff1a;手工注入 来到第一关&#xff0c;图上说我们需要一个数字的参数 于是我们先手工注入?id1 and 11 跟?id1 and 12发现页面没有报错 每张截图上面页面中有select查询语句&#xff0c;这是我在第一关的源码中加上了echo "$sql ";…
阅读更多...
探索无界知识：用 ChatGPT 的原理学习任何事物！

探索无界知识：用 ChatGPT 的原理学习任何事物！

为避免文章重复&#xff0c;您的文本已通过更改句式、用词以及句子结构进行了修改。现在的文本应该能更好地满足去重的需求&#xff1a; 从ChatGPT原理出发&#xff0c;我们探讨GPT如何启发人类学习和构建个人知识体系。 1. 明确学习目标 机器学习必须依靠目标函数。同样&…
阅读更多...
408算法题专项-2019年

408算法题专项-2019年

题目&#xff1a; 分析&#xff1a;要求空间复杂度为O&#xff08;1&#xff09;&#xff0c;我们可以逆向假设可以开空间&#xff0c;得出一种思路&#xff0c;然后对这种思路优化空间即可得到O&#xff08;1&#xff09; 思路一&#xff1a;假设开空间 思考&#xff1a;再开…
阅读更多...
fswatch工具：跟踪Linux中的文件和目录更改

fswatch工具：跟踪Linux中的文件和目录更改

fswatch是一个跨平台的文件更改监视器&#xff0c;当指定文件或目录的内容被更改或修改时&#xff0c;它会收到通知警报。 fswatch在不同的操作系统上执行多种类型的监视器&#xff0c;例如&#xff1a; 基于 Apple OS X 的文件系统事件 API 构建的监视器。基于kqueue的监视器…
阅读更多...
05、Kafka 操作命令

05、Kafka 操作命令

05、Kafka 操作命令 1、主题命令 &#xff08;1&#xff09;创建主题 kafka-topics.sh --create --bootstrap-server 192.168.135.132:9092,192.168.135.133:9092,192.168.135.134:9092 --topic test1 --partitions 4 --replication-factor 3–bootstrap-server&#xff1a;…
阅读更多...
互动科技如何强化法治教育基地体验？

互动科技如何强化法治教育基地体验？

近年来&#xff0c;多媒体互动技术正日益融入我们生活的各个角落&#xff0c;法治教育领域亦不例外。步入法治教育基地&#xff0c;我们不难发现&#xff0c;众多创新的多媒体互动装置如雨后春笋般涌现&#xff0c;这些装置凭借前沿的科技手段&#xff0c;不仅极大地丰富了法制…
阅读更多...
Capl中的运算符

Capl中的运算符

Capl中的运算符类似于C语言。由于capl中没有指针的概念&#xff0c;所以没有指针取值&#xff0c;取地址等运算符。 Capl中的运算符优先级同C语言一样&#xff0c;同样小括号可以 提升优先级。 1.算数运算符 整数类型之间的数据进行除法运算&#xff0c;结果一定是整数。如果…
阅读更多...
双目相机标定流程(MATLAB)

双目相机标定流程(MATLAB)

一&#xff1a;经典标定方法 1.1OPENCV 1.2ROS ROS进行双目视觉标定可以得到左右两个相机的相机矩阵和畸变系数&#xff0c;如果是单目标定&#xff0c;用ROS会非常方便。 3.MATLAB标定&#xff08;双目标定&#xff09; MATLAB用来双目标定会非常方便&#xff0c;主要是为…
阅读更多...
SparkSQL编程入口和模型与SparkSQL基本编程

SparkSQL编程入口和模型与SparkSQL基本编程

SparkSQL编程入口和模型 SparkSQL编程模型 主要通过两种方式操作SparkSQL&#xff0c;一种就是SQL&#xff0c;另一种为DataFrame和Dataset。 1)SQL&#xff1a;SQL不用多说&#xff0c;就和Hive操作一样&#xff0c;但是需要清楚一点的是&#xff0c;SQL操作的是表&#xf…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023