数据结构与C

数据结构与C 知识量:8 - 24 - 99

5.3 树与森林><

双亲表示法- 5.3.1 -

双亲表示法是树的一种存储方式,主要利用了树的这个性质,在存储结点信息的同时,在每个节点中附设一个指向其双亲的指针,指向双亲在链表中的位置。这种结构一般借助数组来实现,这样的链表也称为静态链表。

以下是双亲表示法在C语言中的存储结构定义:

#define MAX_TREE_SIZE 100 // 最大树节点数  
  
typedef struct TreeNode {  
    int data; // 节点数据  
    int parentIndex; // 双亲节点在数组中的索引  
    struct TreeNode *leftChild; // 左孩子指针  
    struct TreeNode *rightChild; // 右孩子指针  
} TreeNode;  
  
// 初始化二叉树  
void initTree(TreeNode *tree, int size) {  
    for (int i = 0; i < size; i++) {  
        tree[i].parentIndex = -1; // 初始时,所有节点的双亲为空  
        tree[i].leftChild = NULL; // 初始时,所有节点的左孩子为空  
        tree[i].rightChild = NULL; // 初始时,所有节点的右孩子为空  
    }  
}

在上述代码中,定义了一个TreeNode结构体来表示二叉树的节点。每个节点包含一个data字段表示节点的数据,一个parentIndex字段表示该节点的双亲节点在数组中的索引,以及两个指针字段leftChild和rightChild分别表示该节点的左孩子和右孩子。

在initTree函数中,初始化所有节点的双亲为空,左孩子和右孩子也为空。

孩子表示法- 5.3.2 -

孩子表示法是一种二叉树的存储结构,每个节点有两个指针,一个指向第一个孩子,一个指向下一个兄弟。这种表示法适用于需要频繁查找孩子节点的操作,因为在孩子表示法中查找孩子节点的操作的时间复杂度为O(1)。然而,孩子表示法不适用于需要频繁查找父节点的操作,因为在孩子表示法中查找父节点的操作的时间复杂度为O(n)。

孩子表示法在C语言中的存储结构定义如下:

#define MAX_TREE_SIZE 100 // 最大树节点数  
  
typedef struct TreeNode {  
    int data; // 节点数据  
    struct TreeNode *firstChild; // 第一个孩子节点指针  
    struct TreeNode *nextSibling; // 下一个兄弟节点指针  
} TreeNode;

在上述代码中,定义了一个TreeNode结构体来表示二叉树的节点。每个节点包含一个data字段表示节点的数据,以及两个指针字段firstChild和nextSibling分别表示该节点的第一个孩子节点和下一个兄弟节点。

孩子兄弟表示法- 5.3.3 -

孩子兄弟表示法是一种二叉树的存储结构,它采用一个记录孩子和兄弟信息的链表来表示二叉树。每个节点包含三个指针:一个指向第一个孩子节点,一个指向下一个兄弟节点,还有一个指向其父节点。

这种表示法的优点是:

  • 查找孩子节点和兄弟节点的时间复杂度都是O(1)。

  • 查找父节点的时间复杂度也是O(1)。

孩子兄弟表示法的存储结构定义如下:

#define MAX_TREE_SIZE 100 // 最大树节点数  
  
typedef struct TreeNode {  
    int data; // 节点数据  
    struct TreeNode *firstChild; // 第一个孩子节点指针  
    struct TreeNode *nextSibling; // 下一个兄弟节点指针  
    struct TreeNode *parent; // 父节点指针  
} TreeNode;

在上述代码中,定义了一个TreeNode结构体来表示二叉树的节点。每个节点包含一个data字段表示节点的数据,以及三个指针字段firstChild、nextSibling和parent分别表示该节点的第一个孩子节点、下一个兄弟节点和父节点。

森林- 5.3.4 -

森林是一个由若干棵互不相交的树组成的集合。这些树之间没有父子关系,也就是说它们没有共享任何节点。每个树都可以独立地进行遍历,而不需要考虑其他树的结构。

森林的概念可以用来描述一些现实世界中的问题,例如文件系统、社交网络等。在这些场景中,每个节点代表一个实体,而边则表示这些实体之间的关系。如果我们将这些实体看作是树,那么整个系统就可以被看作是一个森林。

森林通常是用二叉树的逻辑结构来表示的。在这种情况下,每个树都是一个二叉树,而整个森林就是由这些二叉树组成的集合。这种表示方法可以方便地实现各种树的操作,例如插入、删除、查找等。

需要注意的是,森林中的树可以是任意类型的树,包括二叉树、多叉树等。因此,森林的概念和含义是非常广泛的,可以用来描述各种不同的数据结构和算法问题。