将普通树转为二叉树

普通树转化为二叉树！

普通树转化为二叉树！

普通树转化为二叉树！

重要的事情说三遍（雾）

 

最近在刷树形dp的题，而树形dp的某些特殊题目多依靠二叉树的结构写出状态转移方程，所以专门看看不得不说说的普通树（多叉树）转二叉树。

 

上图！（没图我说个jb）

 

如图有一颗生长健康饱满有活力的树，但是仔细看看可以发现节点2有三个儿子，即这并不是我们想要的二叉树。

 

怎么办？

 

留长子：

 

剔除所有节点除大儿子以外的所有儿子

养兄弟：

每个无父亲节点指向长兄

至此，一颗多叉树顺利转变为我们想要的二叉树

下面附上源代码/pas:

var
i,x,y:longint;
b:array[0..100]of longint;
begin
readln(n,m);
fillchar(b,sizeof(b),0);
for i:=1 to n do
begin
readln(x,y);
if b[x]=0 then t[x].l:=y
else t[b[x]].r:=y;
b[x]:=y;
end;
end;