2019考研计算机：数据结构森林与二叉树的转换复习重点

考研网

《数据结构(C语言版)》复习重点在二、三、六、七、九、十章，考试内容两大类：概念，算法，自从计算机专业课统考以后，专业课考试题型分为2类，一类选择题，一类综合应用题。接下来是新东方在线整理的数据结构(C语言版)树转换成二叉树复习重点。
        1、 树转换成二叉树：连兄弟，留长子，删孩子。
    a) 连线，连接所有兄弟结点。
    b) 删线，仅保留双亲与长子结点的连线，删除与其他孩子结点之间的连线。
    c) 整理，原有的长子结点为左子树，从兄弟转换为孩子的结点为右子树。
    d) 注意，由于树根没有兄弟结点，固树转换为二叉树后，二叉树根结点的右子树必为空。
   

5799154466177928.png

    2、森林转换成二叉树：连树根及兄弟，留长子，删孩子。
    a) 连线，连接每棵树的根结点及所有兄弟结点。
    b) 删线，仅保留双亲与长子结点的连线，删除与其他孩子结点之间的连线。
    c) 整理，第一棵树根结点为二叉树根结点，原有的长子结点为左子树，从兄弟转换为孩子的结点为右子树。
   

3072154466177928.png

    　　3、 二叉树转换成树：连左孩子的右孩子及其右孩子…，删原树右孩子。
    a)
连线，若某结点X存在左孩子XL，则将这个左孩子的右孩子结点XLR、左孩子的右孩子的右孩子结点XLRR、左孩子的右孩子的右孩子的右孩子结点XLRRR…都与X结点连线。
    b) 删线，删除原二叉树的所有双亲与右孩子结点的连线。
    c) 整理，原二叉树根结点为树根结点。
   

2304154466177928.png

    　　4、 二叉树转换成森林：连左孩子的右孩子及其右孩子…，删原树右孩子。
    a)
连线，若某结点X存在左孩子XL，则将这个左孩子的右孩子结点XLR、左孩子的右孩子的右孩子结点XLRR、左孩子的右孩子的右孩子的右孩子结点XLRRR…都与X结点连线。
    b) 删线，删除原二叉树的所有双亲与右孩子结点的连线。
    c) 整理，调整为多棵树的森林。
   

3443154466177928.png