实现树的先根遍历(c++)输入:若干行,每行描述了一组双亲节点和孩子节点的关系序偶对(每个节点用不同的大小写字母表示,节点小于26个)。且树的度小于5。输出:该树的先根遍历序列,序列中每个字母用空格隔开
时间: 2024-03-17 20:40:26 浏览: 14
以下是实现树的先根遍历的C++代码:
```c++
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=30;
int n;
int p[N];//记录每个节点的双亲节点
int c[N][5];//记录每个节点的孩子节点
bool st[N];//记录每个节点是否已经被遍历过
void dfs(int u){//先根遍历
st[u]=true;
cout<<(char)(u+'A')<<" ";
for(int i=0;i<5;i++){
int son=c[u][i];
if(son==-1) break;
if(!st[son]){
dfs(son);
}
}
}
int main(){
memset(c,-1,sizeof c);
memset(st,false,sizeof st);
string str;
while(cin>>str){
if(str=="()") break;
int len=str.size();
int u=str[1]-'A';
for(int i=3;i<len;i++){
if(str[i]>='A'&&str[i]<='Z'){
c[u][p[u]++]=str[i]-'A';
}
else if(str[i]==',') continue;
else{
p[u]=str[i]-'0';
break;
}
}
}
for(int i=0;i<26;i++){//遍历所有节点,找到根节点
for(int j=0;j<5;j++){
int son=c[i][j];
if(son!=-1) p[son]++;
}
}
int root;
for(int i=0;i<26;i++){
if(p[i]==0){
root=i;
break;
}
}
dfs(root);
return 0;
}
```
输入说明:
第一行输入一组双亲节点和孩子节点的关系序偶对,每个节点用不同的大小写字母表示,节点小于26个。如果孩子节点数小于5,则用-1补齐。
输出说明:
输出该树的先根遍历序列,序列中每个字母用空格隔开。
例如,输入如下:
```
(A,2,B,C)
(B,1,D)
(C,2,E,F)
(E,0)
(D,0)
(F,0)
()
```
则输出:
```
A B D C E F
```