树的存储结构

树的存储结构

树的结构很强大，操作系统的文件管理、操作系统的目录管理、网络系统中的域名管理、数据库系统中的索引都利用了树的结构。

树的存储结构有以下三种常见的表示法：1、双亲表示法 2、孩子表示法 3、孩子兄弟表示法

 

双亲表示法-以双亲作为索引关键词的一种存储方式。

双亲表示法的存储结构如下;

#define MAX_TREE_SIZE  100
typedef int ElemType;
typedef struct PTNode
{
	ElemType data;//结点数据
	int parent;//双亲位置
}PTNode;
typedef struct
{
	PTNode nodes[MAX_TREE_SIZE];
	int root;//根的位置
	int num;//结点数目
}PTree;

双亲表示法的存储结构，可以根据某结点的parent指针找到它的双亲结点，且时间复杂度为O(1)。但是要找到某结点的孩子，则必须遍历整个树结构。

孩子表示法-就是每个结点中存放指向它第一孩子结点的指针，若此结点没有孩子，则此结点存放的指针为NULL。若此结点有多个孩子结点，则第一个孩子结点存放指向第二个孩子结点的指针，依次下去。

为了找到该结点的双亲结点，此时我们结合上面两种表示法，得到双亲孩子表示法。双亲孩子表示法的存储结构如下：

#define MAX_TREE_SIZE  100
typedef int ElemType;
//孩子结点
typedef struct CTNode
{
	int child;//孩子结点的下标
	 struct CTNode* next;//指向下一个孩子结点的指针
}*ChildPtr;
//表头结构
typedef struct
{
	ElemType data;//每个结点存放的数据
	int parent;//结点双亲的下标
	ChildPtr firstchild;//指向第一个孩子结点的指针
}CTBox;
//树结构
typedef struct
{
	CTBox nodes[MAX_TREE_SIZE];
	int root;//根的位置
	int num;//结点数目
}CTree;