《计算思维与算法入门》 —2.7.3 树转化为二叉树的算法

2.7.3  树转化为二叉树的算法

对于将一般树结构转化为二叉树，使用的方法称为“Child-Sibling”（Leftmost-Child-Next-Right-Sibling，左儿子右兄弟表示法）法则。以下是其执行步骤：

（1）将节点的所有兄弟节点用横线连接起来。

（2）只保留与最左子节点的连接，删掉其他所有与子节点间的连接。

（3）右子树都顺时针旋转45度。

按照下面的范例实践一次，就可以有更清楚的认识。转化前的多叉树如图2-61所示。

图2-61  将此多叉树转化为二叉树

     将树的各层兄弟用横线连接起来，如图2-62所示。

图2-62  将各层兄弟用横线连接起来

     只保留最左边的父子节点的连接，删掉其他所有子节点间的连接，如图2-63所示。

图2-63  只保留最左边的父子节点的连接

     右子树都顺时针旋转45度，如图2-64所示。

图2-64  顺时针旋转45度