对于普通树转二叉树，要记住6个字口诀：左儿子，右兄弟
实现的步骤是这样的：
- 将树的根节点直接作为二叉树的根节点
- 将树的根节点的第一个子节点作为根节点的左儿子，若该子节点存在兄弟节点，则将该子节点的第一个兄弟节点（方向从左往右）作为该子节点的右儿子
- 将树中的剩余节点按照上一步的方式，依序添加到二叉树中，直到树中所有的节点都在二叉树中
其实说白了就是每个点的左儿子是它的第一个儿子，右儿子是它从左往右数的第一个兄弟
如下图所示（可以自己画一画理解一下）：
还可以这样理解普通树转换成二叉树（实际上是一样的）：
- 在所有兄弟结点之间加一连线
- 对每个结点，除了保留与其第一个儿子的连线外，去掉该结点与其它孩子的连线
如下图所示：
这样一来，就能使一些问题（例如树形DP）更好做一点
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=105;
int son[N],left[N],right[N];
int main()
{
int n,i,x,y;
scanf("%d",&n); //表示有n个点
for(i=1;i<=n;i++)
{
scanf("%d",&x); //x是i号节点的父亲
if(!son[x]) left[x]=i; //这两步就是根据左儿子右兄弟的方式转二叉树
else right[son[x]]=i;
son[x]=i;
}
for(i=1;i<=n;++i)
printf("%d %d\n",left[i],right[i]);
return 0;
}
例题传送门选课
题目大意：有N门功课，每门课有个学分，每门课有0或1门先修课（若课程a是课程b的先修课，那么只有学完了课程a，才能学习课程b）。现要选择M门课程，求最大的学分（洛谷 P2014）
这道题可以把它当做树形DP来做，首先，每个节点的父亲节点是它的先修课，虚建一个节点连向先修课，然后把它转换成二叉树来做，就和二叉苹果树那道题差不多了
不过要注意的是转移的时候有一些差别
要学第x门课和以它为先修课的课：f[x][y]=max(f[x][y],dp(son[x],i)+dp(bro[x],y-i-1)+a[x]);
不学第x门课，全部学它兄弟的课程：f[x][y]=max(f[x][y],dp(bro[x],y));
那么直接用树形DP就行了
代码如下：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=305;
int n,m;
int a[N],bro[N],son[N],f[N][N];
int dp(int x,int y)
{
if(x==-1||y==0) return 0;
if(f[x][y]) return f[x][y];
int i;
f[x][y]=max(f[x][y],dp(bro[x],y));
for(i=0;i<=y-1;++i)
f[x][y]=max(f[x][y],dp(son[x],i)+dp(bro[x],y-i-1)+a[x]);
return f[x][y];
}
int main()
{
int x,i;
memset(son,-1,sizeof(son));
memset(bro,-1,sizeof(bro));
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%d%d",&x,&a[i]);
bro[i]=son[x];
son[x]=i;
}
dp(0,m+1);
printf("%d",f[0][m+1]);
return 0;
}