树、森林、二叉树的转换原理
把所有兄弟结点之间加连线(用红色的表示)
树中的每个结点只保留与第一个孩子结点的连线,其他的连线都去除(灰色虚线部分)
调整方位
树转二叉树
森林转二叉树
将每个树都转为二叉树
第一棵二叉树不动,作为转换后涵盖根结点的部分,其余转换后的二叉树依次添加到右孩子,作为根节点的右子树
二叉树转树
能转换为树的前提是:二叉树的根结点要没有右子树。
如果左边的结点存储,则将左孩子的n个右孩子结点都作为此结点的孩子。将该结点与这些右孩子连接起来。
删除原来的二叉树中的所有结点和其右孩子的连线(红色为新增连线,灰色虚线为待删除连线)
调整层次
二叉树转森林
能转换为树的前提是:二叉树的根结点要有右子树。
从根结点开始,如果有右子树的存在,则把根结点与右子树的连线删掉。
然后查看分离后的二叉树,如果右孩子存在,重复第一步