二叉树链式存储详解
前言
二叉树是数据结构中一个非常重要的概念,它广泛应用于各种算法和程序设计中。在C语言中,我们可以使用链式存储的方式来实现二叉树。本文将详细介绍如何使用C语言实现二叉树的链式存储,并提供相关的代码示例,帮助初学者更好地理解和掌握二叉树的相关知识。
二叉树的基本概念
在正式介绍二叉树的链式存储之前,我们先来回顾一下二叉树的基本概念。
二叉树是一种特殊的树形结构,它的每个节点最多只能有两个子节点,分别称为左子节点和右子节点。二叉树的子树有左右之分,其次序不能颠倒。二叉树的第一个节点称为根节点,根节点的子树称为左子树和右子树。
二叉树具有以下特点:
- 每个节点最多有两个子节点,即左子节点和右子节点。
- 左子树和右子树是有顺序的,次序不能随意颠倒。
- 即使树中某节点只有一个子节点,也要区分它是左子节点还是右子节点。
二叉树节点的定义
在使用链式存储实现二叉树时,我们需要先定义二叉树节点的结构体。每个节点包含三个部分:数据域、左子节点指针和右子节点指针。
typedef struct TreeNode {
int val; // 数据域
struct TreeNode *left; // 左子节点指针
struct TreeNode *right; // 右子节点指针
} TreeNode;
在上面的代码中,我们定义了一个名为TreeNode
的结构体,它包含一个整型变量val
表示节点的数据,以及两个指向TreeNode
类型的指针left
和right
,分别表示节点的左子节点和右子节点。
创建二叉树节点
有了二叉树节点的定义,我们就可以编写一个函数来创建新的二叉树节点了。
TreeNode* createNode(int val) {
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
newNode->val = val;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
在上面的代码中,我们定义了一个名为createNode
的函数,它接受一个整型参数val
,表示要创建的节点的数据。函数内部首先使用malloc
函数动态分配一个TreeNode
类型的内存空间,然后将val
赋值给新节点的数据域,并将左右子节点指针初始化为NULL
,最后返回新创建的节点。
插入节点
创建了新的节点后,我们需要将其插入到二叉树中的适当位置。以下是一个递归实现的插入函数:
void insertNode(TreeNode** root, int val) {
if (*root == NULL) {
*root = createNode(val);
} else {
if (val < (*root)->val) {
insertNode(&((*root)->left), val);
} else if (val > (*root)->val) {
insertNode(&((*root)->right), val);
}
}
}
在上面的代码中,insertNode
函数接受两个参数:一个指向指针的指针root
,表示要插入节点的二叉树的根节点;一个整型变量val
,表示要插入的节点的数据。
函数首先判断根节点是否为NULL
,如果是,则直接将新节点作为根节点插入。否则,函数会比较要插入的节点的数据与当前节点的数据大小,如果小于当前节点,则递归地在左子树中插入新节点;如果大于当前节点,则递归地在右子树中插入新节点。
二叉树的遍历
二叉树的遍历是指按照某种顺序访问二叉树中的每个节点,使得每个节点都被访问且只被访问一次。二叉树有三种常见的遍历方式:前序遍历、中序遍历和后序遍历。
前序遍历
前序遍历的顺序是:根节点 -> 左子树 -> 右子树。
void preorderTraversal(TreeNode* root) {
if (root != NULL) {
printf("%d ", root->val);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
}
中序遍历
中序遍历的顺序是:左子树 -> 根节点 -> 右子树。
void inorderTraversal(TreeNode* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->val);
inorderTraversal(root->right);
}
}
后序遍历
后序遍历的顺序是:左子树 -> 右子树 -> 根节点。
void postorderTraversal(TreeNode* root) {
if (root != NULL) {
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->val);
}
}
示例程序
下面是一个完整的示例程序,展示了如何使用C语言实现二叉树的链式存储,并进行插入和遍历操作。
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
TreeNode* createNode(int val) {
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
newNode->val = val;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
void insertNode(TreeNode** root, int val) {
if (*root == NULL) {
*root = createNode(val);
} else {
if (val < (*root)->val) {
insertNode(&((*root)->left), val);
} else if (val > (*root)->val) {
insertNode(&((*root)->right), val);
}
}
}
void preorderTraversal(TreeNode* root) {
if (root != NULL) {
printf("%d ", root->val);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
}
void inorderTraversal(TreeNode* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->val);
inorderTraversal(root->right);
}
}
void postorderTraversal(TreeNode* root) {
if (root != NULL) {
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->val);
}
}
int main() {
TreeNode* root = NULL;
insertNode(&root, 5);
insertNode(&root, 3);
insertNode(&root, 7);
insertNode(&root, 1);
insertNode(&root, 9);
printf("前序遍历: ");
preorderTraversal(root);
printf("\n");
printf("中序遍历: ");
inorderTraversal(root);
printf("\n");
printf("后序遍历: ");
postorderTraversal(root);
printf("\n");
return 0;
}
在上面的示例程序中,我们首先定义了二叉树节点的结构体TreeNode
,然后实现了创建节点的函数createNode
和插入节点的函数insertNode
。接着,我们实现了三种遍历方式的函数:preorderTraversal
(前序遍历)、inorderTraversal
(中序遍历)和postorderTraversal
(后序遍历)。
在main
函数中,我们创建了一个空的二叉树,然后通过insertNode
函数插入了几个节点。最后,我们分别调用三种遍历函数,打印出二叉树的前序遍历、中序遍历和后序遍历结果。
运行该程序,输出结果如下:
前序遍历: 5 3 1 7 9
中序遍历: 1 3 5 7 9
后序遍历: 1 3 9 7 5
可以看到,程序正确地实现了二叉树的链式存储,并按照不同的遍历方式输出了二叉树的节点值。
总结
本文详细介绍了如何使用C语言实现二叉树的链式存储,包括二叉树节点的定义、创建节点、插入节点以及三种常见的遍历方式(前序遍历、中序遍历和后序遍历)。通过示例程序,我们展示了如何将这些概念应用到实际的编程中。
对于初学者来说,理解和掌握二叉树的链式存储是学习数据结构和算法的重要一步。希望本文能够对你有所帮助,让你更好地理解二叉树的相关知识。如果你有任何问题或建议,欢迎留言交流。