二叉树的基本数据结构类型（c语言）
二叉树基本数据结构与实现总结
数据结构设计
一、树节点结构
typedef struct TreeNode {
eleType val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
说明:
- 成员变量:
val: 节点的值（类型为eleType，此处定义为char）。left和right: 指向左右子节点的指针，分别表示节点的左子树和右子树。
- 用途:
- 表示树的基本组成单元，每个节点存储数据并连接到其左右子节点。
二、树的整体结构
typedef struct Tree {
TreeNode* nodes; // 存储所有节点的数组
TreeNode* root; // 指向树的根节点
size_t nodeSize; // 树的节点总数
} Tree;
说明:
- 成员变量:
nodes: 动态分配的TreeNode数组，用于存储树的所有节点。root: 指向根节点，表示二叉树的入口。nodeSize: 记录树中节点的总数量。
- 用途:
- 包装整个二叉树的结构，提供统一管理节点及树的接口。
三、树的基本操作
3.1. 初始化树
void Init_Tree(Tree* T, int size)
{
T->nodeSize = size;
T->nodes = (TreeNode*)malloc(sizeof(TreeNode) * size);
T->root = NULL;
}
功能:
- 动态分配内存以存储 size 个节点。
- 初始化树的节点数组、根节点指针以及节点数量。
关键点:
- 动态分配内存时，需保证后续释放操作。
- root 设置为 NULL 表示树为空。
3.2. 销毁树
void Destory_Tree(Tree* T)
{
free(T->nodes);
T->nodes = NULL;
T->nodeSize = 0;
T->root = NULL;
}
功能:
- 释放动态分配的内存，清空树的所有数据。
关键点:
- 指针置为
NULL，避免悬空指针问题。
3.3. 获取节点
TreeNode* GetNode_Tree(Tree* T, int id)
{
return &T->nodes[id];
}
功能:
- 根据节点的下标直接访问节点数组中的节点。
关键点:
- 数组下标需在合法范围内，否则可能访问无效内存。
3.4. 创建二叉树
递归创建函数
//a-->元素数组，nodeId-->根节点下标, Nullnode-->空节点标识符
TreeNode* Creat_Recursively(Tree* T, eleType a[], int size, int nodeId, eleType NullNode)
{
if (nodeId >= size || a[nodeId] == NullNode)
{
return NULL;
}
TreeNode* nowNode = GetNode_Tree(T, nodeId);
nowNode->val = a[nodeId];
nowNode->left = Creat_Recursively(T, a, size, nodeId * 2, NullNode);
nowNode->right = Creat_Recursively(T, a, size, nodeId * 2 + 1, NullNode);
return nowNode;
}
功能:
- 按照完全二叉树的层序布局递归创建节点。
实现逻辑:
1）：递归终止条件：
当节点超出数组范围，或节点值为 NullNode 时，返回空树（NULL）。
2）：创建当前节点:
从节点数组中获取节点并赋值。
3）：递归创建子树:
递归调用自身，分别创建左子树（nodeId * 2）和右子树（nodeId * 2 + 1）。
注意:
- 输入数组需按照完全二叉树的顺序存储，根节点下标从 1 开始。
3.5封装创建函数
void Creat_binaryTree(Tree* T, eleType a[], int size, eleType nullNode)
{
T->root = Creat_Recursively(T, a, size, 1, nullNode);
}
功能:
- 对递归创建函数进行封装，默认从根节点开始。
四. 遍历二叉树
4.1、前序遍历
void preOrder(Tree* T, TreeNode* node)
{
if (node)
{
visit(node);
preOrder(T, node->left);
preOrder(T, node->right);
}
}
顺序:
- 根 -> 左子树 -> 右子树
4.2、中序遍历
void InOrder(Tree* T, TreeNode* node)
{
if (node)
{
InOrder(T, node->left);
visit(node);
InOrder(T, node->right);
}
}
顺序:
- 左子树 -> 根 -> 右子树
4.3、后序遍历
void PostOrder(Tree* T, TreeNode* node)
{
if (node)
{
PostOrder(T, node->left);
PostOrder(T, node->right);
visit(node);
}
}
顺序:
- 左子树 -> 右子树 -> 根
主函数
int main()
{
const char nullNode = '*';
char a[24] = {
nullNode,'-','+','/','a',
'x','e','f',nullNode,nullNode,
'b','-',nullNode,nullNode,nullNode,
nullNode,nullNode,nullNode,nullNode,nullNode,
nullNode,nullNode,'c','d'
};
Tree T;
Init_Tree(&T, 24);
Creat_binaryTree(&T, a, 24, nullNode);
printf("前序遍历：");
preOrder(&T, T.root);
printf("\n");
printf("中序遍历：");
InOrder(&T, T.root);
printf("\n");
printf("后序遍历：");
PostOrder(&T, T.root);
printf("\n");
Destory_Tree(&T);
system("pause");
return 0;
}
功能:
- 创建并初始化一个二叉树。
- 使用不同遍历方式输出节点值。
五、结果演示：
六、总结
-
基本数据结构:
- 树节点由
TreeNode结构体表示，包含数据与左右子节点指针。 - 树由
Tree结构体管理，提供统一的入口和操作方法。
- 树节点由
-
树的操作:
- 包含初始化、销毁、节点访问、递归创建与遍历操作，覆盖了二叉树的主要功能。
-
实现技巧:
- 使用数组模拟完全二叉树，方便递归创建。
- 遍历函数通过递归实现，逻辑清晰简洁。