数据结构 二叉树的遍历 c语言版

### 数据结构：二叉树的遍历（C语言版） #### 一、引言 在计算机科学中，数据结构是组织和存储数据的一种方式，它不仅决定了数据的组织形式，还影响了算法的设计与实现。其中，二叉树是一种非常重要的非线性数据结构，在实际应用中有着广泛的应用场景，比如在编译器中的语法分析、文件系统的目录管理等方面都有所体现。本文将详细介绍如何用C语言实现二叉树的三种基本遍历方法：前序遍历、中序遍历以及后序遍历。 #### 二、二叉树的基本概念 二叉树是由节点组成的数据结构，每个节点最多有两个子节点，通常被称作左子节点和右子节点。二叉树具有以下特点： 1. **根节点**：树的最顶端的节点。 2. **叶子节点**：没有子节点的节点。 3. **分支节点**：至少有一个子节点的节点。 4. **深度**：节点到根节点的路径长度。 5. **高度**：树中节点的最大深度。 #### 三、二叉树的遍历 二叉树的遍历是指按照一定的顺序访问二叉树的所有节点，使得每个节点仅被访问一次。常见的遍历方式有三种： - **前序遍历**：访问根节点 -> 遍历左子树 -> 遍历右子树。 - **中序遍历**：遍历左子树 -> 访问根节点 -> 遍历右子树。 - **后序遍历**：遍历左子树 -> 遍历右子树 -> 访问根节点。 接下来，我们将基于给定的C语言代码示例，详细解释这三种遍历方法的实现原理。 #### 四、代码解析 ##### 1. 定义二叉树结构体 ```c typedef struct BiTNode { int data; struct BiTNode* lchild; struct BiTNode* rchild; } BiTree; ``` 这里定义了一个名为`BiTree`的结构体类型，用于表示二叉树的节点。每个节点包含三个成员：`data`存储节点的值；`lchild`指向左子节点；`rchild`指向右子节点。 ##### 2. 创建二叉树 ```c void CreateBiTree(BiTree*& T) { int d; scanf("%d", &d); if (d == 0) T = NULL; else { T = (BiTree*)malloc(sizeof(BiTree)); T->data = d; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } } ``` 此函数通过递归的方式创建一棵二叉树。用户输入节点的值，如果输入为0，则表示该位置的子树为空；否则创建一个新的节点，并继续创建左右子树。 ##### 3. 前序遍历 ```c void PreOrderTraverse(BiTree* T) { if (T != NULL) { printf("%d", T->data); PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } } ``` 前序遍历首先访问当前节点，然后递归地遍历左子树和右子树。 ##### 4. 中序遍历 ```c void InOrderTraverse(BiTree* T) { if (T != NULL) { InOrderTraverse(T->lchild); printf("%d", T->data); InOrderTraverse(T->rchild); } } ``` 中序遍历首先遍历左子树，然后访问当前节点，最后遍历右子树。 ##### 5. 后序遍历 ```c void PostOrderTraverse(BiTree* T) { if (T != NULL) { PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); printf("%d", T->data); } } ``` 后序遍历首先遍历左子树，接着遍历右子树，最后访问当前节点。 #### 五、主函数 ```c void main() { BiTree* T = NULL; printf("应:"); CreateBiTree(T); printf(":"); PreOrderTraverse(T); printf("\n:"); InOrderTraverse(T); printf("\n:"); PostOrderTraverse(T); } ``` 这段代码首先创建了一棵二叉树，并分别使用前序、中序和后序遍历打印出树的信息。 #### 六、总结 通过对上述代码的分析，我们可以看到二叉树遍历的基本思路是通过递归的方式来实现的。在实际应用中，二叉树及其遍历方法是非常重要的基础，掌握这些基本概念和技术对于深入理解高级数据结构和算法设计具有重要意义。