C35.【C++ Cont】树的存储网站首页 技术教程

1.按有根树存储

A:存B C D

B:存E F

C:存NULL(空)

D:存G H I

E:存J

F:存NULL(空)

G:存NULL(空)

H:存K

I:存NULL(空)

J:存NULL(空)

K:存NULL(空)

2.按无根树存储

A:存B C D

B:存E F A

C:存A

D:存G H I A

E:存J B

F:存B

G:存D

H:存K D

I:存D

J:存E

K:存H

vector数组实现

设有n个节点,则创建的数组为vector<int> edges[n+10];//多加10个防止意外情况,edge n.边

每个edges[i]存储各自的孩子节点,使用edge[i].push_back(?);即可

例如对上图按无根树处理,由于父子关系不明确,此时需要把所有的情况都存下来,即存储每个节点相连的所有节点,其vector数组可以表示为:

代码示例

#include <iostream>
#include <vector>
using namespace std;
const int N = 1e3 + 10;
vector<int> edges[N];
int n, a, b;
using namespace std;
int main()
{
	cin >> n;
	n--;//节点数==边数+1
	while (n--)//n次询问
	{
		cin >> a >> b;//每次询问读两个节点的编号
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	return 0;
}

放到VS2022上调试,输入下面这个测试用例后在监视窗口上查看

9

3 1

1 2

4 1

2 5

6 2

7 4

4 8

4 9

链式前向星实现

以下面这棵无根树为例,实现链式前向星(Forward Star)存储

链式前向星存储的本质实际上是用链表存储,复习:C31.【C++ Cont】静态实现单链表

由于是无根树,因此需要把连接的所有情况都存下来

1->3 3->1; 3->4 4->3; 4->2 2->4;

创建足够大的数组head存所有结点的哨兵位,哨兵位的下标存储节点的编号,val数组存数据和next数组存指针,id来标记新来节点的位置

操作:当x有一个子节点y时,将y头插到x的链表中

则上图的存储结果为:

例如以head[3]为例,检查它连接的所有结点

链式前向星词语拆解

由上述分析可知,链式前向星的名词可以拆解为"链式"、"前向"、"星"

"链式":利用链表存储

"前向":前向插入,即头插

"星":可以形象理解为在逻辑上类似于“星形”结构.每个节点可以看作是“星”的中心,从该节点出发的所有边像“星芒”一样向外延伸;每条边通过next指针连接起来,形成了一个以该节点为中心的链状结构，整体上呈现出一种“星形”的拓扑结构

代码示例

VS2022上测试以下代码,下断点至return 0;检查head,val,next数组存储的值

(注:直接使用next数组会报错"next"不明确,因为next是C++ 标准库中的一个函数名改成,_next即可)

#include <iostream>
#include <vector>
using namespace std;
//head[0],val[0].next[0]弃置不用
int head[20], val[20], _next[20],id;//最多存19个结点
void push_front(int a, int b)//设b是a的孩子,则将b头插到a的链表中
{
    val[++id] = b;
    _next[id] = head[a];//注意head[a]不能写成_next[head[a]]! head[a]就是指编号为a结点的下一个结点
    head[a] = id;
}

int main()
{
    int num, a, b;//num为结点的总个数
    cin >> num;
    num--;//节点数==边数+1
    while (num--)//num次询问
    {
        cin >> a >> b;
        push_front(a, b);
        push_front(b, a);
    }
    return 0;
}