二叉树遍历大全

### 二叉树遍历大全 #### 一、前序遍历 **1.1 前序遍历概述** 前序遍历是二叉树遍历的一种方式，其顺序为“根节点 -> 左子树 -> 右子树”。在实际应用中，前序遍历通常用于复制树或打印出树的结构。 **1.2 递归实现** 第一段代码示例展示了如何通过递归方式实现前序遍历： ```c void CreateBiTree(BiTree &T) { // … } int print(BiTree T) { if (T == NULL) return 0; else if (T->lchild == NULL && T->rchild == NULL) return 1; else return print(T->lchild) + print(T->rchild); } ``` **1.3 代码解析** - **创建二叉树**: `CreateBiTree` 函数通过递归方式根据输入的字符序列创建二叉树。 - **前序遍历**: `print` 函数实现了前序遍历，其中如果遇到叶子节点，则返回 `1`；如果遇到空节点，则返回 `0`；其他情况下返回左右子树的遍历结果之和。 **1.4 非递归实现** 第二段代码示例给出了另一种前序遍历的方法，它同样采用了递归形式： ```c void CreatBiTree(struct BiTNode *&p) { // … } void print(struct BiTNode *p) { if (p != NULL) { printf("%c", p->data); // 访问根节点 if (p->lchild == NULL && p->rchild == NULL) { // 叶子节点处理 } else { print(p->lchild); // 遍历左子树 print(p->rchild); // 遍历右子树 } } } ``` **1.5 代码解析** - **创建二叉树**: `CreatBiTree` 函数与第一个示例中的创建函数相似，通过递归读取字符并创建节点。 - **前序遍历**: `print` 函数同样采用递归方式，首先访问根节点，然后递归遍历左右子树。 #### 二、中序遍历 **2.1 中序遍历概述** 中序遍历的顺序为“左子树 -> 根节点 -> 右子树”，这种遍历方式对于某些特定的数据结构非常有用，例如二叉搜索树中，中序遍历能够得到升序排列的节点值。 **2.2 递归实现** 给出的代码示例展示了如何通过递归方式实现中序遍历： ```c void later(struct BiTNode *&p) { // … } void print(struct BiTNode *p) { if (p != NULL) { print(p->lchild); // 遍历左子树 printf("%c", p->data); // 访问根节点 print(p->rchild); // 遍历右子树 } } ``` **2.3 代码解析** - **创建二叉树**: `later` 函数负责根据输入字符创建二叉树。 - **中序遍历**: `print` 函数首先递归遍历左子树，接着访问根节点，最后递归遍历右子树。 #### 三、后序遍历 **3.1 后序遍历概述** 后序遍历的顺序为“左子树 -> 右子树 -> 根节点”，主要用于释放树的内存空间等操作。 **3.2 递归实现** 给出的代码示例展示了如何通过递归方式实现后序遍历： ```c void later(struct BiTNode *&p) { // … } void print(struct BiTNode *p) { if (p != NULL) { print(p->lchild); // 遍历左子树 print(p->rchild); // 遍历右子树 printf("%c", p->data); // 访问根节点 } } ``` **3.3 代码解析** - **创建二叉树**: `later` 函数与中序遍历部分相同。 - **后序遍历**: `print` 函数先遍历左右子树，最后访问根节点。 ### 总结 以上内容分别介绍了二叉树的三种基本遍历方法：前序遍历、中序遍历以及后序遍历，并给出了相应的递归实现方式。每种遍历都有其特定的应用场景和用途，在实际开发过程中，理解这些遍历方式的工作原理对于高效解决问题至关重要。