C++的数据结构(五):树和存储结构及示例

news/2024/6/19 5:41:23

        在计算机科学中,树是一种抽象数据类型(ADT)或是实现这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。这种数据结构以一系列连接的节点来形成树形结构。在C++中,树的概念和存储结构是实现各种复杂算法和数据操作的基础。   

     树是由节点和边组成的图,其中每个节点有零个或多个子节点,但只有一个父节点(除了根节点,它没有父节点)。树的顶部节点称为根节点。如果一个节点没有子节点,那么它被称为叶子节点。除了根节点和叶子节点之外的其他节点称为内部节点。由树的根节点和若干棵子树所构成的树称为森林。如下图所示。

         树的术语:    

        (1)路径:在两个节点之间,一系列的边和节点的组合。路径的长度是组成路径的边数。

        (2)深度:一个节点的深度是指从根节点到该节点的最长路径上的边数。根节点的深度为0。

        (3)层次:树的层次从根开始定义,根为第一层,根的子节点为第二层,以此类推。

        (4)高度:树的高度是从叶子节点开始自底向上逐层累加的路径上边的数量。根节点的高度就是树的高度。

        在C++中,树的存储结构主要有两种:顺序存储和链式存储。不同的存储结构对应着不同的表示方法,如孩子表示法、双亲表示法、孩子兄弟表示法等。

        1. 顺序存储:顺序存储通常用于完全二叉树。在完全二叉树中,除了最后一层外,其他层的节点数是满的,并且最后一层的节点都靠左排列。这种特性使得完全二叉树可以使用数组进行顺序存储,其中每个节点的索引与其在树中的位置相关。

        示例:创建一棵简单的完全二叉树,代码如下。

#include <iostream>
#include <vector>using namespace std;class TreeNode {
public:int value;TreeNode* left;TreeNode* right;TreeNode(int x) : value(x), left(nullptr), right(nullptr) {}
};class BinaryTree {
private:vector<TreeNode*> nodes;
public:// 初始化树的根节点void initRoot(int value) {nodes.push_back(new TreeNode(value));}// 添加子节点void addChild(int parentIndex, int leftChildValue, int rightChildValue) {int nextEmptyIndex = nodes.size();if (leftChildValue != -1) {nodes.push_back(new TreeNode(leftChildValue));nodes[parentIndex]->left = nodes[nextEmptyIndex];}if (rightChildValue != -1) {nodes.push_back(new TreeNode(rightChildValue));nodes[parentIndex]->right = nodes[nextEmptyIndex + (leftChildValue != -1)];}}// 示例:创建一棵简单的完全二叉树void createExampleTree() {initRoot(1);addChild(0, 2, 3);addChild(1, 4, 5);addChild(2, 6, -1);addChild(3, 7, 8);}// 其他操作,如遍历、查找等...
};

        链式存储:链式存储通过节点和指针来表示树中的关系。每个节点包含数据域和指向其子节点的指针域。链式存储方式更加灵活,适用于各种类型的树。

        示例一:使用孩子表示法创建树,代码如下。

class TreeNode {
public:int value;vector<TreeNode*> children;TreeNode(int x) : value(x) {}
};// 使用孩子表示法创建树
TreeNode* createTree() {TreeNode* root = new TreeNode(1);TreeNode* node2 = new TreeNode(2);TreeNode* node3 = new TreeNode(3);TreeNode* node4 = new TreeNode(4);TreeNode* node5 = new TreeNode(5);root->children.push_back(node2);root->children.push_back(node3);node2->children.push_back(node4);node2->children.push_back(node5);return root;
}

        上述代码展示了如何使用孩子表示法来创建一个树,其中每个节点都有一个指向其子节点的指针列表。这种方式可以很直观地表示一个节点的所有子节点,但是在查找父节点时不够高效,因为父节点的信息并未存储在当前节点中。

        在双亲表示法中,每个节点不仅包含数据域和指向其子节点的指针,还包含一个指向其父节点的指针。这使得我们可以方便地访问一个节点的父节点,但可能需要额外的空间来存储父节点的指针。

        示例二:使用双亲表示法创建树,代码如下:

class TreeNode {
public:int value;TreeNode* parent; // 指向父节点的指针vector<TreeNode*> children; // 子节点列表TreeNode(int x) : value(x), parent(nullptr) {}
};// 使用双亲表示法创建树
void createTreeWithParent(TreeNode*& root) {root = new TreeNode(1); // 根节点的父节点为nullTreeNode* node2 = new TreeNode(2);TreeNode* node3 = new TreeNode(3);TreeNode* node4 = new TreeNode(4);TreeNode* node5 = new TreeNode(5);node2->parent = root;node3->parent = root;node4->parent = node2;node5->parent = node2;root->children.push_back(node2);root->children.push_back(node3);node2->children.push_back(node4);node2->children.push_back(node5);
}

        在双亲表示法中,我们可以沿着父节点的指针向上遍历树,直到找到根节点或者到达一个父节点为空的节点。这种表示法在需要频繁进行父子节点关系查询时比较有用。

        孩子兄弟表示法是一种结合了孩子表示法和双亲表示法的思想的方法。在这种表示法中,每个节点包含指向其第一个孩子节点的指针和指向其下一个兄弟节点的指针。这种表示法对于二叉树非常自然,并且可以很方便地表示任何类型的树。
        示例三: 使用孩子兄弟表示法创建树,代码如下:

