树的存储结构

1.双亲表示法

#define MAX_SIZE 100
typedef char dadaType;
/**
 * 6.3 树的存储结构
 * 1.双亲表示法
 * 2.孩子表示法(指针方式孩子表示法；数组方式孩子表示法；链表方式孩子表示法)
 * 3.孩子兄弟表示法
 */
// 6.3.1 双亲表示法
typedef struct node
{
    dadaType data;
    int parent;
}node; //双亲表示法的结点

typedef struct parentTree
{
    node treeList[MAX_SIZE];
    int root, length; // 根节点的位置及树结点个数
}tree; //双亲表示法的树

2.孩子表示法(指针方式孩子表示法；数组方式孩子表示法；链表方式孩子表示法)

typedef char dadaType;
// 6.3.2.1 指针方式孩子表示法
#define m 3 //树的度
typedef struct node
{
    dadaType data;
    struct node *child[m]; // 指向孩子的指针数组
}node, *tree;
tree root;

#define MAX_SIZE 100
typedef char dadaType;
// 6.3.2.2 数组方式孩子表示法
#define m 3 //树的度
typedef struct node
{
    dadaType data;
    int child[m]; // 指向孩子的指针数组
}node;

typedef struct tree
{
    node treeList[MAX_SIZE];
    int root, length; // 根节点的位置及树结点个数
}tree;

#define MAX_SIZE 100
typedef char dadaType;
// 6.3.2.3 链表方式孩子表示法
typedef struct chNode // 孩子结点类型(孩子链表)
{
    int child; // 结点位置
    struct chNode *next;
}chNode,*chPoint;

typedef struct node // 树中的结点类型
{
    dadaType data;
    chPoint firstChild; // 指向第一个孩子的指针
}node;

typedef struct tree
{
    node treeList[MAX_SIZE];
    int root, length; // 根节点的位置及树结点个数
}tree;

3.孩子兄弟表示法

typedef char dadaType;
// 3.孩子兄弟表示法
typedef struct node // 树中每个结点类型
{
    dadaType data;
    struct node *firstChild, *rightSibling;
}node, *tree;
tree root;