森林与二叉树之间的转换

2023-01-20学习1 分钟138 次阅读
AI 摘要salmon-ai

本文详细解析了森林与二叉树之间的相互转换方法。森林转二叉树时,先将每棵树按“左孩子保留、

森林转换为二叉树

森林,简单地理解为由多颗树组成,下图左边即为森林
image-20230120182236246

先将树转换为二叉树

  1. 根节点的孩子中,最左孩子不变,其余的作为孩子结点与根节点断开,从左往右,依次作为其左边兄弟结点的右孩子
    image-20230120182236246
  2. 从左到右,依次连接到左子结点的右边(判断规则,右子树结点连接兄弟结点,左子树结点连接其原先左子树结点),故得下图
    image-20230120182236246
  3. 从左到右,依次将其右边的树连接到其右子节点,如下图,即为该森林的二叉树
    image.png

二叉树转换为森林

如下图这颗二叉树
image-20230120182236246
首先将每个结点的右子结点与其断开
image-20230120182236246
接着将这些断开的结点与其原父结点的根节点连接(该父结点需为其父节点的左孩子,如不是,则不连接)
比如结点B为结点A的左孩子,则C与A连接;
结点D的父结点A没有父结点,故D无可连接的结点,那么D作为根节点成为一颗树;
结点H的父节点D不是结点A的左孩子,故其单独作为一颗树;
以此类推...
image-20230120182236246
最后,即为所求森林
image-20230120184312455

觉得有用就点个赞,不用登录也能读

评论

0 条
登录 之后才能评论
—
还没有评论,来说第一句