树、森林、二叉树之间的转换,并不是两两转换
而是普通和二叉之间的转换
树->二叉树
森林->二叉树
这里的树和森林指的是普通的树(树多成林)
相反
二叉和普通之间,只有
二叉树->森林
为什么没二叉树转树呢,我觉得一棵树也可以称之为森林,所以如无必要勿增实体。那问题来了,为什么普通和二叉之间的转换不也只写一个森林转二叉,为什么要有树转二叉树呢,如图所示,树转二叉树是森林转二叉树的基础。
树转二叉树(一棵树唯一的对应一颗二叉树),转换方法就是
1.兄弟变右子树(保证没有多余的叉)
2.顺时针旋转45度(保证变二叉树,而不是普通的树,没有垂直的子树)
森林转二叉树
1第一棵树变左子树
2其余树变右子树
二叉树转森林
1拆树(断开根节点与右子树的连线)
2变普通(左子树逆转45度,右子树变兄弟)
规则有,可是用的时候分不清怎么办呢?
思考普通树和二叉树的主要区别是什么,1.是否只有左右孩子,2.是否至多只有两个叉,这两个是关键点,为什么旋转45度,为的就是区分1.为什么连接兄弟结点或者断开目的是为了区分2.做题的时候想一想这个逻辑,就可以基本推出来做题步骤。
至于森林转二叉树,就是森林先变树,树再变二叉树。