【数据结构与算法学习笔记二十二】树、森林、以及二叉树之间的转化

树、森林转化二叉树

树转二叉树

分为三个步骤:

  • 兄弟+横线
    树中的每一个结点,如果该结点有兄弟结点,那么就在这几个兄弟结点之间进行连线。
  • 保存长子线
    对于树中的每一个结点,如果其有多个子节点,保存其第一个子节点的连线,去除其他子节点的连线。
  • 调整位置
    对每个结点调整一定的位置,使其符合二叉树的标准。

案例:

将上图中的树转化为二叉树

第一步:兄弟+横线

第二步:保留长子线

第三步:调整位置,横线变斜线

森林转二叉树

森林转二叉树分为三个步骤

  • 将每课树转换成二叉树
  • 将每课树的根结点连接起来
    把每棵树的根当做兄弟结点处理,兄弟加横线
  • 旋转调整位置案例:

    将上述森林转化为二叉树

第一步:每课树都转化为二叉树

第二步:根节点横线连接

第三步:调整位置,横线变斜线

二叉树转化为树、森林

二叉树转化树

一般分三个步骤:

  • 若某结点的左孩子结点存在,将左孩子结点的右孩子结点、右孩子结点的右孩子结点……都作为该结点的孩子结点,将该结点与这些右孩子结点用线连接起来;
  • 删除原二叉树中所有结点与其右孩子结点的连线;
  • 调整位置

二叉树转化森林

三步:

  • 先把每个结点与右孩子结点的连线删除,得到分离的二叉树;
  • 把分离后的每棵二叉树转换为树;
  • 调整位置

注:在考研试题当中,一般很少会单独考这个知识点,一般会将这个知识点与二叉树的前序、中序、后序遍历结合,与树和森林的先根、后根遍历相结合。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注