Skip to content

Latest commit

 

History

History
177 lines (146 loc) · 6.59 KB

13 树和森林的遍历.md

File metadata and controls

177 lines (146 loc) · 6.59 KB

#数据结构 #C

[51] 树的存储结构

0.树的基本概念

树是 $n(n ≥ 0)$ 个结点的有限集合。当 $n = 0$ 时，称为空树，这是一种特殊情况。
因此在任意一棵非空树中应满足：

  1. 有且仅有一个特定的称为根的结点。
  2. 当 $n > 1$ 时，其余结点可分为 $m(m > 0)$ 个互不相交的有限集合 $T_1, T_2,…, T_m$ ，其中每个集合本身又是一棵树，并且称为根结点的子树。

1.双亲表示法

每个结点中保存指向双亲的“指针”。

#define MAX_TREE_SIZE 100   // 树中最多的结点
typedef struct {        // 树的结点定义
    ElemType data;      // 数据元素
    int parent;         // 双亲位置域
} PTNode;

typedef struct {                // 树的类型定义
    PTNode node[MAX_TREE_SIZE]; // 双亲表示
    int n;                      // 结点树
} PTree;

上述树结构，可以使用这个表格中的数据结点表示。

数组下标 data parent
0 A -1
1 B 0
2 C 0
3 D 0
4 E 1
5 F 1
6 G 2
7 H 3
8 I 3
9 J 3
10 K 4
11 ... ...

其中，根结点固定存储在0，-1表示没有双亲。

问题来了，如何让用双亲表示法实现增删查操作？ 新增数据元素时候，无需按逻辑上的次序存储，直接在尾部新增即可。例如新增M、L结点，只需要在尾部新增即可。

数组下标 data parent
.......... ...... ........
11 M 7
12 L 4

删除数据元素，如果是叶子结点的话，可以直接删除元素，也可以只让data值删除。 如果不是叶子结点，删除的时候，就需要找到它的所有孩子结点并且全部删除。但是，查找指定结点的孩子只能从头遍历。

  • 优点：查指定 结点的双亲很方便
  • 缺点：查指定 结点的孩子只 能从头遍历

2.孩子表示法

采用顺序+链式存储，顺序存储各个结点，每个结点中保存孩子链表头指针。

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;               // 结点数和根的位置
}

3.孩子兄弟表示法

纯粹使用链表的方式存储：

// 树的存储 -- 孩子兄弟表示法
typeddef struct CSNode {
    ElemType data;                           // 数据域
    struct CSNode *firstchild, *nextSibling; // 第一个孩子和右兄弟指针
} CSNode, *CSTree;

这样的表示方法和二叉树形式同构，可以看作是左指针和右指针表示法。

如图，树转化的二叉树中，某个结点的左右两叉完全属于不同层次。 左叉（蓝色线）为孩子，右叉（黄色线）为兄弟，沿着黄色线一直追溯即可把所有的同层次的结点全找到。相对应的，二叉树也可以复原成原来树的逻辑结构。

4.森林与二叉树转化

把森林中所有的根结点全都视为兄弟。

相对应的，二叉树也可以复原成原来森林的逻辑结构。

[52] 树和森林的遍历

1.树的遍历

树的遍历有以下几种方式：先根遍历、后根遍历、层次遍历。

1.先根遍历

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

// 树的先根遍历
void PreOrder (TreeNode *R)
{
    if (R != NULL) {
        visit(R);       // 访问根结点
        while( R 还有下一个子树T ){
            PreOrder(T); // 先根遍历下一个子树
        }
    }
}

树的先根遍历序列与这棵树转化形成的相应二叉树的先序序列相同。
如下这个树的先根遍历序列是：ABEKFCGDHIJ。

2.后根遍历

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

// 树的先根遍历
void PostOrder (TreeNode *R)
{
    if (R != NULL) {
        while( R 还有下一个子树T ){
            PostOrder(T); // 后根遍历下一个子树
        }
        visit(R);         // 访问根结点
    }
}

树的后根遍历序列与这棵树转化形成的相应二叉树的中序序列相同。
如下这个数的先根遍历序列是：KEFBCGDHIJA。

3.层次遍历

使用队列实现：
（1） 若树非空，则根结点入队；
（2） 若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队；
（3） 重复（2）直到队列为空。

对树的层次遍历可以称作是对树的广度优先遍历(Breadth_First_Search)，对树的先根遍历、后跟遍历是对树的深度优先遍历(Depth_First_Search)。

2.森林的遍历

1.先序遍历森林

若森林为非空，则按如下规则进行遍历：
（1）访问森林中第一棵树的根结点。
（2）先序遍历第一棵树中根结点的子树森林。
（3）先序遍历除去第一棵树之后剩余的树构成的森林。

对森林的先序遍历，效果等同于依次对各个树进行先根遍历，实质上，等同于依次对二叉树的先序遍历。 上图中森林的先序遍历是 BEKFCGDHMIJ。

2.中序遍历森林

若森林为非空，则按如下规则进行遍历：
（1）中序遍历森林中第一棵树的根结点的子树森林。
（2）访问第一棵树的根结点。
（3）中序遍历除去第一棵树之后剩余的树构成的森林。

对森林的先序遍历，效果等同于依次对各个树进行后根遍历，实质上，等同于依次对二叉树的中序遍历。上图中森林的中序遍历是 KEFBGCMHIJD。
总结，树、森林的遍历与其转化成二叉树遍历的对应关系：

树 森林 二叉树
先根遍历 先序遍历 先序遍历
后根遍历 中序遍历 中序遍历