森林与二叉树之间的转换
AI 摘要salmon-ai
本文详细解析了森林与二叉树之间的相互转换方法。森林转二叉树时,先将每棵树按“左孩子保留、
森林转换为二叉树
森林,简单地理解为由多颗树组成,下图左边即为森林

先将树转换为二叉树
- 根节点的孩子中,最左孩子不变,其余的作为孩子结点与根节点断开,从左往右,依次作为其左边兄弟结点的右孩子

- 从左到右,依次连接到左子结点的右边(判断规则,右子树结点连接兄弟结点,左子树结点连接其原先左子树结点),故得下图

- 从左到右,依次将其右边的树连接到其右子节点,如下图,即为该森林的二叉树

二叉树转换为森林
如下图这颗二叉树

首先将每个结点的右子结点与其断开

接着将这些断开的结点与其原父结点的根节点连接(该父结点需为其父节点的左孩子,如不是,则不连接)
比如结点B为结点A的左孩子,则C与A连接;
结点D的父结点A没有父结点,故D无可连接的结点,那么D作为根节点成为一颗树;
结点H的父节点D不是结点A的左孩子,故其单独作为一颗树;
以此类推...

最后,即为所求森林

评论
0 条—
还没有评论,来说第一句