数据结构第十四天（树的存储/双亲表示法）

前言

概述

接口：

源码：

测试函数：

运行结果：

往期精彩内容

前言

孩子，一定要记得你的父母啊！！！

哈哈，今天开始学习树结构中的双亲表示法，让孩子记得归家的路，记得自己的父母是谁😉😉😉

概述

树的双亲表示法是一种常用的树的存储结构，它通过使用一个数组来表示树的节点，并且每个节点都包含了其父节点的索引信息。

在双亲表示法中，树的每个节点都包含以下两个信息：

节点的数据域：用来存储节点的数据。
父节点索引：用来存储该节点的父节点在数组中的索引。

每一个节点我们可以这样表示：

其中 data 是数据域，存储结点的数据信息。而 parent 是指针域，存储该结点的双亲在数组中的下标。

通过这种方式，我们可以方便地找到一个节点的父节点，并且能够实现树的遍历和操作。

使用双亲表示法可以有效地存储树的结构，并且可以方便地进行遍历和操作。但双亲表示法的缺点是，它不太适合表示具有大量节点的树，因为节点之间的关系需要通过数组来表示，可能会浪费一定的空间。

接口：

void addNode(char* data, char* parent);
void getParent(char* dest, char* child);
bool bTrueIfEmptyTree();
bool bTrueIfFullFilledTree();

源码：

#include<string.h>
#include<stdio.h>
#include <malloc.h>
class TREE{
private:struct PARENTSTRUCT{char data[15];struct PARENTSTRUCT* parent;};struct  PARENTSTRUCT* index[15];unsigned int currentSite = 0;struct  PARENTSTRUCT* findParent(char* child);	public:void addNode(char* data, char* parent);
void getParent(char* dest, char* child);
bool bTrueIfEmptyTree();
bool bTrueIfFullFilledTree();
};
struct  TREE::PARENTSTRUCT* TREE::findParent(char* child)
{for (int i = 0; i < currentSite; ++i){if (strcmp(child, index[i]->data) == 0){return index[i]->parent;}}}
void TREE::addNode(char* data, char* parent)
{index[currentSite] = (PARENTSTRUCT*)malloc(sizeof(PARENTSTRUCT));strcpy(index[currentSite]->data, data);if (parent == nullptr){index[currentSite]->parent = nullptr;}else{for (int i = 0; i < currentSite; ++i){if (strcmp(parent, index[i]->data) == 0){index[currentSite]->parent = index[i];}}}currentSite++;return;
}
bool TREE::bTrueIfFullFilledTree()
{if (currentSite == 15){return true;}else{return false;}
}
void TREE::getParent(char* dest, char* child)
{PARENTSTRUCT* ptr = findParent(child);if (ptr != nullptr){strcpy(dest, ptr->data);}else{strcpy(dest, "抱歉，此为根");}return;
}

由下图数据来建一棵树，由此进行测试

测试函数：

#include<stdio.h>
#include<iostream>
using namespace std;
#include"TREE.h"//上面提到的源码函数头文件
#include<windows.h>
int main()
{TREE tree;tree.addNode("A", nullptr);tree.addNode("B","A");tree.addNode("C", "A");tree.addNode("D", "B");tree.addNode("G", "D");tree.addNode("H", "D");tree.addNode("I", "D");tree.addNode("E", "C");tree.addNode("F", "C");tree.addNode("J", "E");char buff[40];tree.getParent(buff, "H");cout << "输出H的父母：" << buff << endl;tree.getParent(buff, "J");cout << "输出J的父母：" << buff << endl;system("pause");return 0;
}