👋 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 二叉树的存储结构]]
如何实现树的顺序存储?
树:一个分支结点可以有多课子树
只依靠数组下标,无法反映结点之间的逻辑关系
思路:
用数组存顺序存储各个结点。每个结点中保存 数据元素、指向双亲结点(父结点)的“指针”
双亲表示法(顺序存储)
#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) 棵互不相交的树的集合
双亲表示法的优缺点
- 优点:找双亲(父结点)很方便
- 缺点:找孩子不方便,只能从头到尾遍历整个数组
- 适用场景:“找父亲”多,“找孩子”少。如:并查集
孩子表示法(顺序+链式存储)
孩子表示法:用数组顺序存储各个结点。每个结点中保存 数据元素、孩子链表头指针
// 链表结点中只需要保存孩子的编号以及指向下一个链表结点的指针
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;
与二叉树类似,采用 二叉链表 实现,每个结点中包含 数据元素 和 两个指针,但这两个指针的含义与二叉树不同