树存储结构的几种表示方法_树的存储结构表示法

/*
名称:树存储结构的几种表示方法
说明:对于树的存储结构，一般有以下三种表示方法。
（1）、双亲表示法。这种存储方式采用一组连续的空间来存储每个结点，同时在每个结点中增设一个伪指针，
指示其双亲在结点中的位置。这种方式比较容易找到双亲，但是不容易找到孩子。
（2）、孩子表示法。这种方法是将每个结点的孩子结点都用链表链接起来形成一个线性结构。这种方式比较
容易找到结点的孩子，但是不容易找到其双亲。
（3）、孩子兄弟表示法。这种方式通俗的说是：“左结点是第一个孩子，右结点是下一个兄弟”。这种方式比较灵活，因为其可以转化为二叉树，对其的操作一般都能转化为二叉树的相关操作。

总之，选用不同的存储结构要根据具体的用途。（这当然是废话）。想说的是，在做一些题的时候，如果可以不用
选用二叉树这种相对复杂的存储结构，那就选择线性的结构。对我来说，线性结构比二维的树的结构用的顺手。

*/

//树的存储结构之双亲表示法

//树的结点定义
typedef struct
{
    int data;   //数据元素
    int parent;     //双亲的位置
}PTNode;

//树的类型定义
typedef struct
{
    //PTNode nodes[MAXSIZE];      //双亲表示
    int n;                  //结点数
}PTree;


//树的存储结构之孩子表示法

//链表中孩子结点表示
typedef struct CHNode
{
    int pos;   //孩子的位置
    CHNode *next;    //指向下一个孩子的指针
}CHNode;


//数组中双亲结点表示
typedef struct CHNode1
{
    int data;       //数据元素
    CHNode *firChild;   //指向第一个孩子的指针

}CHNode1;

//树的类型表示
typedef struct
{
    CHNode1 nodes[MAXSIZE];     //所有的结点
    int n;      //节点的个数
}CHTree;



//树的存储结构之孩子兄弟表示法
typedef struct CSNode
{
    int data;   //结点的数据
    CSNode *firstchild,*nextbling;   //第一个孩子和下一个兄弟

}CSNode,*CSTree;



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55