二叉树先序、中序、后序遍历特点
时间: 2023-11-20 07:59:47 浏览: 96
二叉树的遍历方式有三种:先序遍历、中序遍历和后序遍历。它们的特点如下:
1. 先序遍历:先访问根节点,然后访问左子树,最后访问右子树。其遍历顺序为根-左-右。
2. 中序遍历:先访问左子树,然后访问根节点,最后访问右子树。其遍历顺序为左-根-右。
3. 后序遍历:先访问左子树,然后访问右子树,最后访问根节点。其遍历顺序为左-右-根。
需要注意的是,以上三种遍历方式都是深度优先遍历,因为它们都是先访问一个节点的所有子节点,再访问子节点的子节点,以此类推。而广度优先遍历则是按照层次遍历,即先访问根节点,然后访问第二层的所有节点,再访问第三层的所有节点,以此类推。
相关问题
二叉树先序遍历中序遍历后序遍历
二叉树的遍历方式有三种:先序遍历、中序遍历和后序遍历。其中,先序遍历是指先访问根节点,然后递归遍历左子树和右子树;中序遍历是指先递归遍历左子树,然后访问根节点,最后递归遍历右子树;后序遍历是指先递归遍历左子树和右子树,最后访问根节点。
以下是三种遍历方式的代码实现:
1. 先序遍历
```python
def pre_order(root):
if root:
print(root.val)
pre_order(root.left)
pre_order(root.right)
```
2. 中序遍历
```python
def in_order(root):
if root:
in_order(root.left)
print(root.val)
in_order(root.right)
```
3. 后序遍历
```python
def post_order(root):
if root:
post_order(root.left)
post_order(root.right)
print(root.val)
```
数据结构二叉树先序中序后序遍历递归
二叉树的先序、中序和后序遍历是通过递归实现的。先序遍历指的是先访问根节点,然后依次对左子树和右子树进行先序遍历;中序遍历指的是先对左子树进行中序遍历,然后访问根节点,最后对右子树进行中序遍历;后序遍历指的是先对左子树进行后序遍历,然后对右子树进行后序遍历,最后访问根节点。
递归实现先序遍历的代码如下:
```
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 << " "; // 访问根节点
}
```