C语言实现二叉树的创建遍历

### C语言实现二叉树的创建与遍历 在计算机科学中，二叉树是一种重要的数据结构，它具有丰富的应用场景，比如文件系统、编译器的设计等。本篇文章将详细介绍如何使用C语言来实现二叉树的基本操作：创建与遍历。 #### 一、二叉树简介 二叉树（Binary Tree）是每个节点最多有两个子节点的树结构。通常子节点被称作“左子节点”和“右子节点”。二叉树是由节点组成的集合，该集合要么为空集（称为空二叉树），要么由一个根节点及两棵分别称为左子树和右子树的不相交的二叉树组成。 #### 二、C语言中的二叉树定义 在C语言中，可以通过结构体来定义二叉树节点。例如： ```c typedef struct T_NODE { char elem; // 节点存储的数据 struct T_NODE *lc, *rc; // 左子节点指针和右子节点指针 } T_NODE, *T_tree; ``` 这里定义了一个名为`T_NODE`的结构体类型，其中包含一个字符型数据`elem`用于存储节点的值，两个指向同类型结构体的指针`lc`和`rc`分别表示左子节点和右子节点。 #### 三、二叉树的创建 二叉树的创建可以采用递归的方式进行。具体实现代码如下： ```c void creat_T(T_tree &tree) { char e; e = getchar(); // 输入节点值 if (e == '\n') { // 输入结束符，表示创建结束 tree = NULL; } else { tree = (T_tree)malloc(sizeof(T_NODE)); // 分配内存 tree->elem = e; // 设置节点值 creat_T(tree->lc); // 递归创建左子树 creat_T(tree->rc); // 递归创建右子树 } } ``` 此函数通过递归调用自身来构建整棵树。当输入为换行符时，创建结束，返回空指针。否则，创建一个新的节点，并递归地创建左右子树。 #### 四、二叉树的遍历 遍历是访问二叉树中所有节点的过程。常见的遍历方法有三种：前序遍历、中序遍历和后序遍历。 1. **前序遍历**：访问顺序为“根—左—右”。 2. **中序遍历**：访问顺序为“左—根—右”。 3. **后序遍历**：访问顺序为“左—右—根”。 本例中实现了中序遍历，代码如下： ```c void bl(T_tree p) { if (p != NULL) { bl(p->lc); // 先遍历左子树 printf("%c", p->elem); // 访问根节点 bl(p->rc); // 再遍历右子树 } } ``` 中序遍历首先递归遍历左子树，然后访问根节点，最后递归遍历右子树。 #### 五、完整程序示例 下面是完整的C语言程序，实现了二叉树的创建与中序遍历： ```c #include <stdio.h> #include <malloc.h> typedef struct T_NODE { char elem; struct T_NODE *lc, *rc; } T_NODE, *T_tree; void creat_T(T_tree &tree) { char e; e = getchar(); if (e == '\n') { tree = NULL; } else { tree = (T_tree)malloc(sizeof(T_NODE)); tree->elem = e; creat_T(tree->lc); creat_T(tree->rc); } } void bl(T_tree p) { if (p != NULL) { bl(p->lc); printf("%c", p->elem); bl(p->rc); } } int main() { T_tree A, p; printf("请输入节点值(输入回车结束):\n"); creat_T(A); printf("中序遍历结果:\n"); p = A; bl(p); printf("\n"); return 0; } ``` 此程序首先提示用户输入节点值，然后创建二叉树，并进行中序遍历打印出结果。 #### 六、总结 本文介绍了如何使用C语言实现二叉树的创建与中序遍历。通过递归的方法，我们可以方便地实现这些功能。二叉树作为一种基本的数据结构，在计算机科学中有着广泛的应用。掌握其基本操作对于理解和解决复杂问题非常有帮助。