在树形数据结构中，二叉树是最常见的一种，但有时我们需要每个节点有三个子节点，这时就可以使用三叉树。三叉树是一种每个节点最多拥有三个子节点（左子树、中子树、右子树）的树结构。本文将介绍三叉树的基本概念，并通过 C 语言示例代码展示如何实现创建、插入、遍历以及释放三叉树。
1. 三叉树的基本概念
在三叉树中，每个节点包含三个指向子节点的指针：
- 左子节点（left）
- 中子节点（middle）
- 右子节点（right）
三叉树可以用于解决某些特殊场景的问题，比如在数据分类时，根据某种规则将数据分为三种情况。示例中，我们采用如下简单规则：
- 如果待插入数据小于当前节点数据，插入左子树；
- 如果等于当前节点数据，插入中子树；
- 如果大于当前节点数据，插入右子树。
2. 数据结构定义
首先，我们需要定义一个表示三叉树节点的结构体。节点包含数据域和三个指针域。
#include <stdio.h>
#include <stdlib.h>typedef struct TreeNode {int data;struct TreeNode* left;struct TreeNode* middle;struct TreeNode* right;
} TreeNode;
3. 详细代码示例
以下代码示例展示了如何在 C 语言中实现三叉树，包括节点的创建、插入节点、先序遍历和内存释放等功能。
#include <stdio.h>
#include <stdlib.h>// 三叉树节点结构体定义
typedef struct TreeNode {int data;struct TreeNode* left;struct TreeNode* middle;struct TreeNode* right;
} TreeNode;// 创建新节点
TreeNode* createNode(int data) {TreeNode* newNode = (TreeNode*) malloc(sizeof(TreeNode));if (newNode == NULL) {printf("内存分配错误\n");exit(1);}newNode->data = data;newNode->left = newNode->middle = newNode->right = NULL;return newNode;
}// 插入节点函数：根据数据大小选择插入左、中或右子树
void insert(TreeNode** root, int data) {if (*root == NULL) {*root = createNode(data);return;}// 示例规则：小于放左子树，等于放中子树，大于放右子树if (data < (*root)->data) {insert(&((*root)->left), data);} else if (data == (*root)->data) {insert(&((*root)->middle), data);} else {insert(&((*root)->right), data);}
}// 先序遍历三叉树：访问顺序为当前节点、左子树、中子树、右子树
void preOrder(TreeNode* root) {if (root == NULL)return;printf("%d ", root->data);preOrder(root->left);preOrder(root->middle);preOrder(root->right);
}// 释放三叉树所占用的内存
void freeTree(TreeNode* root) {if (root == NULL)return;freeTree(root->left);freeTree(root->middle);freeTree(root->right);free(root);
}int main() {TreeNode* root = NULL;// 插入一些示例数据insert(&root, 5);insert(&root, 3);insert(&root, 7);insert(&root, 5);insert(&root, 2);insert(&root, 8);insert(&root, 6);insert(&root, 5);printf("三叉树的先序遍历结果:\n");preOrder(root);printf("\n");// 释放内存freeTree(root);return 0;
}
4. 代码讲解
-
创建节点：
createNode函数负责分配内存并初始化一个新节点，将三个子节点指针都置为空。 -
节点插入：
insert函数采用递归方式，将数据插入到正确的位置。示例中采用简单比较规则：- 数据小于当前节点值则插入左子树；
- 等于则插入中子树；
- 大于则插入右子树。
-
先序遍历：
preOrder函数采用递归方式先访问当前节点，再依次遍历左、中、右子树。遍历结果会依次输出每个节点的数据。 -
内存释放：
freeTree函数递归释放每个节点的内存，防止内存泄漏。
5. 总结
通过本文介绍，我们了解了三叉树的基本概念以及如何用 C 语言实现三叉树的创建、插入、遍历和内存管理。该示例为初学者提供了一个清晰的实践案例，帮助大家更好地掌握树形数据结构在 C 语言中的实现方法。当然，实际应用中，三叉树的插入规则、平衡调整等可以根据需求进一步扩展和完善。
