当前位置:首页 > 芯闻号 > 充电吧
[导读]1、树转换为二叉树---- 将树转换为二叉树的步骤如下:--1)加线。在所有兄弟结点之间加一条连线。--2)去线。对树中每个结点,只保留它与第一个孩子结点的连线,删除它与其他孩子结点之间的连线。--3

1、树转换为二叉树

---- 将树转换为二叉树的步骤如下:

--1)加线。在所有兄弟结点之间加一条连线。

--2)去线。对树中每个结点,只保留它与第一个孩子结点的连线,删除它与其他孩子结点之间的连线。

--3)层次调整。以树的根结点为轴心,将整棵树顺时针旋转一定的角度,使之结构层次分明。

注意第一个孩子是二叉树结点的左孩子,兄弟转换过来的孩子是结点的右孩子。

例如下图,一棵树经过三个步骤转换为一棵二叉树。

                    

                      

                       

                   

2、森林转换为二叉树

---- 森林是由若干棵树组成的,所以完全可以理解为:森林中的每一棵树都是兄弟,可以按照兄弟的处理办法来操作。

步骤如下:

--1)把每个树转换为二叉树。

--2)第一棵二叉树不动,从第二棵二叉树开始,依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子,用线连接起来。

当所有的二叉树连接起来后就得到了由森林转换来的二叉树。

如下图所示,将森林的三棵树转化为一棵二叉树:

              

                    

3、二叉树转换为树

---- 二叉树转换为树是树转换为二叉树的逆过程,反过来做。步骤如下:

--1)加线。若某结点的左孩子结点存在,则将这个左孩子的右孩子结点、右孩子的右孩子结点.....右孩子的右孩子的右孩子的结点。。

左孩子的n个右孩子结点都作为此结点的孩子。将该结点与这些右孩子结点用线连接起来。

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

--3)层次调整。使之结构层次分明。

---- 转换过程如下图所示:

                 

              

                     

4、二叉树转换为森林

---- 判断一棵二叉树能够转换为一棵树还是森林,只要看这棵二叉树的根结点有没有右孩子,有就是森林,没有就是一棵树。

如果是转换成森林,步骤如下:

--1)从根结点开始,若右孩子存在,则把与右孩子结点的连线删除,再查看分离后的二叉树,若右孩子存在,则连线删除......,

直到所有右孩子连线都删除为止,得到分离的二叉树。

--2)再将每棵分离后的二叉树转换为树即可。

5、树与森林的遍历

---- 树的遍历分为两种方式:

--1)一种是先根遍历树,即先访问树的根结点,然后依次先根遍历根的每棵子树。

--2)另一种是后根遍历,即先依次后根遍历每棵子树,然后再访问根结点。

             

如上图的树,先根遍历序列为ABEFCDG,后根遍历序列为EFBCGDA。

---- 森林的遍历也分为两种方式:

--1)前序遍历:先访问森林中第一棵树的根结点,然后再依次先根遍历根的每棵子树,再依次用同样方式遍历除去第一棵树的剩余树

构成的森林。

--2)后序遍历:先访问森林中第一棵树,后根遍历的方式遍历每棵子树,然后再访问根结点,再依次同样方式遍历除去第一棵树的剩余

树构成的森林。

           

如上图有三棵树的森林,前序遍历序列的结果是:ABCDEFGHJI。后续遍历的结果是:BCDAFEJHIG。

通过对森林转化为的二叉树进行分析发现:

森林的前序遍历和二叉树的前序遍历结果相同,森林的后序遍历和二叉树的中序遍历结果相同。

---- 当以二叉链表做树的存储结构时,树的先根遍历和后根遍历完全可以借用二叉树的前序遍历和中序遍历的算法来实现。

找到了对树和森林这种复杂问题的简单解决办法。


本站声明: 本文章由作者或相关机构授权发布,目的在于传递更多信息,并不代表本站赞同其观点,本站亦不保证或承诺内容真实性等。需要转载请联系该专栏作者,如若文章内容侵犯您的权益,请及时联系本站删除。
换一批
延伸阅读

9月2日消息,不造车的华为或将催生出更大的独角兽公司,随着阿维塔和赛力斯的入局,华为引望愈发显得引人瞩目。

关键字: 阿维塔 塞力斯 华为

加利福尼亚州圣克拉拉县2024年8月30日 /美通社/ -- 数字化转型技术解决方案公司Trianz今天宣布,该公司与Amazon Web Services (AWS)签订了...

关键字: AWS AN BSP 数字化

伦敦2024年8月29日 /美通社/ -- 英国汽车技术公司SODA.Auto推出其旗舰产品SODA V,这是全球首款涵盖汽车工程师从创意到认证的所有需求的工具,可用于创建软件定义汽车。 SODA V工具的开发耗时1.5...

关键字: 汽车 人工智能 智能驱动 BSP

北京2024年8月28日 /美通社/ -- 越来越多用户希望企业业务能7×24不间断运行,同时企业却面临越来越多业务中断的风险,如企业系统复杂性的增加,频繁的功能更新和发布等。如何确保业务连续性,提升韧性,成...

关键字: 亚马逊 解密 控制平面 BSP

8月30日消息,据媒体报道,腾讯和网易近期正在缩减他们对日本游戏市场的投资。

关键字: 腾讯 编码器 CPU

8月28日消息,今天上午,2024中国国际大数据产业博览会开幕式在贵阳举行,华为董事、质量流程IT总裁陶景文发表了演讲。

关键字: 华为 12nm EDA 半导体

8月28日消息,在2024中国国际大数据产业博览会上,华为常务董事、华为云CEO张平安发表演讲称,数字世界的话语权最终是由生态的繁荣决定的。

关键字: 华为 12nm 手机 卫星通信

要点: 有效应对环境变化,经营业绩稳中有升 落实提质增效举措,毛利润率延续升势 战略布局成效显著,战新业务引领增长 以科技创新为引领,提升企业核心竞争力 坚持高质量发展策略,塑强核心竞争优势...

关键字: 通信 BSP 电信运营商 数字经济

北京2024年8月27日 /美通社/ -- 8月21日,由中央广播电视总台与中国电影电视技术学会联合牵头组建的NVI技术创新联盟在BIRTV2024超高清全产业链发展研讨会上宣布正式成立。 活动现场 NVI技术创新联...

关键字: VI 传输协议 音频 BSP

北京2024年8月27日 /美通社/ -- 在8月23日举办的2024年长三角生态绿色一体化发展示范区联合招商会上,软通动力信息技术(集团)股份有限公司(以下简称"软通动力")与长三角投资(上海)有限...

关键字: BSP 信息技术
关闭
关闭