如何区分树、森林与二叉树的转换规则

简介: 如何区分树、森林与二叉树的转换规则

20210928150734205.png

树、森林、二叉树之间的转换,并不是两两转换

而是普通和二叉之间的转换

树->二叉树

森林->二叉树

这里的树和森林指的是普通的树(树多成林)

相反

二叉和普通之间,只有

二叉树->森林

为什么没二叉树转树呢,我觉得一棵树也可以称之为森林,所以如无必要勿增实体。那问题来了,为什么普通和二叉之间的转换不也只写一个森林转二叉,为什么要有树转二叉树呢,如图所示,树转二叉树是森林转二叉树的基础。

树转二叉树(一棵树唯一的对应一颗二叉树),转换方法就是

1.兄弟变右子树(保证没有多余的叉)

2.顺时针旋转45度(保证变二叉树,而不是普通的树,没有垂直的子树)


森林转二叉树

1第一棵树变左子树

2其余树变右子树


二叉树转森林


1拆树(断开根节点与右子树的连线)

2变普通(左子树逆转45度,右子树变兄弟)

规则有,可是用的时候分不清怎么办呢?

思考普通树和二叉树的主要区别是什么,1.是否只有左右孩子,2.是否至多只有两个叉,这两个是关键点,为什么旋转45度,为的就是区分1.为什么连接兄弟结点或者断开目的是为了区分2.做题的时候想一想这个逻辑,就可以基本推出来做题步骤。

至于森林转二叉树,就是森林先变树,树再变二叉树。


相关文章
|
8月前
|
算法 程序员 测试技术
【数据结构-二叉树 九】【树的子结构】:树的子结构
【数据结构-二叉树 九】【树的子结构】:树的子结构
85 0
|
8月前
|
存储 JavaScript 算法
TypeScript算法专题 - blog4 - 单链表节点的两-两翻转(两两一组逆序)
TypeScript算法专题 - blog4 - 单链表节点的两-两翻转(两两一组逆序)
56 0
|
7月前
|
机器学习/深度学习 存储 算法
数据结构和算法学习记录——树(基本介绍、树的定义、树的特点、树的一些基本术语、树的表示、儿子-兄弟表示法)
数据结构和算法学习记录——树(基本介绍、树的定义、树的特点、树的一些基本术语、树的表示、儿子-兄弟表示法)
115 0
|
8月前
|
存储 机器学习/深度学习 人工智能
树和森林 查找
树和森林 查找
46 2
|
8月前
|
存储
树的存储结构以及树,二叉树,森林之间的转换
树的存储结构以及树,二叉树,森林之间的转换
45 0
|
8月前
|
机器学习/深度学习 算法 测试技术
【深度优先搜索】【树】【C++算法】2003. 每棵子树内缺失的最小基因值
【深度优先搜索】【树】【C++算法】2003. 每棵子树内缺失的最小基因值
|
索引
一次区分 B树、B+树,B*树
一次区分 B树、B+树,B*树
101 0
|
存储
树型结构——二叉数
树型结构——二叉数
158 0
树型结构——二叉数
|
Python
Python 再说勾股树,这次整一棵五彩的任意“生长”的分形树!
Python 再说勾股树,这次整一棵五彩的任意“生长”的分形树!
235 0
|
存储 算法
【数据结构oj】树的度(树和二叉树的相互转化)
【数据结构oj】树的度(树和二叉树的相互转化)
76 0