C++ 实现二叉树遍历：前序、中序、后序

"C++ 遍历二叉树实例详解，包括前序遍历、中序遍历和后序遍历的递归实现。同时提供了创建二叉树的代码片段。" 在计算机科学中，二叉树是一种数据结构，其中每个节点最多有两个子节点，通常分为左子节点和右子节点。二叉树常用于实现各种算法，如搜索、排序等。在C++中，遍历二叉树是理解和操作这种数据结构的关键部分。本文将详细讲解三种主要的遍历方法：前序遍历、中序遍历和后序遍历，并提供C++的代码示例。 1. **前序遍历**：前序遍历的顺序是根节点 -> 左子树 -> 右子树。递归实现中，首先访问根节点，然后递归地遍历左子树，最后遍历右子树。以下为C++实现： ```cpp void Preorder(BiTNode* T) { if (T) { printf("%c", T->data); Preorder(T->lchild); Preorder(T->rchild); } } ``` 2. **中序遍历**：中序遍历的顺序是左子树 -> 根节点 -> 右子树。在二叉搜索树（BST）中，中序遍历会得到节点按值升序的序列。中序遍历的递归实现如下： ```cpp void Inorder(BiTNode* T) { if (T) { Inorder(T->lchild); printf("%c", T->data); Inorder(T->rchild); } } ``` 3. **后序遍历**：后序遍历的顺序是左子树 -> 右子树 -> 根节点。在计算表达式树或释放二叉树的内存时，后序遍历非常有用。以下是其递归实现： ```cpp void Postorder(BiTNode* T) { if (T) { Postorder(T->lchild); Postorder(T->rchild); printf("%c", T->data); } } ``` 此外，上述代码还展示了如何创建一个简单的二叉树，通过输入字符来构建。`CreateBiTree`函数会递归地根据用户输入创建二叉树的结构。 ```cpp void CreateBiTree(BiTree* T) { char ch; scanf("%c", &ch); getchar(); if (ch == '\n') { printf("不产生子树。\n"); *T = NULL; } else { if (!(*T = (BiTNode*)malloc(sizeof(BiTNode)))) { printf("分配空间失败"); return; } (*T)->data = ch; printf("产生左右子树。\n"); CreateBiTree(&(*T)->lchild); CreateBiTree(&(*T)->rchild); } } ``` 除了递归遍历，还可以使用栈进行非递归遍历。例如，非递归前序遍历（也称为迭代前序遍历）通常使用一个栈来存储待访问的节点，确保正确地遍历整个树。不过，这部分内容在提供的代码片段中没有展示。 二叉树遍历是理解和操作二叉树的基础，也是许多高级算法（如树的复制、查找、插入和删除）的前提。熟练掌握这三种遍历方法对于C++程序员来说至关重要。