树的存储结构

树的存储结构有以下几种

1. 双亲表示法

#define MAXSIZE 20

// 节点
typedef struct PTNode
{
    int data;
    // 双亲下标
    int parent;
} PTNode;

// 树
tyepdef struct
{
    PTNode nodes[MAXSIZE];
    // 根的位置和节点树
    inr r, n;
} PTree;

这样子表示的优势在于访问双亲节点的时间复杂度为O(1)，但是如果想要访问一个节点的孩子节点则需要遍历整个树。

2. 孩子表示法

#define MAXSIZE 20

// 孩子节点
typedef struct CTNode
{
    int child;
    struct CTNode *next;
} *ChildPtr

// 节点
typedef struct
{
    int data;
    // int parent;
    ChildPtr first_child;
} CTBox;

typedef struct
{
    // 节点数组
    CTBox nodes[MAXSIZE];
    // 根的位置和节点数
    int r, n;
} CTree;

3. 孩子兄弟表示法

// 孩子兄弟表示法
typedef struct CSNode
{
    int data;
    struct CSNode *first_child, *right_brother;
} CSNode, *CSTree;

这样表示的好处是将一个复杂的树转化为了二叉树。