二叉树的遍历方法总结
时间: 2023-08-04 11:14:32 浏览: 42
二叉树的遍历方法主要有三种:前序遍历、中序遍历和后序遍历。其中,前序遍历是指先访问根节点,然后访问左子树,最后访问右子树;中序遍历是指先访问左子树,然后访问根节点,最后访问右子树;后序遍历是指先访问左子树,然后访问右子树,最后访问根节点。
以下是三种遍历方法的递归实现:
前序遍历(根->左->右):
```
void preorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
cout << root->val << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
```
中序遍历(左->根->右):
```
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
```
后序遍历(左->右->根):
```
void postorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->val << " ";
}
```
以上实现方式都是使用递归实现的,也可以使用迭代的方式来实现遍历。