linked-list - 将二叉树展平为带有旋转的链表

Question

我想展平二叉树并使用旋转将其转换为链表。我们应该有两种类型的链表，第一种是当所有节点都在左侧时，即：我们的树将只有左孩子，所有右孩子都将变为 NULL，我们将通过做这种类型的转换对所有具有右孩子的节点进行左旋转。第二种类型是一棵只有右孩子的树，左孩子设置为 NULL，我们通过对所有有左孩子的节点进行右旋转来进行这种转换。尽管我尝试了很多，但我不知道如何编写此转换的算法，我只需要此转换的算法或 C 中的代码。这是数据结构：

 typedef struct Tib Type_Tib  ;
  typedef Type_Tib * Typestr_Tib ;
  typedef int Type1_Tib  ;
  typedef bool Type2_Tib  ;
  struct Tib
    {
      Type1_Tib Champ1 ;
      Type2_Tib Champ2 ;
    };

  Type1_Tib Struct1_Tib ( Typestr_Tib S)
    {
      return  S->Champ1 ;
    }

  Type2_Tib Struct2_Tib ( Typestr_Tib S)
    {
      return  S->Champ2 ;
    }

  void Aff_struct1_Tib ( Typestr_Tib S, Type1_Tib Val )
    {
       S->Champ1 = Val ;
    }

  void Aff_struct2_Tib ( Typestr_Tib S, Type2_Tib Val )
    {
       S->Champ2 = Val ;
    }


  /** Arbres de recherche binaire **/

  typedef Typestr_Tib Typeelem_ATib   ;
  typedef struct Noeud_ATib * Pointeur_ATib ;

  struct Noeud_ATib
    {
      Typeelem_ATib  Val ;
      Pointeur_ATib Fg ;
      Pointeur_ATib Fd ;
      Pointeur_ATib Pere ;
     } ;

希望你能帮助我，因为我真的需要这个算法。

标签： linked-listbinary-search-treenodestransformationchildren