树的邻接矩阵、双亲孩子表示法…… C++ 不知树系列之初识树( 二 ) _生活百科

arrTree的矩阵，行和列的编号对应节点的编号，并初始矩阵的值都为 0 。

文章插图

在树结构中，编号为 1 的节点和编号为2、3的节点存在父子关系，则把矩阵的 arrTree[1][2]和 arrTree[1][3]的位置设置为1 。也就是说，行号和列号交叉位置的值如果是 1 ，则标志着编号和行号、列号相同的节点之间有关系。

文章插图

找到树中所有结点之间的关系，最后矩阵中的信息如下图所示。

文章插图
矩阵记录了结点之间的双向（父到子，子到父）关系，最终看到是一个对称的稀疏矩阵。可以只存储上三角或下三角区域的信息，并可以对矩阵进行压缩存储。
邻接矩阵存储优点是实现简单、查询方便。但是，如果不使用压缩算法，空间浪费较大。
3.1.2 编码实现现采用邻接矩阵方案实现对如下树的具体存储：

文章插图

节点类型：用来描述数据的信息。

struct TreeNode{ //节点的编号 int code; //节点上的值 int data;};

树类型：树类型中除了存储节点（数据）信息以及节点之间的关系，还需要提供相应的数据维护算法。本文仅考虑如何对树进行存储。

class Tree {	private:int size=7;vector<TreeNode> treeNodes;//使用矩阵存储节点之间的关系，矩阵第一行第一列不存储信息int matrix[7][7];//节点编号，为了方便，从 1 开始int idx=1;	public:Tree() {}//初始根节点Tree(char root) {cout<<3<<endl;for(intr=1; r<this->size; r++) {for(int c=1; c<this->size; c++) {this->matrix[r][c]=0;}}TreeNode node= {this->idx,root};this->treeNodes.push_back(node);//节点的编号由内部指定this->idx++;}//获取到根节点TreeNode getRoot() {return this->treeNodes[0];}//添加新节点int addVertex(char val) {if (this->idx>=this->size)return 0;TreeNode node= {this->idx,val};this->treeNodes.push_back(node);//返回节点编号return this->idx++;;}/** 添加节点之间的关系*/bool addEdge(int from,int to) {char val;//查找编号对应节点是否存在if (isExist(from,val) && isExist(to,val)) {//建立关系this->matrix[from][to]=1;//如果需要，可以打开双向关系//this->matrix[to][from]=1;}}//根据节点编号查询节点bool isExist(int code,char & val) {for(int i=0; i<this->treeNodes.size(); i++) {if (this->treeNodes[i].code==code) {val=this->treeNodes[i].data;return true;}}return false;}//输出节点信息void showAll() {cout<<"矩阵信息"<<endl;for(intr=1; r<this->size; r++) {for(int c=1; c<this->size; c++) {cout<<this->matrix[r][c]<<" ";}cout<<endl;}cout<<"所有节点信息："<<endl;for(int i=0; i<this->treeNodes.size(); i++) {TreeNode tmp=this->treeNodes[i];cout<<"节点："<<tmp.code<<"-"<<tmp.data<<endl;//以节点的编号为行号，在列上扫描子节点char val;for(int j=1; j<this->size; j++ ) {if(this->matrix[tmp.code][j]!=0) {isExist(j,val);cout<<"\t子节点："<<j<<"-"<<val<<endl;}}}}};

测试代码：

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();}

输出结果：