• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

合法括号序列与树形结构的相互转换


Recommended Posts

一、算法简述

将一棵有$n$个节点的树转换成长度为$2n$的合法括号序列;

字符括号[];

int cnt

void dfs(int x) {

括号[CNT]='(';

for(int I : son(x))DFS(I);

括号[CNT]=')';

}

生成方法:从根节点dfs到整个树,从父节点dfs到这个节点,插入一个(;从一个子节点追溯到这个节点时,在括号序列中插入一个。

一种从括号序列推导树结构的算法:

int now=0,cnt,fa[];

对于(char s :支架){

if(s=='(') {

cnt

儿子(现在)。推送(CNT);

fa[CNT]=now;

}

else now=fa[now];

}

二、性质

根据题目的条件灵活运用。

括号序列对应的一条链是(((((()))))。

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now