6-2二叉树的遍历

二叉树是一种非常重要的数据结构，在计算机科学中应用广泛，尤其是在搜索和排序算法中。由于二叉树是一个树形结构，所以遍历二叉树是非常重要的操作。本文将从多个角度分析二叉树的遍历方式。

一、二叉树的遍历方式

二叉树的遍历方式主要有三种：前序遍历、中序遍历和后序遍历。其中，前序遍历是先遍历根节点，然后遍历左子树和右子树；中序遍历是先遍历左子树，然后遍历根节点和右子树；后序遍历是先遍历左子树和右子树，然后遍历根节点。除此之外，还有广度优先遍历，即层次遍历，它是先遍历根节点，然后遍历第一层节点、第二层节点……直到所有节点都被遍历完。

二、三种遍历方式的实现

实现三种遍历方式的代码如下所示：

前序遍历：

```

void preOrder(TreeNode* root) {

if (root == NULL) return;

cout< val<<" "; // 先遍历根节点

preOrder(root->left); // 再遍历左子树

preOrder(root->right); // 最后遍历右子树

}

```

中序遍历：

```

void inOrder(TreeNode* root) {

if (root == NULL) return;

inOrder(root->left); // 先遍历左子树

cout< val<<" "; // 再遍历根节点

inOrder(root->right); // 最后遍历右子树

}

```

后序遍历：

```

void postOrder(TreeNode* root) {

if (root == NULL) return;

postOrder(root->left); // 先遍历左子树

postOrder(root->right); // 再遍历右子树

cout< val<<" "; // 最后遍历根节点

}

```

三、三种遍历方式的适用场景

三种遍历方式各有适用的场景。前序遍历适用于序列化和反序列化二叉树，以及在树中查找路径；中序遍历适用于在二叉搜索树中搜索和排序；后序遍历适用于计算二叉树的深度、判断二叉树是否对称以及计算二叉树节点之和。

四、递归和非递归遍历的实现

以上代码实现都是使用递归算法实现的，但是对于非递归遍历也有许多实用的算法。比如使用栈的非递归遍历算法，使用队列的广度优先遍历算法等。

五、总结

本文从多个角度分析了二叉树的遍历方式，包括三种遍历方式的实现、适用场景以及递归和非递归遍历的实现。掌握二叉树的遍历方式对于理解搜索和排序算法，以及其他与树相关的算法都是非常有帮助的。