数据结构第十五天（树的存储/孩子表示法）
目录
前言
概述
接口
源码
测试函数
运行结果
往期精彩内容
前言
最近在知乎上看到的一个问题，
也许，短暂的离别，只为更好的相遇！
2024，友友们，龙年快乐，新的一年，祝愿码上升薪，一头黑发无烦恼。
概述
树的存储孩子表示法是一种常见的树的存储方式，也被称为多重链表表示法。这种方式是通过记录每个节点的所有子节点来实现的。
具体地，对于每个节点，它的所有子节点都被保存在一个链表中，这个链表中的每个元素都指向该节点的一个子节点。如果节点没有子节点，则该链表为空。同时，该节点还需要保存它的父节点的指针，以便能够在需要时回溯到父节点。
这种方式的优点在于可以快速访问任意节点的子节点，因为每个节点的子节点都被直接存储在链表中，不需要遍历整个树来查找。同时，也可以方便地插入和删除节点，只需要修改相应的链表即可。
然而，这种方式也有一些缺点。首先，它需要额外的空间来保存每个节点的子节点链表和父节点指针，空间占用较大。其次，由于每个节点的子节点链表是无序的，因此在查找特定子节点时可能需要遍历整个链表才能找到目标节点，效率较低。
总而言之，树的存储孩子表示法是一种简单且易于实现的树结构存储方式，它适用于小规模的树和需要快速访问子节点的场景。
接口
void addNode(char* data);void addChild(char* parent, char* child);void getChild(char* parent);源码
#include <malloc.h>
#include<string.h>
#include<iostream>
using namespace std;
class TREECHILD
{
private:struct DATA{char data[15];struct DATA* next;struct DATA* child;};struct DATA* head = nullptr, *tail = nullptr;
private:struct DATA* getPtrOfData(char* data);
public:TREECHILD(){head = tail = (struct DATA*)malloc(sizeof(struct DATA));}void addNode(char* data);void addChild(char* parent, char* child);void getChild(char* parent);
};
struct TREECHILD::DATA* TREECHILD::getPtrOfData(char* data)
{struct DATA* ptr = head;while (ptr != nullptr){if (strcmp(data, ptr->data) == 0){return ptr;}ptr = ptr->next;}return nullptr;
}
void TREECHILD::getChild(char* parent)
{struct DATA* ptr = getPtrOfData(parent);ptr = ptr->child;while (ptr != nullptr){cout << ptr->data << endl;ptr = ptr->child;}return ;
}
void TREECHILD::addNode(char* data)
{strcpy(tail->data, data);tail->next = (struct DATA*)malloc(sizeof(struct DATA));tail->child = nullptr;tail = tail->next;tail->next=nullptr;return;
}
void TREECHILD::addChild(char* parent, char* child)
{struct DATA* parentPtr = getPtrOfData(parent);if (parentPtr->child == nullptr){parentPtr->child = (struct DATA*)malloc(sizeof(struct DATA));strcpy(parentPtr->child->data, child);parentPtr->child->child = nullptr;parentPtr->child->next = nullptr;}else{struct DATA* ptr = nullptr;ptr = parentPtr->child;parentPtr->child = (struct DATA*)malloc(sizeof(struct DATA));strcpy(parentPtr->child->data, child);parentPtr->child->child = ptr;parentPtr->child->next = nullptr;}return;
}以下为测试用例：
测试函数
#include<stdio.h>
#include<iostream>
using namespace std;
#include"TREE(child express).h"//（树存储孩子表示法头文件）
#include<windows.h>
int main()
{
//树表示法（孩子表示法）测试TREECHILD treeChild;//创建树的节点treeChild.addNode("A");treeChild.addNode("B");treeChild.addNode("C");treeChild.addNode("D");treeChild.addNode("E");treeChild.addNode("F");treeChild.addNode("G");treeChild.addNode("H");treeChild.addNode("I");treeChild.addNode("J");//添加孩子链表treeChild.addChild("A", "B");treeChild.addChild("A", "C");treeChild.addChild("B", "D");treeChild.addChild("D", "G");treeChild.addChild("D", "H");treeChild.addChild("D", "I");//输出孩子cout << "输出A的孩子：" << endl;treeChild.getChild("A");cout << "输出B的孩子：" << endl;treeChild.getChild("B");cout << "输出D的孩子：" << endl;treeChild.getChild("D");system("pause");return 0;
}运行结果
