数据结构（王道）——数据结构之 二叉树的存储结构

**数据结构之二叉树的存储结构**

二叉树是一种常见的数据结构，它在计算机科学中有着广泛的应用。二叉树的定义是：每个结点最多有两个子结点，分别称为左孩子和右孩子。在本文中，我们将讨论二叉树的存储结构。

**二叉树的基本概念**

二叉树由结点组成，每个结点包含以下信息：

* **值（Value）**：每个结点所代表的数据。
* **左孩子（Left Child）**：指向左子结点的指针。
* **右孩子（Right Child）**：指向右子结点的指针。

二叉树的存储结构可以分为两种：

1. **链式存储结构**：每个结点都有一个指向其左孩子和右孩子的指针。
2. **数组存储结构**：使用一个一维数组来表示二叉树，每个元素代表一个结点。

在本文中，我们将重点讨论链式存储结构。

**链式存储结构**

链式存储结构是最常见的二叉树存储结构。每个结点都有一个指向其左孩子和右孩子的指针。这种结构可以很方便地插入、删除结点。

下面是一个简单的例子：

ctypedef struct Node {
 int value;
 struct Node* left;
 struct Node* right;
} Node;

Node* createNode(int value) {
 Node* node = (Node*)malloc(sizeof(Node));
 node->value = value;
 node->left = NULL;
 node->right = NULL;
 return node;
}

void insertNode(Node** root, int value) {
 if (*root == NULL) {
 *root = createNode(value);
 return;
 }

 if (value < (*root)->value) {
 insertNode(&(*root)->left, value);
 } else if (value > (*root)->value) {
 insertNode(&(*root)->right, value);
 }
}

void printTree(Node* root) {
 if (root == NULL) return;

 printTree(root->left);
 printf("%d ", root->value);
 printTree(root->right);
}

在这个例子中，我们定义了一个 `Node` 结构体来表示每个结点。我们还定义了一个 `createNode` 函数来创建新结点，一个 `insertNode` 函数来插入新结点，并且一个 `printTree` 函数来打印二叉树。

**数组存储结构**

数组存储结构使用一个一维数组来表示二叉树，每个元素代表一个结点。这种结构可以很方便地实现一些特定的操作，如查找最小值或最大值。

下面是一个简单的例子：

ctypedef struct {
 int* array;
 int size;
} ArrayTree;

ArrayTree* createArrayTree(int capacity) {
 ArrayTree* tree = (ArrayTree*)malloc(sizeof(ArrayTree));
 tree->array = (int*)malloc(capacity * sizeof(int));
 tree->size =0;
 return tree;
}

void insertNode(ArrayTree* tree, int value) {
 if (tree->size == tree->array[0]) {
 // resize array int* newArray = (int*)realloc(tree->array, (tree->size +1) * sizeof(int));
 tree->array = newArray;
 }

 tree->array[tree->size++] = value;
}

void printTree(ArrayTree* tree) {
 for (int i =0; i < tree->size; i++) {
 printf("%d ", tree->array[i]);
 }
}

在这个例子中，我们定义了一个 `ArrayTree` 结构体来表示二叉树。我们还定义了一个 `createArrayTree` 函数来创建新二叉树，一个 `insertNode` 函数来插入新结点，并且一个 `printTree` 函数来打印二叉树。

**总结**

在本文中，我们讨论了二叉树的存储结构。我们重点介绍了链式存储结构和数组存储结构。链式存储结构是最常见的二叉树存储结构，每个结点都有一个指向其左孩子和右孩子的指针。数组存储结构使用一个一维数组来表示二叉树，每个元素代表一个结点。

我们还提供了两个例子，分别演示链式存储结构和数组存储结构的实现。这些例子可以帮助读者更好地理解二叉树的存储结构及其应用。

**参考**

* 《数据结构与算法分析》(第2 版) - Mark Allen Weiss* 《算法导论》(第3 版) - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein