05-5.4.1 树的存储结构
👋 Hi, I’m @Beast Cheng
👀 I’m interested in photography, hiking, landscape…
🌱 I’m currently learning python, javascript, kotlin…
📫 How to reach me --> 458290771@qq.com
喜欢《数据结构》部分笔记的小伙伴可以订阅专栏，今后还会不断更新。🧑💻
感兴趣的小伙伴可以点一下订阅、收藏、关注！🚀
谢谢大家！🙏
树的逻辑结构回顾
[[5.1.1~2 树的定义和基本术语]]
[[5.2.2 二叉树的存储结构]]
如何实现树的顺序存储？
树：一个分支结点可以有多课子树
只依靠数组下标，无法反映结点之间的逻辑关系
思路：
用数组存顺序存储各个结点。每个结点中保存 数据元素、指向双亲结点（父结点）的“指针”
双亲表示法（顺序存储）
![![[Pasted image 20240617204710.png]]](https://img-blog.csdnimg.cn/direct/5e42e2677a0d4bec89f49dd0188f1c5f.png)
![![[Pasted image 20240617204517.png]]](https://img-blog.csdnimg.cn/direct/3692e236282f4e1a9283f4f5183ca298.png)
#define MAX_TREE_SIZE 100 // 树中最多结点数typedef struct{ // 树的结点定义ElemType data; // 数据元素int parent; // 双亲位置域
}PTNode;typedef struct{ // 树的类型定义PTNode nodes[MAX_TREE_SIZE]; // 双亲表示int n; // 结点数
}PTree;
拓展：双亲表示法存储“森林”
森林是 m ( m ≥ 0 ) m(m \geq 0) m(m≥0) 棵互不相交的树的集合
![![[Pasted image 20240617204640.png]]](https://img-blog.csdnimg.cn/direct/cac61871f3844c55a9ae1b73f8ded19a.png)
双亲表示法的优缺点
- 优点：找双亲（父结点）很方便
- 缺点：找孩子不方便，只能从头到尾遍历整个数组
- 适用场景：“找父亲”多，“找孩子”少。如：并查集
孩子表示法（顺序+链式存储）
![![[Pasted image 20240617204926.png]]](https://img-blog.csdnimg.cn/direct/44a651a652884d07a2d2617f202504fb.png)
孩子表示法：用数组顺序存储各个结点。每个结点中保存 数据元素、孩子链表头指针
// 链表结点中只需要保存孩子的编号以及指向下一个链表结点的指针
struct CTNode{int child; // 孩子结点在数组中的位置struct CTNode *next; // 下一个孩子
};// 一个数组元素中包含数据元素data和一个链表的指针firstChild
typedef struct{ElemType data;struct CTNode *firstChild; // 第一个孩子
} CTBox;// 用上面声明的结构体定义一个数组，在数组中存储结点的信息，同时还要记录这棵树中总共有多少个结点，以及根结点的下标是多少
typedef struct{CTBox nodes[MAX_TREE_SIZE];int n, r; // 结点数和根的位置
} CTree;
用孩子表示法存储“森林”
用孩子表示法存储“森林”
需要记录多个根的位置
孩子表示法的优缺点
- 优点：找孩子很方便
- 缺点：找双亲结点很不方便
- 适用场景：“找孩子”多，“找父亲”少。如：服务流程树
孩子兄弟表示法（链式存储）
typedef struct CSNode{ElemType data; // 数据域struct CSNode *firstChild. *nextsibling; // 第一个孩子和右兄弟指针
} CSNode, *CSTree;
与二叉树类似，采用 二叉链表 实现，每个结点中包含 数据元素 和 两个指针，但这两个指针的含义与二叉树不同
孩子兄弟表示法存储“森林”
![![[Pasted image 20240617210552.png]]](https://img-blog.csdnimg.cn/direct/d02c90bff2f946ba96cbef9b6493b164.png)
![![[Pasted image 20240617210626.png]]](https://img-blog.csdnimg.cn/direct/6a8e7452da374703bdd040db4cc951bd.png)