数据布局(5.4_1)——树的存储布局

树的逻辑布局

双亲表现法(次序存储)

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

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

复制代码

增长结点操纵 

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

 
删除叶结点操纵 

1、删除结点数据域                           

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

删除非叶结点操纵  

探求其双亲结点相同的结点

孩子表现法 (次序+链式存储)

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

1. #define MAX_TREE_SIZE 100//树中最多结点
3. struct CTNode {
4.     int child;//孩子在结点数组中的位置
5.     struct CTNode* next;//下一个孩子
6. };
7. typedef struct {
8.     int data;
9.     struct  CTNode* firstChild;//第一个孩子
10. }CTBox;
11. typedef struct {
12.     CTBox nodes[MAX_TREE_SIZE];
13.     int n, r;//结点数和根的位置
14. }CTree;

复制代码

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

 

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

复制代码

树和二叉树的转化：

使用孩子兄弟表现法

 
丛林和二叉树的转化 

丛林—>二叉树

二叉树—>丛林

 
总结： 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。