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

可以根据节点类型中的信息不同分为如下几种具体存储方案：
3.2.1 双亲表示法结点类型有 2 个存储域：

数据域。
指向父节点的指针域。

文章插图
如下文所示的树结构，用双亲表示法思路存储树结构后的物理结构如下图所示。

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

文章插图
孩子表示法，查找节点的子节点或兄弟节点都很方便，但是查找父节点，就不怎方便了。可以综合双亲、孩子表示法。
3.2.3 双亲孩子表示法双亲孩子表示法的存储结构，无论是查询父节点还是子节点都变得轻松。如下图所示。

文章插图
双亲孩子表示法的具体实现：

设计节点类型:

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

测试代码：

int main(int argc, char** argv) {	Tree tree('A');//返回根节点	TreeNode * root =tree.getRoot();//根节点下添加 B、C两个子节点	TreeNode * rootB= tree.addTreeNode('B',root);	TreeNode * rootC= tree.addTreeNode('C',root);//B下添加D子节点	TreeNode * rootD= tree.addTreeNode('D',rootB);//C下添加E、F子节点	TreeNode * rootE= tree.addTreeNode('E',rootC);	TreeNode * rootF= tree.addTreeNode('F',rootC);	tree.showAll();	return 0;}

输出结果：