5.4.2 树、森林与二叉树的转换
原书定位
印刷页P172起,对应PDF第184页。下文为目视整理的知识提要;完整内容见原书对照。
规则为“左孩子、右兄弟”:每结点左指针指其首孩子,右指针指相邻右兄弟。单棵树的根没有兄弟,因此转换后根的右子树为空。
森林先分别转换每棵树,再用各树根的右指针连接。二叉树反向转森林时,将根与其左子树还原成首棵树,沿根的右链继续得到其余树。
森林的叶结点对应二叉树中左孩子为空的结点;二叉树真正的叶结点还要求右指针为空。森林中树的数量等于转换后从根沿真实右孩子链可数出的结点数。

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

图5.23 森林与二叉树的转换,原书P174。
对应练习
关联知识
原书对照
展开原书对照截图


