达州做网站
大橙子网站建设，新征程启航
为企业提供网站建设、域名注册、服务器等服务
树的存储结构-创新互联
提到存储结构，可以很自然的想到顺序存储结构和链式存储结构两种。树这种数据结构类型，它是由结点和联接结点的边构成。这些边，联接了树中的任意两个结点，从计算机内存中的存储方式来看，其实，就是通过指针保存了地址，从而实现了两个结点间的联接。
那么关于树的表示方式，先讲一下最简单的，就是双亲表示法，我把它称之为父节点表示法。毕竟，在树中，双亲结点其实就是父节点。既然，链表也是有结点构成，那么，这个结点中，必然的必须得有能够存放数据的变量，以及存放下一个结点的地址的变量，如果没有这个变量，如何建立两个结点间的联接呢？但是，此时，这个存放的地址的变量，并不是存放下一个结点的地址，存放的是它的父节点的地址，也就是父节点在数组中的下标位置。然后还得再定义一个树结构，这个数结构中，必须得包含一个数组，因为数组就是用来表示结点的，还得有一个根节点的位置变量以及结点数的变量。那么，该结构定义如下：
#define MAX_TREE_SIZE 100
typedef int TElemType;
typedef struct PTNode{
TElemType data;
int parent;
}PTNode;
typedef struct{
PTNode nodes[MAX_TREE_SIZE];
int r, n;
}PTree;因为，根节点就是祖先，所以它没有父类，所以，约定,根节点的位置域设置为-1。
如上图所示，结点A就是根结点。
下标 data parent 0 A -1 1 B 0 2 C 0 3 D 0 4 E 1 5 F 1 6 G 1 7 H 2 8 I 3 9 J 3
因为B的父亲是A，所以B中存放了A的下标0，C和D的父亲都是A，所以都存放了下标0，E、F和G的父亲是B，所以它们存放了B的下标1；H的父亲是C，所以H存放了下标2；I和J的父亲是D，所以它们存放了D的下标3。这种方式可以知道哪个结点是哪个结点的父亲，哪个结点是哪个结点的儿子，但是却无法确定顺序，也就是说，一个结点可能拥有多个子节点，但是却无法确定这些子节点哪个在前哪个在后。双亲表示法求父节点方便，因为每个结点中都保存了其父节点的下标。
第二种方式。孩子表示法。依然采用连续存储，也就是数组存储，不过，一个结点分为两部分，一部分放数据，另一部分放其子节点的指针（地址）。若是一个结点有多个孩子，假设A有三个孩子，B、C和D。那么，A中就存放B的指针域，在B中则存放C的指针域，C中则存放D的指针域，也就是A的孩子采用了链式存储的方式，串联了起来。孩子表示法，求其子节点比较方便，而求其父节点就比较麻烦。
孩子表示法结构代码如下：
#define MAXZ_TREE_SIZE 100
typedef struct CTNode{
int child;
struct CTNode *next;
}*ChildPtr;
typedef struct{
TElemType data;
ChildPtr firstchild;
}CTBox;
typedef struct{
CTBox nodes[MAX_TREE_SIZE];
int r, n; //存放树的根和结点数
}CTree;第三种方式。父亲孩子表示法。顾名思义，就是将前两种方式结合了。也就是说，一个结点不止存放数据，还存放该该节点的父节点的下标，还存放该节点子节点的指针，那为什么父节点可以存放下标，存放子节点就只能存放子节点的指针？因为，一个结点只有一个父节点，却有多个子节点，或者是没有子节点，所以没有办法确定子节点的个数，于是，就只能通过链式存储了。
二叉树法（孩子兄第表示法）就是将一般树转化为二叉树。具体转化方式为：左指针指向它的第一个孩子结点，右指针指向它的第一个兄弟结点。
二叉树法结构代码定义如下：
typedef struct CSNode{
TElemType data;
struct CSNode *firstchild, *rightsib;
}CSNode, *CSTree;
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
文章题目：树的存储结构-创新互联
浏览地址：http://dzwzjz.com/article/iiigo.html