|
|
|
知识路径： > 计算机科学基础 > 常用数据结构 > 树 > 树和二叉树 >
|
|
相关知识点：11个
|
|
|
|
|
由于树或森林可借用孩子兄弟表示法实现与二叉树的转换，因而我们只要研究二叉树的特性就行了，而无须对树或森林单独进行深入的讨论。
|
|
|
|
这里仅给出森林和二叉树的转换算法，树和二叉树的转换算法类似。
|
|
|
|
|
|
|
|
设T=｛T1,T2,…，Tn｝是森林，对应的二叉树B={root, LB, RB｝，则：
|
|
|
|
|
|
（2）若T非空，即n>0，则二叉树的根为T1的根，其左子树是从T1中根节点的子树森林T=｛T11,T12，…，T1n}转换而成的二叉树；其右子树是从森林T=｛T2,T3，…,Tn｝转换而成的二叉树。
|
|
|
|
|
|
若B是一棵二叉树，根为T，L为左子树的根，R为右子树的根，则其相应的森林T｛B｝由下列步骤形成：
|
|
|
|
|
|
（2）若B非空，则B的根节点T为｛T1, T2, …,Tn｝的根节点，B[L]构成了T1的不相交的子树集合｛T11，T12,…，T1n｝；B[R]构成了森林中其他的树T2，…，Tn。
|
|
|
|
|
|
|
|
