vlambda博客
学习文章列表

树、森林、二叉树的转换原理

    树转二叉树

    1. 把所有兄弟结点之间加连线(用红色的表示)

    2. 树中的每个结点只保留与第一个孩子结点的连线,其他的连线都去除(灰色虚线部分)

    3. 调整方位

  • 森林转二叉树

    1. 将每个树都转为二叉树

    2. 第一棵二叉树不动,作为转换后涵盖根结点的部分,其余转换后的二叉树依次添加到右孩子,作为根节点的右子树

树、森林、二叉树的转换原理


  • 二叉树转树

    能转换为树的前提是:二叉树的根结点要没有右子树。

    1. 如果左边的结点存储,则将左孩子的n个右孩子结点都作为此结点的孩子。将该结点与这些右孩子连接起来。

    2. 删除原来的二叉树中的所有结点和其右孩子的连线(红色为新增连线,灰色虚线为待删除连线)

    3. 调整层次

  • 二叉树转森林

    能转换为树的前提是:二叉树的根结点要有右子树。

    1. 从根结点开始,如果有右子树的存在,则把根结点与右子树的连线删掉。

    2. 然后查看分离后的二叉树,如果右孩子存在,重复第一步