树的表示法||干货满满
2024-10-12 20:36:39
发布于:浙江
树的表示法
赋予每一个节点编号,我们可以利用每一个节点的编号作为数组的下标,开辟一个数组来保存每个节点的相关信息。
例如一棵树当中有节点编号。我们就可以开一个数组来保存节点的信息到a[1],a[3],a[5],a[7],a[9]
的数组空间当中。
1. 父亲表示法
利用孩子编号作为下标的数组空间当中,保存了他父亲节点的相关编号信息。
假如说现在存在一个节点编号为的节点,他的父亲节点为号,我们就可以用数组空间a[3] = 1
来表示3号节点的父亲为1号节点。
2.孩子表示法
利用当前节点编号作为下标,开辟一个静态链表(通常可以使用vector来表示),储存孩子的编号
举个糖炒栗子,假如现在有一个节点,孩子为,我们就可以开辟一个vector数组 ve[100005]
,使用ve[3]
保存数字4,5,6
,即ve[3] = {4,5,6}
。 来代表3号节点的孩子存在4,5,6
。
*孩子表示法与父亲表示法结合
我们可以发现无论是哪种表示法都是采用当前节点编号作为下标来保存父亲/孩子的编号,那么我们就可以开辟一个结构体,同时创建出两片空间来保存父亲和孩子 即
struct Node{
int father;
vecotr<int> son ;
}a[10005];
当你存在一个节点,父亲节点为1
且孩子节点为6,7
时,你就可以这样保存它。
a[3].father = 1; // 保存父亲编号
a[3].son.push_back(6);
a[3].son.push_back(7); // 保存孩子编号
这里空空如也
有帮助,赞一个