数据结构(5.4_1)——树的存储结构

树的逻辑结构

双亲表示法(顺序存储)

每个结点中保存指向双亲的“指针”

#define MAX_TREE_SIZE 100//树中最多结点  typedef struct {//树的结点定义     int data;//数据元素     int parent;//双亲位置域 }PTNode; typedef struct {//树的类型定义     PTNode nodes[MAX_TREE_SIZE];//双亲表示         int n;//结点数 }PTree;

增加结点操作 

新增数据元素无需按逻辑上的次序存储，之家在上一个结点后添加新结点，并记录双亲结点

删除叶结点操作 

1、删除结点数据域                           

2、将尾部数据移动至删除结点位置填充空缺

删除非叶结点操作  

寻找其双亲结点相同的结点

孩子表示法 (顺序+链式存储)

顺序存储各个节点，每个结点中保存孩子的链表头指针

#define MAX_TREE_SIZE 100//树中最多结点  struct CTNode {     int child;//孩子在结点数组中的位置     struct CTNode* next;//下一个孩子 }; typedef struct {     int data;     struct  CTNode* firstChild;//第一个孩子 }CTBox; typedef struct {     CTBox nodes[MAX_TREE_SIZE];     int n, r;//结点数和根的位置 }CTree;

孩子兄弟表示法(链式存储) 

/树的存储——孩子兄弟表示法 typedef struct CSNode {     int data;     struct CSNode* firsitchild, * nextsilbling;//第一个孩子和右兄弟指针 }CSNode,*CSTree; int main() {      return 0; } 

树和二叉树的转化：

使用孩子兄弟表示法

森林和二叉树的转化 

森林—>二叉树

二叉树—>森林

总结：