数据结构与算法之树、森林与二叉树的转换(手绘)

树、森林与二叉树的转换

视频讲解：【数据结构】树、二叉树、森林直接的转换_哔哩哔哩_bilibili

树转换成二叉树

原则：

1. 给兄弟加线
2. 给出除长子外的结点去线【第一个连接的节点就是长子】
3. 层次调整，兄弟节点变成右子元素【书上说：以树根为轴心，顺时钟旋转 45 度】

步骤展示

连线

给出除长子外的结点去线

层次调整

森林转换成二叉树

原则

1. 森林中的每棵树=> 二叉树
2. 将所有的二叉树=> 一颗二叉树

步骤展示

以下列森林为例

根据树转换成二叉树的原则将每颗树转变成二叉树

第 n 棵树作为第 n-1 棵树根节点的右子节点

二叉树转换成树

原则

1. 加线：结点与其后代的右孩子结点连接
2. 去线：去除结点[有右孩子的结点]与其右孩子结点连接
3. 层序调整：同层次调整，兄弟节点变成右子元素【书上说：以树根为轴心，顺时钟旋转45度】

步骤展示

加线

去线

层序调整

二叉树转化到森林

能否转换成森林，看二叉树的根节点有无右孩子？有就是森林

原则

1. 去线：寻找右孩子去线，分离后的两颗树也需要这么分离，直到均无右孩子
2. 转换：将分离的二叉树转换成树

步骤展示

去线

转换

‍