经验总结

  1. 首页 > 生活 > >

树的邻接矩阵、双亲孩子表示法…… C++ 不知树系列之初识树( 三 )

生活百科

测试代码：
int main() { //通过初始化根节点创建树 Tree tree('A'); TreeNode root=tree.getRoot(); int codeB= tree.addVertex('B'); tree.addEdge(root.code,codeB); int codeC= tree.addVertex('C'); tree.addEdge(root.code,codeC); int codeD= tree.addVertex('D'); tree.addEdge(codeB,codeD); int codeE= tree.addVertex('E'); tree.addEdge(codeC,codeE); int codeF= tree.addVertex('F'); tree.addEdge(codeC,codeF); tree.showAll();}输出结果：

树的邻接矩阵、双亲孩子表示法…… C++ 不知树系列之初识树

文章插图
邻接矩阵存储方式的优点：
  • 节点存储在线性容器中，可以很方便的遍历所有节点 。
  • 使用矩阵仅存储节点之间的关系，节点的存储以及其关系的存储采用分离机制，无论是查询节点还是关系（以节点的编号定位矩阵的行，然后在此行上以列扫描就能找到所以子节点）都较方便 。
缺点：
  • 矩阵空间浪费严重，虽然可以采用矩阵压缩，但是增加了代码维护量 。
3.2 邻接表存储邻接表存储和邻接矩阵的分离存储机制不同，邻接表的节点类型中除了存储数据信息，还会存储节点之间的关系信息 。
可以根据节点类型中的信息不同分为如下几种具体存储方案：
3.2.1 双亲表示法结点类型有 2 个存储域：
  • 数据域 。
  • 指向父节点的指针域 。

树的邻接矩阵、双亲孩子表示法…… C++ 不知树系列之初识树

文章插图
如下文所示的树结构，用双亲表示法思路存储树结构后的物理结构如下图所示 。
树的邻接矩阵、双亲孩子表示法…… C++ 不知树系列之初识树

文章插图
根节点没有父结点，双亲指针域中的值为 0 。
双亲表示法很容易找到节点的父节点，如果要找到节点的子节点，需要对整个表进行查询，双亲表示法是一种自引用表示法 。
双亲表示法无论使用顺序存储或链表存储都较容易实现 。
3.2.2 孩子表示法用顺序表存储每一个节点，然后以链表的形式为每一个节点存储其所有子结点 。如下图所示，意味着每一个节点都需要维护一个链表结构，如果某个节点没有子结点，其维护的链表为空 。
树的邻接矩阵、双亲孩子表示法…… C++ 不知树系列之初识树

文章插图
孩子表示法，查找节点的子节点或兄弟节点都很方便，但是查找父节点，就不怎方便了 。可以综合双亲、孩子表示法 。
3.2.3 双亲孩子表示法双亲孩子表示法的存储结构，无论是查询父节点还是子节点都变得轻松 。如下图所示 。
树的邻接矩阵、双亲孩子表示法…… C++ 不知树系列之初识树

文章插图
双亲孩子表示法的具体实现：
  • 设计节点类型:
#include <iostream>#include <vector>using namespace std;struct TreeNode { //节点编号 int code; //节点的值 char val; //节点的父节点 TreeNode *parent; //节点的子节点信息，以单链表的方式存储,head 指向第一个子节点的地址 TreeNode *head; //兄弟结点 TreeNode *next; //构造函数 TreeNode(int code,char val) {this->code=code;this->val=val;this->parent=NULL;this->head=NULL;this->next=NULL; } //自我显示 void show() {cout<<"结点：";cout<<this->code<<"-"<<this->val<<endl;if(this->parent) {cout<<"\t父节点：";cout<<this->parent->code<<"-"<<this->parent->val<<endl;}TreeNode *move=this->head;while(move) {cout<<"\t子节点："<<move->code<<"-"<<move->val<<endl;move=move->next;} }};树类型定义：
class Tree { private://一维数组容器，存储所有结点vector<TreeNode*> treeNodes;//节点的编号生成器int idx=0; public://无参构造函数Tree() {}//有参构造函数，初始化根节点Tree(char val) {//动态创建节点TreeNode* root=new TreeNode(this->idx,val);this->idx++;this->treeNodes.push_back(root);}//返回根节点TreeNode* getRoot() {return this->treeNodes[0];}//添加新节点TreeNode* addTreeNode(char val,TreeNode *parent) {//创建节点TreeNode* newNode=new TreeNode(this->idx,val);if(!newNode)//创建失败return NULL;if(parent) {//设置父节点newNode->parent=parent;//本身成为父节点的子节点if(parent->head==NULL)parent->head=newNode;else {//原来头节点成为尾节点newNode->next=parent->head;//新子节结点成为头结点parent->head=newNode;}}//编号自增this->idx++;//添加到节点容器中this->treeNodes.push_back(newNode);return newNode;}//显示树上的所有结点，以及结点之间的关系void showAll() {for(int i=0; i<this->treeNodes.size(); i++) {TreeNode *tmp=this->treeNodes[i];tmp->show();}}};

经验总结扩展阅读


上一篇：2023年农历正月十四宜旅游吗 2023年2月4日旅游吉日一览表

下一篇：2023年9月29日粉刷墙壁好吗 2023年9月29日粉刷墙壁行吗