2020-11-22（树，森林和二叉树转换）-白红宇的个人博客

2020-11-22（树，森林和二叉树转换）

发布日期：2021-05-07 12:06:14 浏览次数：18 分类：技术文章

本文共 317 字，大约阅读时间需要 1 分钟。

树转换成相应二叉树分两个步骤：

a.在树中所有的兄弟结点之间加一横线

b.对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线

（1.加线，在所有的兄弟结点之间加一条连线；2.去线，对树中每个结点，只保留它与第一孩子结点的连线，删除它与其他孩子结点之间的连线；3.层次调整，以树的根节点位轴心，将整颗树顺时针旋转一定的角度，使之结构层次分明）

无右子树，只有左子树

森林到二叉树的转换

a.先将森林中的每棵树变成二叉树

b.再将各二叉树的根节点视为兄弟从左至右连在一起，就形成一棵二叉树

一般左右子树都有

左子树是由第一棵树除根节点外（因为第一棵树的根节点变成了此时二叉树的根节点）所构成的，右子树是由其它树所有节点构成的

上一篇：2020-11-23（彻底理解KMP）

下一篇：2020-11-22（操作系统——页面置换算法）

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！