Python实现树的先序、中序和后序遍历详解

在计算机科学中，树是一种重要的数据结构，常用于许多算法和编程问题中，特别是在搜索、排序和图论等领域。树的基本结构由节点（或顶点）和边组成，每个节点可以有零个或多个子节点。这里我们将探讨三种常见的二叉树遍历方法：先序遍历、中序遍历和后序遍历，这些都是在处理树形数据时的基础操作。 1. **先序遍历（Preorder Traversal）** 先序遍历是访问根节点、然后递归地访问左子树，最后访问右子树。在给定的代码片段中，使用栈来实现这个过程。通过`stack<TreeNode*> st;`存储待访问的节点，首先将根节点入栈，然后进入一个循环，当栈不为空时，取出栈顶节点，访问其值并将其子节点按照“右-左”的顺序入栈。这样保证了先访问根节点，再遍历左子树，最后遍历右子树。例如： ```cpp vector<int> preorderTraversal(TreeNode* root) { vector<int> rst; if (!root) return rst; stack<TreeNode*> st; st.push(root); while (!st.empty()) { TreeNode* node = st.top(); st.pop(); rst.push_back(node->val); if (node->right) st.push(node->right); if (node->left) st.push(node->left); } return rst; } ``` 2. **中序遍历（Inorder Traversal）** 中序遍历的顺序是先递归地访问左子树、然后访问根节点，最后访问右子树。代码中使用两个嵌套的`while`循环实现。外部循环用于遍历直到遇到空节点，内部循环则确保一直把节点压入栈，直到到达最左边的节点。然后弹出栈顶节点，访问其值，接着移动到右子树。这样就保证了按左-根-右的顺序遍历。 ```cpp vector<int> inorderTraversal(TreeNode* root) { vector<int> rst; if (!root) return rst; stack<TreeNode*> st; while (!st.empty() || root) { while (root) { st.push(root); root = root->left; } root = st.top(); st.pop(); rst.push_back(root->val); root = root->right; } return rst; } ``` 3. **后序遍历（Postorder Traversal）** 后序遍历遵循左子树、右子树、根节点的顺序。这里同样使用栈，但策略不同。首先将根节点入栈，然后按“左-右”的顺序将节点入栈，但访问时遵循后序规则。因此，需要先弹出所有子节点，再访问根节点。代码中的`reverse`函数就是用来反转存储结果的向量，使得访问顺序符合后序规则。 ```cpp vector<int> postorderTraversal(TreeNode* root) { vector<int> re; if (root == NULL) return re; stack<TreeNode*> st; st.push(root); while (!st.empty()) { // ... (类似前两种方法的循环) } // 使用reverse函数反转re，得到后序遍历结果 reverse(re.begin(), re.end()); return re; } ``` 总结来说，理解这些基本的二叉树遍历方法对编程非常重要，它们不仅在LeetCode等在线编程平台上常被作为面试题，也是许多高级算法的基础。掌握这些遍历方式有助于在构建搜索算法、构建二叉树数据结构、以及解决与树相关的问题时游刃有余。