二叉树与树或森林转换的目的-软考在线

二叉树与树或森林转换的目的

由于树或森林可借用孩子兄弟表示法实现与二叉树的转换，因而我们只要研究二叉树的特性就行了，而无须对树或森林单独进行深入的讨论。

这里仅给出森林和二叉树的转换算法，树和二叉树的转换算法类似。

1）森林的二叉树表示

森林转换成二叉树的步骤如下。

设T=｛T₁,T₂,…，T_n｝是森林，对应的二叉树B={root, LB, RB｝，则：

（1）若T为空，即n=0，则B为空。

（2）若T非空，即n>0，则二叉树的根为T₁的根，其左子树是从T₁中根节点的子树森林T=｛T₁₁,T₁₂，…，T₁_n}转换而成的二叉树；其右子树是从森林T=｛T₂,T₃，…,T_n｝转换而成的二叉树。

2）二叉树转化为森林

若B是一棵二叉树，根为T，L为左子树的根，R为右子树的根，则其相应的森林T｛B｝由下列步骤形成：

（1）若B为空，则T为空。

（2）若B非空，则B的根节点T为｛T₁, T₂, …,T_n｝的根节点，B[L]构成了T₁的不相交的子树集合｛T₁₁，T₁₂,…，T₁_n｝；B[R]构成了森林中其他的树T₂，…，T_n。

更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5