C++实现二叉树四种遍历方法详解：递归与非递归

在C++中，二叉树遍历是一种基础但重要的概念，它涉及到如何有序地访问二叉树中的每个节点。这里介绍了四种常见的二叉树遍历方法：前序遍历、中序遍历、后序遍历和层序遍历。 1. 前序遍历： 前序遍历遵循递归的思想，其规则是从根节点开始，先访问根节点，然后递归地遍历左子树，最后遍历右子树。在递归实现中，我们定义了一个`TreeNode`结构体来表示二叉树节点，然后定义了`PreOrderTraverse`函数，当遇到空节点时，函数会直接返回。函数首先输出当前节点的值，接着递归调用左子树和右子树的前序遍历。 ```cpp void PreOrderTraverse(BiTNode* T) { if (T == nullptr) { return; } cout << T->val; // 输出节点值 PreOrderTraverse(T->left); // 递归左子树 PreOrderTraverse(T->right); // 递归右子树 } ``` 非递归版本通过使用一个`stack`来存储待访问的节点，将节点入栈，当遇到空节点或栈为空时，弹出栈顶节点并访问其值，然后将指向左子树的节点入栈，直至遍历完整棵树。 2. 中序遍历： 中序遍历同样基于递归，规则是从根节点开始，先遍历左子树，然后访问根节点，最后遍历右子树。递归版本中，访问根节点的位置被推迟到访问完左子树之后。 3. 后序遍历： 后序遍历的顺序与前两种相反，先访问左子树和右子树，最后访问根节点。这通常用于计算表达式树的值，因为它是先乘除后加减的顺序。 4. 层序遍历： 层序遍历是广度优先搜索(BFS)的方式，从根节点开始，逐层向下访问，每层从左到右。非递归实现通常使用队列辅助，先将根节点入队，然后循环进行以下操作：取出队首节点，访问并将其左右子节点入队，直到队列为空。 以上四种遍历方式各有其应用场景，例如前序遍历常用于复制一棵树，中序遍历用于排序（如二叉搜索树），后序遍历可用于计算表达式，而层序遍历则用于图形处理等场景。理解并掌握这些遍历方法对于深入理解二叉树数据结构及其应用至关重要。