树和森林

发表于   |   分类于

二叉树、树和森林之间是可以转换的.

一. 树的存储结构

1. 双亲表示法

a. 含义

用一个结构体数组表示一棵树, 每个数组元素由数据域和双亲域组成, 保存着当前结点的数据, 以及该结点双亲在数组中的位置.

b. 代码

1
2
3
4
5
6
7
8
9
10
struct DataNode  //结点的结构
{
    TypeData data;  //数据域
    int parent;  //记录双亲在数组中的位置
}DataNode;
struct PTree  //树的结构
{
    DataNode nodes[100];  //树中最多有一百个元素
    int r, n;  //根的位置和结点数 
}PTree;

ｃ. 优缺点

给出某个位置的结点, 方便找到它的双亲, 但是不方便找到它的孩子结点.

2. 孩子表示法

a. 含义

用一个结构体数组表示一棵树, 每棵树都有数据域和孩子域. 数据域保存当前结点的数据, 孩子域指向当前结点的第一个孩子, 如果不止一个孩子, 则第一个孩子的指针域又指向下一个孩子.

b. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct CTNode  //孩子结点的结构
{
    int index;  //孩子结点在数组中的位置
    struct CTNode * next;  //下一个孩子的位置
}CTNode;
typedef struct TNode  //结点的结构
{
    DataType data;  //结点的数据
    struct CTNode * firstchild;  //指向当前结点的第一个孩子
}TNode;
typedef struct Tree  //树的结构
{
    TNode nodes[100];  //树中最多有一百个元素
    int r, n;  //根的位置和结点数
};

c. 优缺点

方便找出某个结点的所有孩子, 但是不能方便地得到某个结点的双亲. 可以通过在数组元素中加入一个属性, 保存双亲在数组中的位置.

3. 孩子兄弟表示法

a. 含义

用链表表示一棵树, 其中的每个结点由数据域和两个指针组成, 这两个指针分别指向当前结点的第一个孩子和当前结点的下一个兄弟. 由此将一个树连接起来.

b. 代码

1
2
3
4
5
typedef struct TNode
{
    DataType data;
    struct TNode * firstchild, * nextsibling;
}TNode, * PTNode;

c. 优缺点

存储更加灵活, 比较常用.

二. 森林和二叉树的转换

1. 树和二叉树之间的转换

二叉树中的结点指向左右子树, 而树中的结点指向第一个孩子和下一个兄弟, 虽然在理解上不一样, 但是在物理存储上, 两种方式是一样的. 也就是说, 树和二叉树之间不用做任何转换, 只需要将树结点的第一个孩子看成二叉树结点的左子树, 树结点的下一个兄弟看成二叉树结点的右子树即可.

2. 森林转换为二叉树

  • 如果森林为空, 则二叉树也为空.
  • 如果森林不为空, 则森林的第一棵树的根结点作为二叉树的根节点, 第一棵树的子树作为二叉树的左子树, 剩下的树作为二叉树的右子树, 以此类推.

3. 二叉树转换为森林

  • 如果二叉树为空, 森林也为空.
  • 如果二叉树不为空, 二叉树的根以及左子树作为森林的第一棵树, 右子树继续转换为森林, 以此类推.

三. 树和森林的遍历

1. 树的遍历

a. 先根遍历

先访问根节点, 然后依次访问根的每棵子树.

b. 后根遍历

先遍历根的每棵子树, 然后再访问根.
(注意是结点和结点之间是父子关系还是兄弟关系)

##　２. 森林的遍历

a. 先序遍历森林

  • 先访问第一棵树的根
  • 先序遍历第一棵树的根结点的子树森林
  • 先序遍历除第一棵树以外的树组成的森林

b. 中序遍历森林

  • 先遍历第一棵树的根结点的子树森林
  • 访问第一棵树的根节点
  • 中序遍历除第一棵树以外的树组成的森林

(森林的遍历即多棵树的遍历)