C++二叉树 遍历算法
时间: 2024-09-06 13:02:26 浏览: 25
C++中的二叉树遍历算法主要包括三种方式:前序遍历、中序遍历和后序遍历。此外,还有层次遍历,但通常我们讨论的是前三种。
1. 前序遍历(Pre-order Traversal):首先访问根节点,然后递归地先序遍历左子树,接着递归地先序遍历右子树。遍历顺序为根节点 -> 左子树 -> 右子树。
2. 中序遍历(In-order Traversal):首先递归地中序遍历左子树,然后访问根节点,最后递归地中序遍历右子树。对于二叉搜索树,中序遍历可以得到一个有序的元素序列。遍历顺序为左子树 -> 根节点 -> 右子树。
3. 后序遍历(Post-order Traversal):首先递归地后序遍历左子树,然后递归地后序遍历右子树,最后访问根节点。遍历顺序为左子树 -> 右子树 -> 根节点。
以下是三种遍历算法的简单示例代码:
```cpp
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
void preOrder(TreeNode* root) {
if (root == nullptr) return;
// 访问根节点
visit(root);
// 遍历左子树
preOrder(root->left);
// 遍历右子树
preOrder(root->right);
}
void inOrder(TreeNode* root) {
if (root == nullptr) return;
// 遍历左子树
inOrder(root->left);
// 访问根节点
visit(root);
// 遍历右子树
inOrder(root->right);
}
void postOrder(TreeNode* root) {
if (root == nullptr) return;
// 遍历左子树
postOrder(root->left);
// 遍历右子树
postOrder(root->right);
// 访问根节点
visit(root);
}
```
在实际应用中,可能还需要根据具体情况进行变体处理,比如非递归实现,使用栈等数据结构来模拟递归过程。