树、森林与二叉树的转换

树或森林与二叉树之间有一个自然的一一对应关系。任何一个森林或一棵树可惟一地对应到一棵二叉树;反之,任何一棵二叉树也能惟一地对应到一个森林或一棵树。

树、森林与二叉树的转换

工具/原料

    一棵树,二叉树,或者森林

方法/步骤

    1

    将树转换为二叉树:

    树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树:1.在所有兄弟结点之间加一连线2.对每个结点,除了保留与其长子的连线外,去掉该结点与其它孩子的连线。

    如下图所示:

    树、森林与二叉树的转换

    2

    将一个森林转换为二叉树:

    具体方法是:1.将森林中的每棵树变为二叉树;2.因为转换所得的二叉树的根结点的右子树均为空,故可将各二叉树的根结点视为兄弟从左至右连在一起,就形成了一棵二叉树。

    如下图所示:

    树、森林与二叉树的转换

    3

    二叉树转换为树:

    是树转换为二叉树的逆过程。

    1.加线。若某结点X的左孩子结点存在,则将这个左孩子的右孩子结点、右孩子的右孩子结点、右孩子的右孩子的右孩子结点…,都作为结点X的孩子。将结点X与这些右孩子结点用线连接起来。

    2.去线。删除原二叉树中所有结点与其右孩子结点的连线。

    如下图所示:

    树、森林与二叉树的转换

    4

    二叉树转换为森林:

    假如一棵二叉树的根节点有右孩子,则这棵二叉树能够转换为森林,否则将转换为一棵树。

    1.从根节点开始,若右孩子存在,则把与右孩子结点的连线删除。再查看分离后的二叉树,若其根节点的右孩子存在,则连线删除…。直到所有这些根节点与右孩子的连线都删除为止。

    2.将每棵分离后的二叉树转换为树。

    如下图所示:

    树、森林与二叉树的转换

    5

    树和二叉树是两种不同的数据结构,树实现起来比较麻烦,但是树可以转换为二叉树进行处理,处理完以后再从二叉树还原为树。

    树、森林与二叉树的转换END

注意事项

    树和二叉树是两种不同的数据结构,树实现起来比较麻烦,但是树可以转换为二叉树进行处理,处理完以后再从二叉树还原为树。

温馨提示:经验内容仅供参考,如果您需解决具体问题(尤其法律、医学等领域),建议您详细咨询相关领域专业人士。
免责声明:本文转载来之互联网,不代表本网站的观点和立场。如果你觉得好欢迎分享此网址给你的朋友。
转载请注明出处:https://www.i7q8.com/jiaoyu/2381.html

打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023年07月13日
下一篇 2023年07月15日
single-end

热门百科

single-end

相关推荐

  • 如何区别older和elder

    如何区别older和elder,older和elder的区别有哪些?让我们一起来看视频吧。...

    2024年03月28日
    0℃
  • 科目二定点停车与半坡起步操作技巧图解

    科目二定点停车与半坡起步操作技巧图解,小编只说一下定点停车与半坡起步的操作技巧,至于怎么打转向灯,按喇叭相信教练会教的。...

    2024年03月28日
    0℃
  • 申请美国本科有哪些可以加分的课外活动?

    申请美国本科有哪些可以加分的课外活动,在美国大学的申请要求中,我们常常提到“软实力”。课外活动作为“软实力”的一个方面,能成为招生官筛选学生的重要条件。因为,这些额外的课外活动能够让学生显的更加的优秀。同时,有甚多课外活动在申请美国大学的时候是能够加分的。那么,美国大学更看重什么样的课外活动?...

    2024年03月28日
    0℃
  • 学生如何办理韩国个人旅游签证?

    学生如何办理韩国个人旅游签证,去韩国旅游需要办理旅游签证,大家知道怎么办理签证吗?办理签证时申请人操作要小心,最好不要出错,一旦出错那么您的签证就有可能会被拒签。下面小编就为大家分享一些有关办签的相关说明,大家在办理签证之前需要先来了解一下,希望有利于您的签证办理。...

    2024年03月28日
    0℃
  • 你知道美国计算机专业都有哪些方向吗?

    你知道美国计算机专业都有哪些方向吗,计算机专业作为这些年来最受欢迎的专业,每年申请这个专业的同学都非常多,毕竟计算机领域的工作都是高收入。今天,为了准备申请美国计算机专业的你,就跟着慧德高端留学老师一起来看一下计算机都有哪些方向吧!...

    2024年03月28日
    0℃
关注微信