从叶子结点向上构造二叉树,只是加了一点剪枝 但…………求大佬找一下剪枝的错误
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
void init();
void bfs(int);
void Pr(int);
struct toTr//节点
{
int value,no,soLe,soRi;
toTr operator = (toTr &b)
{
memcpy(this,&b,sizeof(toTr));
return *this;
}
};
const int N = 10000;
typedef pair<int,int> pa;
map<pair<int,int>,bool>un;
toTr a[N];
int b[N],n,cnt,ct;//节点数
int main()
{
init();
bfs(n);
return 0;
}
void init()
{
// memset(a,0,sizeof(a);
scanf("%d",&n);
for(int i = 1;i <= n;i++)
{
a[i].value = a[i].no = i;
}
cnt = ct = n+1;
}
void bfs(int d)
{
if(d == 1)
{
puts("ed");
for(int i = 1;i < ct;i++)if(!b[i])
{
Pr(i);
}
return;
}
for(int i = 1;i < ct;i++)if(!b[i])
{
for(int j = 1;j < ct;j++)if(!b[j])if(i!=j)
{
pa t;
toTr tt;
tt.soLe= a[i].no,t.first = a[i].value,tt.soRi = a[j].no, t.second = a[j].value;
if(!un[t])//map 应该是0吧 不一定正确的剪枝 已经枚举过的节点不再枚举
{
tt.value = cnt;
tt.no = ct;
un[t] = 1;
a[ct] = tt;
b[j] = b[i] = 1;
// toTr tp = a[i];
cnt++;
ct++;
// printf("d:%d ct:%d cnt:%d no:%d va:%d sl:%d sr:%d\n",d,ct,cnt,a[ct].no,a[ct].value,a[ct].soLe,a[ct].soRi);
bfs(d-1);
ct--;
b[j] = b[i] = 0;
// a[ct] = tp;
}
}
}
}
void Pr(int n)
{
printf("%d:%3d ",n,a[n].value);
int t = a[n].soLe;
if(t)Pr(t);
else putchar(65);
putchar('\n');
t = a[n].soRi;
if(t)Pr(t);
else putchar(65);
}