【数据结构】树和森林（树和森林的存储结构、树森林二叉树的转换、树和森林的遍历

5.树和森林

5.1 树的存储结构

• 树的逻辑结构

  树是n个结点的有限集合。n=0时称为空树。

  在任意一棵非空树中应满足：

  1）有且只有一个特定的根结点；

  2）当n>1，其余结点可分为m个互不相交的有限集合，每个集合本身又是一棵树，称为根结点的子树。

• 双亲表示法——顺序存储

  • 思路：用数组顺序存储各个结点。每个结点中保存数据元素、指向双亲结点的指针。

  • 如：

    

  • 存储结构

    #define MAX_TREE_SIZE 100 //树中最多结点数
    // 树的结点定义
    typedef struct{
        ElemType data; //数据元素
        int parent; //双亲位置域
    }PTNode;
    //树的类型定义
    typedef struct{
        PTNode nodes[MAX_TREE_SIZE]; //双亲表示
        int n; //结点数
    }PTree;
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11

  • 双亲表示法的优缺点

    优点：找双亲方便；

    缺点：找孩子不方便，只能从头遍历整个数组。

    ∴适用于找父亲多，找孩子少的场景，如：并查集

• 孩子表示法——树的顺序存储+链式存储结合

  • 思路：用数组顺序存储各个结点。每个结点中保存数据元素、孩子链表头指针。

  • 如：

    

  • 存储结构

    struct CTNode{
        int child; //孩子结点在数组中的位置
        struct CTNode *next; //下一个孩子
    };
    typedef struct{
        ElemType data;
        struct CTNode *firstChild; //第一个孩子
    }CTBox;
    typedef struct{
        CTBox nodes[MAX_TREE_SIZE];
        int n,r; //结点数和根的位置
    }CTree;
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13

  • 孩子表示法的优缺点

    优点：找孩子方便

    缺点：找双亲不方便，只能遍历每个链表

    ∴适用于找孩子多，找父亲少的场景，如：服务流程树

• 孩子兄弟表示法

  typedef struct CSNode{
   ElemType data; //数据域
   struct CSNode *firstchild,*nextsibling; //第一个孩子和右兄弟指针
  }CSNode,*CSTree;
  1
  2
  3
  4

  • 用于存储森林时，将森林中的每棵树的根节点视为平级的兄弟关系。
  • 从存储视角看形态上和二叉树类似。

5.2 树、森林、二叉树的转换

5.2.1 树转二叉树

• 转换技巧

  1.先在二叉树中，画一个根节点；

  2.按“树的层序”依次处理每个节点。

  基于孩子兄弟表示法：如果当前处理的结点在树中有孩子，就把所有孩子结点“用右指针串成糖葫芦”，并在二叉树中把第一个孩子挂在当前结点的左指针下方。

  

5.2.2 森林转二叉树

• 转换技巧

  1.先把所有树的根结点画出来，在二叉树中用右指针串成糖葫芦；

  2.按森林的层序依次处理每个结点。

  

5.2.3 二叉树转树

• 转换技巧

  1.先画出树的根结点；

  2.从树的根结点开始，按树的层序恢复每个结点的孩子。

  • 如何恢复一个结点的孩子：在二叉树中，如果当前处理的结点有左孩子，就把左孩子和“一整串右指针糖葫芦”拆下来，按顺序挂在当前结点下方。

    

5.2.4 二叉树转森林

• 转换技巧

  1.先把二叉树的根节点和“一整串右指针糖葫芦”拆下来，作为多棵树的根节点；

  2.按森林的层序恢复每个结点的孩子。

  • 如何恢复一个结点的孩子：在二叉树中，如果当前处理的孩子有左孩子，就把左孩子和“一整串右指针糖葫芦”拆下来，按顺序挂在当前结点下方。

    

5.3 树和森林的遍历

5.3.1 树的先根遍历

• 方法

  若树非空，先访问根结点，再依次对每棵子树进行先根遍历。

  void PreOrder(TreeNode *R){
   if(R!=NULL){
       visit(R); //访问根节点
       while(R还有下一个子树T)
           PreOrder(T); //先根遍历下一棵子树
   }
  }
  1
  2
  3
  4
  5
  6
  7

• 例子

5.3.2 树的后根遍历

• 方法

  若树非空，先依次对每棵子树进行后根遍历，最后再访问根结点。

  void PostOrder(TreeNode *R){
   if(R!=NULL){
       while(R还有下一个子树T)
           PostOrder(T); //后根遍历下一棵子树
       visit(R);
   }
  }
  1
  2
  3
  4
  5
  6
  7

• 例子
  

5.3.3 树的层次遍历

• 方法（用队列实现）

  1.若树非空，则根节点入队；

  2.若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队；

  3.重复第2步直到队列为空。

• 例子

5.3.4 森林的先序遍历

• 方法

  若森林为非空，则按如下规则进行遍历：

  1.访问森林中第一棵树的根结点；

  2.先序遍历第一棵树中根结点的子树森林；

  3.先序遍历除去第一棵树后剩余的树构成的森林。

5.3.5 森林的中序遍历

• 方法

  若森林为非空，则按如下规则进行遍历：

  1.中序遍历森林中第一棵树的根结点的子树森林；

  2.访问第一棵树的根结点；

  3.中序遍历除去第一棵树之后剩余的树构成的森林。