5.4.2 树、森林与二叉树的转换

教材导航 · 第5章

原书定位

印刷页P172起,对应PDF第184页。下文为目视整理的知识提要;完整内容见原书对照。

规则为“左孩子、右兄弟”:每结点左指针指其首孩子,右指针指相邻右兄弟。单棵树的根没有兄弟,因此转换后根的右子树为空。

森林先分别转换每棵树,再用各树根的右指针连接。二叉树反向转森林时,将根与其左子树还原成首棵树,沿根的右链继续得到其余树。

森林的叶结点对应二叉树中左孩子为空的结点;二叉树真正的叶结点还要求右指针为空。森林中树的数量等于转换后从根沿真实右孩子链可数出的结点数。

图5.22 树与二叉树的转换

图5.22 树与二叉树的转换,原书P173。

图5.23 森林与二叉树的转换

图5.23 森林与二叉树的转换,原书P174。

对应练习

5.4 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P172,PDF第184页

原书对照,原书P173,PDF第185页

原书对照,原书P174,PDF第186页