class TreeNode {
public:int value;TreeNode* firstChild; // 指向第一个孩子节点TreeNode* nextSibling; // 指向下一个兄弟节点TreeNode(int x) : value(x), firstChild(nullptr), nextSibling(nullptr) {}
};// 使用孩子兄弟表示法创建树
void createTreeWithChildSibling(TreeNode*& root) {root = new TreeNode(1);TreeNode* node2 = new TreeNode(2);TreeNode* node3 = new TreeNode(3);TreeNode* node4 = new TreeNode(4);TreeNode* node5 = new TreeNode(5);root->firstChild = node2;node2->nextSibling = node3;node3->firstChild = node4;node3->nextSibling = node5;
}

        在这种表示法中,通过firstChild可以访问到该节点的所有子节点,而通过nextSibling可以遍历该节点的所有兄弟节点。这种方法特别适合处理那些子节点之间没有顺序要求的树结构。

        每种存储结构都有其适用的场景和优缺点,例如顺序存储适合表示完全二叉树,而链式存储则更加灵活,能够表示任意结构的树。在实际应用中,需要根据具体需求和树的特点来选择适当的存储结构。


https://dhexx.cn/news/show-5353027.html

相关文章

D60SB60-ASEMI电源设备首选整流桥D60SB60

编辑&#xff1a;ll D60SB60-ASEMI电源设备首选整流桥D60SB60 型号&#xff1a;D60SB60 品牌&#xff1a;ASEMI 封装&#xff1a;DSB-4 最大重复峰值反向电压&#xff1a;600V 最大正向平均整流电流(Vdss)&#xff1a;60A 功率(Pd)&#xff1a;大功率 芯片个数&#xf…

python创建新环境并安装pytorch

python创建新环境并安装pytorch 一、创建新环境1、准备工作2、创建虚拟环境并命名3、激活虚拟环境 二、安装pytorch1、pytorch官网2、选择与你的系统相对应的版本3、安装成功 一、创建新环境 1、准备工作 本次创建的环境是在anaconda环境下&#xff0c;否则需要在纯净环境下创…

体积渲染技术在AI去衣应用中的创新探索

引言&#xff1a; 随着计算机视觉和人工智能技术的飞速发展&#xff0c;AI去衣技术逐渐走进公众视野。这一技术以其独特的应用前景和技术挑战引起了广泛的关注。在实现衣物去除的同时保持图像质量的关键技术之一&#xff0c;便是体积渲染技术。本文将深入探讨体积渲染技术在AI去…

如何在mac电脑安装 Android SDK

1、在 Mac 电脑上安装 Android SDK 的步骤如下: 前往 Android 开发者网站下载 Android SDK 打开 Android 开发者网站 (https://developer.android.com/studio) 打开下载好的 Android SDK 安装包 2、解压 Android SDK 安装包 打开下载好的 Android SDK 安装包 将 android-…

centOS忘记密码的处理办法

1、开机后在出现内核选项时&#xff0c;按 e&#xff1b; 2、在Linux 开头的这行&#xff0c;输入 rd.break 如下图&#xff1b; 3、然后&#xff0c;执行&#xff1a;CtrlX&#xff1b; 4、进入之后是 switch_root:/#输入 mount -o rw,remount /sysroot 以读写方式重新挂载 /s…

visual studio snippet常用注释片段

Visual Studio 2022 添加自定义代码片段_vs2022 代码片段-CSDN博客 dclass.snippet: <?xml version"1.0" encoding"utf-8"?> <CodeSnippets xmlns"http://schemas.microsoft.com/VisualStudio/2005/CodeSnippet"> …

OpenAI GPT-4o:开启人工智能交互新纪元

引言 在人工智能领域&#xff0c;OpenAI一直是创新的代名词。2024年5月14日&#xff0c;OpenAI再次以GPT-4o模型震撼了科技界&#xff0c;这款全新的旗舰生成模型不仅免费向公众开放&#xff0c;更以其革命性的多模态交互能力&#xff0c;引领我们进入了一个全新的科幻时代。 …

【Linux:进程概念】

目录 了解冯诺依曼思想&#xff1a; 操作系统如何管理软硬件资源&#xff1f; 进程与程序的区别 了解冯诺依曼思想&#xff1a; 1.所有的数据采用二进制的存储 2.数据存储在内存中 CPU处理器只做俩种运算&#xff1a;逻辑&&算数运算 操作系统的组成&#xff1f;…

电影网站|基于SSM+vue的电影网站系统(源码+数据库+文档)

电影网站 目录 基于SSMvue的电影网站系统 一、前言 二、系统设计 三、系统功能设计 1 系统功能模块 2 管理员功能模块 四、数据库设计 五、核心代码 六、论文参考 七、最新计算机毕设选题推荐 八、源码获取&#xff1a; 博主介绍&#xff1a;✌️大厂码农|毕设布道…

Linux中的nproc命令

2024年5月15日&#xff0c;周三上午 nproc 是一个在类 Unix 系统中使用的命令行实用程序&#xff0c;用于返回系统上可用的处理器核心数量。这个数字通常比物理 CPU 核心的数量要少&#xff0c;因为它可能排除了超线程核心或热插拔核心。nproc 命令读取 /proc/cpuinfo 文件来获…