1. 双亲表示法（顺序存储）：每个结点中保存【指向双亲的指针】

优点：查指定结点的双亲很方便

缺点：查指定结点的孩子只能从头遍历

#define MAX_TREE_SIZE 100
// 树的结点
typedef struct{
    ElemType data;
    int parent;
}PTNode;

// 树的类型
typedef struct{
    PTNode nodes[MAX_TREE_SIZE];
    int n;	//结点数量
}PTree;
1
2
3
4
5
6
7
8
9
10
11
12

• 如果新增元素的话，直接在数组后面加上即可【data+父结点】，无需按逻辑上的次序存储
• 如果删除3号元素的话，7、8、9也会被删除【通过遍历的方法，找7、8、9】
    
  ①data去掉，parent=-1
  
  ②让最后一个元素，等于这个【间接删除】

---

2. 孩子表示法 （顺序+链式存储）：顺序存储各个节点，每个结点中保存【孩子链表头指针】

#define MAX_TREE_SIZE 100

struct CTNode{
  int child;	//孩子结点在数组中的位置
  struct CTNode *next;	//下一个孩子
}

typedef struct{
  ElemType data;
  struct CTNode *firstChild;	//第一个孩子
}CTBox;

typedef struct{
  CTBox node[MAX_TREE_SIZE];
  int n,r;	//结点数和根的位置
}CTree;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

3. 孩子兄弟表示法（链式存储）：将树转换为二叉树的形式

typedef struct CSNode{
    ElemType data;
    struct CSNode *firstchild, *nextsibling;	//第一个孩子   和   右兄弟结点
}CSNode, *CSTree;
1
2
3
4

---

重点

1. 树与二叉树的转换【就是孩子兄弟表示法】

例子1

2. 森林与二叉树的转换

森林是m（m≥0）棵互不相交的树的集合，可以将森林中的树看做一棵树中的兄弟结点，再使用孩子兄弟表示法将其转换为二叉树。

例子1：森林——>二叉树
例子2：二叉树——>森林