树、二叉树（C语言版）详解

**树、二叉树详解**

**前言**

在计算机科学中，树是一种常见的数据结构，它可以用来表示复杂的关系或结构。二叉树是树的一种特殊形式，它每个结点最多有两个子结点。二叉树广泛应用于算法设计、数据库管理等领域。

**什么是树**

树是一种非线性的数据结构，通常用来表示复杂的关系或结构。它由一组结点和这些结点之间的边组成，每个结点代表一个元素或值。树可以看作是一个有序集合，每个结点都有一个唯一的标识符。

**什么是二叉树**

二叉树是一种特殊的树，它每个结点最多有两个子结点。也就是说，一个结点可以有左孩子和右孩子，但不能有其他孩子。二叉树的结构如下：

 A / 
 B C /  / 
D E F G

在这个例子中，A是根结点，B、C是其孩子结点，D、E、F、G是其孙结点。

**二叉树的定义**

二叉树可以用以下定义来描述：

* 每个结点最多有两个子结点（左孩子和右孩子）。
* 每个结点都有一个唯一的标识符。
* 每个结点都有一个父结点，除了根结点外。

**二叉树的类型**

二叉树可以分为以下几种类型：

* **满二叉树**：每个结点都有两个子结点，除非它是叶结点。
* **完全二叉树**：对于任意结点，如果其左孩子存在，则其右孩子也一定存在。
* **平衡二叉树**：对于任意结点，其左右子树的高度差不超过1。

**二叉树的应用**

二叉树广泛应用于算法设计、数据库管理等领域。例如：

* **排序算法**：二叉树可以用来实现快速排序和堆排序。
* **查找算法**：二叉树可以用来实现二分查找和平衡查找。
* **数据库管理**：二叉树可以用来实现索引结构和缓存机制。

**C语言版的二叉树**

下面是C语言版的二叉树的基本结构：

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

typedef struct BinaryTree {
 Node *root;
} BinaryTree;

在这个例子中，我们定义了一个结点结构体`Node`，它包含一个数据域和两个指针域（左孩子和右孩子）。我们还定义了一个二叉树结构体`BinaryTree`，它包含一个根结点的指针。

**创建二叉树**

下面是创建二叉树的例子：

cvoid createBinaryTree(BinaryTree *tree) {
 Node *root = (Node *)malloc(sizeof(Node));
 root->data =1;
 root->left = NULL;
 root->right = NULL;

 tree->root = root;
}

在这个例子中，我们创建一个根结点，并将其赋值给二叉树的根结点。

**插入结点**

下面是插入结点的例子：

cvoid insertNode(BinaryTree *tree, int data) {
 Node *newNode = (Node *)malloc(sizeof(Node));
 newNode->data = data;
 newNode->left = NULL;
 newNode->right = NULL;

 if (tree->root == NULL) {
 tree->root = newNode;
 } else {
 insertNodeRecursive(tree->root, newNode);
 }
}

void insertNodeRecursive(Node *currentNode, Node *newNode) {
 if (newNode->data < currentNode->data) {
 if (currentNode->left == NULL) {
 currentNode->left = newNode;
 } else {
 insertNodeRecursive(currentNode->left, newNode);
 }
 } else {
 if (currentNode->right == NULL) {
 currentNode->right = newNode;
 } else {
 insertNodeRecursive(currentNode->right, newNode);
 }
 }
}

在这个例子中，我们创建一个新结点，并将其插入到二叉树中。我们使用递归函数来实现这一点。

**查找结点**

下面是查找结点的例子：

cNode *findNode(BinaryTree *tree, int data) {
 if (tree->root == NULL) {
 return NULL;
 }

 Node *currentNode = tree->root;

 while (currentNode != NULL) {
 if (data < currentNode->data) {
 currentNode = currentNode->left;
 } else if (data > currentNode->data) {
 currentNode = currentNode->right;
 } else {
 return currentNode;
 }
 }

 return NULL;
}

在这个例子中，我们使用一个循环来查找结点。我们从根结点开始，并沿着左孩子或右孩子移动，直到找到匹配的结点。

**删除结点**

下面是删除结点的例子：

cvoid deleteNode(BinaryTree *tree, int data) {
 tree->root = deleteNodeRecursive(tree->root, data);
}

Node *deleteNodeRecursive(Node *currentNode, int data) {
 if (currentNode == NULL) {
 return currentNode;
 }

 if (data < currentNode->data) {
 currentNode->left = deleteNodeRecursive(currentNode->left, data);
 } else if (data > currentNode->data) {
 currentNode->right = deleteNodeRecursive(currentNode->right, data);
 } else {
 //一个结点没有孩子 if (currentNode->left == NULL && currentNode->right == NULL) {
 free(currentNode);
 return NULL;
 }
 //一个结点有左孩子 else if (currentNode->left == NULL) {
 Node *temp = currentNode->right;
 free(currentNode);
 return temp;
 }
 //一个结点有右孩子 else if (currentNode->right == NULL) {
 Node *temp = currentNode->left;
 free(currentNode);
 return temp;
 }
 //一个结点有左孩子和右孩子 else {
 Node *temp = findMinNode(currentNode->right);
 currentNode->data = temp->data;
 currentNode->right = deleteNodeRecursive(currentNode->right, temp->data);
 }
 }

 return currentNode;
}

Node *findMinNode(Node *currentNode) {
 while (currentNode->left != NULL) {
 currentNode = currentNode->left;
 }

 return currentNode;
}

在这个例子中，我们使用递归函数来删除结点。我们首先找到匹配的结点，然后根据其孩子的情况进行处理。

**总结**

在本文中，我们详细介绍了树和二叉树的概念、定义和应用。我们还提供了C语言版的二叉树的基本结构和相关函数，包括创建、二叉树、插入结点、查找结点和删除结点等功能。