二叉树遍历算法的实现
时间: 2024-04-30 11:15:09 浏览: 13
二叉树遍历算法是指按照一定的顺序访问二叉树中的节点。常见的二叉树遍历算法有三种:前序遍历、中序遍历和后序遍历。
1. 前序遍历(Preorder Traversal):先访问根节点,然后递归地前序遍历左子树,最后递归地前序遍历右子树。
2. 中序遍历(Inorder Traversal):先递归地中序遍历左子树,然后访问根节点,最后递归地中序遍历右子树。
3. 后序遍历(Postorder Traversal):先递归地后序遍历左子树,然后递归地后序遍历右子树,最后访问根节点。
以下是二叉树遍历算法的实现方式:
1. 前序遍历算法实现:
```
void preorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
// 访问根节点
visit(root);
// 递归前序遍历左子树
preorderTraversal(root->left);
// 递归前序遍历右子树
preorderTraversal(root->right);
}
```
2. 中序遍历算法实现:
```
void inorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
// 递归中序遍历左子树
inorderTraversal(root->left);
// 访问根节点
visit(root);
// 递归中序遍历右子树
inorderTraversal(root->right);
}
```
3. 后序遍历算法实现:
```
void postorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
// 递归后序遍历左子树
postorderTraversal(root->left);
// 递归后序遍历右子树
postorderTraversal(root->right);
// 访问根节点
visit(root);
}
```