树、森林与二叉树的转换
标签: 数据结构
学习人数: 4815


全屏播放
赞赏支持

树转换为二叉树

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

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

(3)层次调整。以树的根节点为轴心,将整棵树顺时针旋转一定角度,使之结构层次分明。(注意第一个孩子是结点的左孩子,兄弟转换过来的孩子是结点的右孩子)

                      

 

森林转换为二叉树

(1)把每棵树转换为二叉树。

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

 

 

二叉树转换为树

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

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

登录查看完整内容


课后作业

课后习题

 

【2014年真题】将森林 F 转换为对应的二叉树 T,F 中叶结点的个数等于()
A.T 中叶结点的个数         B.T 中度为 1 的结点个数 
C.T 中左孩子指针为空的结点个数     D.T 中右孩子指针为空的结点个数

参考答案:C
答案解析:将森林转化为二叉树即相当于用孩子兄弟表示法表示森林。在变化过程中,原森林 某结点的第一个孩子结点作为它的左子树,它的兄弟作为它的右子树。那么森林中的叶结点由于没有孩子结点,那么转化为二叉树时,该结点就没有左结点,所以 F 中叶结点的个数就等于 T 中左孩子指针为空的结点个数,选 C。 
此题还可以通过一些特例来排除 A、B、D 选项。 

 

【2011年真题】已知一棵有2011个结点的树,其叶结点个数为116,该树对应的二叉树中无右孩子的结点个数是()
A.115
B.116
C.1895
D.1896 

解答:D。本题可采用特殊情况法解。设题意中的树是如下图所示的结构,则对应的二 
叉树中仅有前115个叶结点有右孩子。


【2009年真题】将森林转换为对应的二叉树,若在二叉树中,结点 u 是结点 v 的父结点的父结点,则在原来的森林中,u和 v 可能具有的关系是()。 
Ⅰ.父子关系 Ⅱ.兄弟关系 
Ⅲ.u 的父结点与 v 的父结点是兄弟关系 
A. 只有Ⅱ B.Ⅰ和Ⅱ C.Ⅰ和Ⅲ D.Ⅰ、Ⅱ和Ⅲ

参考答案:B
答案解析:考查森林和二叉树的转换。 
森林与二叉树的转换规则为“左孩子右兄弟”。在最后生成的二叉树中,父子关系在对应森林关系中可能是兄弟关系或原本就是父子关系。 
情形Ⅰ:若结点 v 是结点 u 的第二个孩子结点,在转换时,结点 v 就变成结点 u 第一个孩子的右孩子,符合要求。 
情形Ⅱ:结点 u 和 v 是兄弟结点的关系,但二者之中还有一个兄弟结点 k,则转换后,结点 v 就变为结点 k 的右孩子,而结点 k 则是结点 u 的右孩子,符合要求。 
情形Ⅲ:结点 v 的父结点要么是原先的父结点或兄弟结点。若结点 u 的父结点与 v 的父结点是兄弟关系,则转换之后,不可能出现结点 u 是结点 v 的父结点的父结点。 


登录后发布评论

暂无评论,来抢沙发