树的遍历三种顺序代码

树是一种重要的数据结构，因为它可以模拟自然界中很多现象，如家谱、文件系统等。在处理树这种数据结构时，我们经常需要遍历整棵树，以便对树中的每个节点进行一些操作。树的遍历分为三种顺序：先序遍历、中序遍历和后序遍历。本文将从多个角度分析这三种遍历顺序的代码实现。

1. 先序遍历

先序遍历的代码实现是最简单的。只需在函数中先操作当前节点，再递归操作它的左右子节点即可。下面是先序遍历的代码实现：

```

void preOrder(TreeNode* root) {

if (root != nullptr) {

// 操作当前节点

// ...

preOrder(root->left); // 递归操作左子节点

preOrder(root->right); // 递归操作右子节点

}

}

```

2. 中序遍历

中序遍历和先序遍历的区别在于，操作当前节点的时机不同。在中序遍历中，我们需要先递归操作左子节点，然后操作当前节点，最后递归操作右子节点。下面是中序遍历的代码实现：

```

void inOrder(TreeNode* root) {

if (root != nullptr) {

inOrder(root->left); // 递归操作左子节点

// 操作当前节点

// ...

inOrder(root->right); // 递归操作右子节点

}

}

```

3. 后序遍历

后序遍历则需要先递归操作左右子节点，最后再操作当前节点。下面是后序遍历的代码实现：

```

void postOrder(TreeNode* root) {

if (root != nullptr) {

postOrder(root->left); // 递归操作左子节点

postOrder(root->right); // 递归操作右子节点

// 操作当前节点

// ...

}

}

```

4. 代码分析

以上三种遍历顺序的代码实现都使用了递归。递归操作起来比较简单，但是有时候会导致栈溢出的问题，因为递归调用会占用栈空间，如果树的深度很大，栈就会很快耗尽。如果我们有可能遇到这种情况，可以使用非递归的方法实现遍历。

非递归的遍历实现一般使用栈来模拟递归过程。以先序遍历为例，代码如下：

```

void preOrder(TreeNode* root) {

stack s;

s.push(root);

while (!s.empty()) {

TreeNode* node = s.top();

s.pop();

if (node != nullptr) {

// 操作当前节点

// ...

s.push(node->right); // 先加入右节点

s.push(node->left); // 再加入左节点

}

}

}

```

栈的作用是暂时保存还没有被处理的节点。这里我们先加入右节点再加入左节点，这样出栈的时候先处理左节点，符合先序遍历的顺序。

中序遍历和后序遍历的非递归实现可以调整入栈顺序，从而模拟相应的遍历顺序。

5. 总结

本文从三个方面分析了树的遍历三种顺序代码的实现，包括递归实现、非递归实现以及栈的使用。虽然递归实现简单易懂，但是有可能导致栈溢出；非递归实现比较复杂，但是可以有效避免栈溢出问题。不同的实现方式适用于不同的场景，我们应该根据具体情况来选择合适的方式。