树、二叉树和森林之间的转换
树、二叉树和森林之间的转换
树转化为二叉树
- 连线：将所有的兄弟节点连接
- 去线：删除树中每个节点除第一个孩子以外的孩子节点的连线
- 调整：以根节点为轴心，顺时针旋转一定角度，是层次结构分明
森林转化为二叉树
- 把森林中的每棵树转化为二叉树
- 从第二棵二叉树开始，将树的根节点作为前一棵树根节点的右孩子连接
一个拥有三棵树的森林
将所有树转化为二叉树
将所有二叉树转化为一颗二叉树
二叉树转化为树
是树转化为二叉树的逆运算
- 连线：若节点的左孩子节点存在，则将此节点的右孩子节点以及右孩子节点的右孩子节点，以此类推的所有节点与此节点连接
- 去线：删除二叉树中所有节点与右孩子节点的连线
- 层次结构进行调整
二叉树转化为森林
根节点具有右孩子的二叉树能转化为森林，没有的将转化为一棵树
- 分离二叉树：将二叉树根节点与右孩子的连线删除，生成新的二叉树，继续上述操作直到二叉树的根节点没有右孩子
- 将每棵分离后的二叉树转化为树，形成森林