基于二叉链表的二叉树的遍历
时间: 2024-05-06 13:18:16 浏览: 64
二叉树的遍历分为三种方式:前序遍历、中序遍历和后序遍历。以下是基于二叉链表实现的三种遍历方式的代码:
```c++
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 前序遍历
void preorderTraversal(TreeNode* root) {
if (root == nullptr) return;
cout << root->val << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// 中序遍历
void inorderTraversal(TreeNode* root) {
if (root == nullptr) return;
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
// 后序遍历
void postorderTraversal(TreeNode* root) {
if (root == nullptr) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->val << " ";
}
```
以上代码中,`TreeNode` 结构体表示二叉树的节点。在遍历时,先访问根节点,然后递归遍历左子树和右子树。在前序遍历中,先访问根节点,然后递归遍历左子树和右子树;在中序遍历中,先递归遍历左子树,然后访问根节点,最后递归遍历右子树;在后序遍历中,先递归遍历左子树和右子树,最后访问根节点。
阅读全文