迹忆客 专注技术分享

二叉树是一种非线性数据结构。它被称为二叉树，因为每个节点最多只有两个子节点。这些子节点被称为左子和右子。它也可以解释为一个不定向图，其中最上面的节点称为根。与线性数据结构只能以一种方式遍历不同，树可以以不同的方式遍历。我们可以通过沿着深度或广度进行探索来遍历一棵树。第一种方法叫做深度优先遍历，第二种方法叫做广度优先遍历。在本文中，我们将讨论深度优先遍历。

深度优先遍历有 3 种-中序遍历、前序遍历和后序遍历。我们将逐一讨论它们。

二元树遍历

中序遍历

在这个遍历中，我们首先访问左子树，然后是根，最后是右子树。每个节点都类似于一个子树。对于 BST，中序遍历按升序返回所有的元素

前序遍历

在这个遍历中，我们首先访问根，然后是左边的子树，最后是右边的子树。每个节点都类似于一个子树。它通常用于复制，即创建树的副本。前缀遍历也有助于从表达式树生成前缀表达式。

后序遍历

在这个遍历中，我们首先访问左子树，然后是右子树，最后是根。每一个节点都类似于一个子树。它被用来有效地删除树。它还有助于从表达式树生成后缀表达式。

二元树遍历图解

中序遍历：(4、2、1、5、3、6、7、8、9)

我们在根节点 3 上调用中序遍历。递归向左遍历到达节点 4，它是最左的节点，并将其包含在我们的输出中；由于它是根节点，没有左节点，我们访问它最右的节点 2，并将其包含在我们的遍历中。这样，我们遍历整棵树，得到上述顺序作为我们的输出。

前序遍历：(3，1，4，2，5，7，6，9，8)

我们在根节点 3 上调用前序遍历，并将其包含在我们的输出中。然后我们向左递归遍历到下一个根节点 1，然后是 4。由于 4 没有左边的子节点，我们访问右边的节点 2。现在我们已经覆盖了根节点 4 下的子树，我们回溯到节点 1，并向右走到节点 5。这样，我们遍历整棵树，得到上述顺序作为我们的输出。

后序遍历：(2，4，5，1，6，8，9，7，3)

我们在根节点 3 上调用后序遍历，向左递归遍历到达节点 4。在将 4 纳入我们的遍历之前，我们必须访问它的右边节点 2。1 的右侧节点 5 未被访问，所以我们先将 5 包括在内，然后将 1 输出。然后我们追溯到根节点 3，并继续遍历右边的子树。这样，我们遍历整棵树，得到上述顺序作为我们的输出。

二叉树遍历算法

中序遍历

• 通过递归调用 in-order 函数，遍历左侧子树。
• 访问根节点。
• 通过递归调用 in-order 函数来遍历右侧子树。

前序遍历

• 访问根节点。
• 通过递归调用 in-order 函数来遍历左边的子树。
• 通过递归调用顺序内函数来遍历右边的子树。

后序遍历

• 通过递归调用 in-order 函数来遍历左边的子树。
• 通过递归调用 in-order 函数来遍历右侧子树。
• 访问根节点。

二叉树遍历的实现

#include <iostream>
using namespace std;

class Node {
public:
    int key;
    Node *left, *right;
    Node(int x) {
        this->key = x;
        this->left = this->right = NULL;
    }
};

void inorder(Node *root) {
    if (root != NULL)
    {
        inorder(root->left);
        cout << root->key << " ";
        inorder(root->right);
    }
}
void preorder(Node*root) {
    if (root != NULL) {
        cout << root->key << " ";
        preorder(root->left);
        preorder(root->right);
    }
}

void postorder(Node* root) {
    if (root != NULL) {
        postorder(root->left);
        postorder(root->right);
        cout << root->key << " ";
    }
}

int main() {
    Node* root = new Node(3);
    root->left = new Node(1);
    root->right = new Node(7);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->left->left->right = new Node(2);
    root->right->left = new Node(6);
    root->right->right = new Node(9);
    root->right->right->left = new Node(8);
    cout << "The inorder traversal of the tree is : "; inorder(root); cout << endl;
    cout << "The preorder traversal of the tree is : "; preorder(root); cout << endl;
    cout << "The postorder traversal of the tree is : "; postorder(root); cout << endl;
}

二叉树遍历算法的复杂度

时间复杂度

• 平均情况

一棵树上有 n 个节点，在所有 3 种遍历中，我们必须去访问每个节点。由于我们在 n 个节点上迭代，虽然顺序不同，但 3 种遍历的时间复杂度都是 O(n)。平均情况下的时间复杂度是 O(n)。

• 最佳情况

最佳情况下的时间复杂度是 O(n)。它与所有 3 遍历的平均情况时间复杂度相同。

• 最坏情况

最坏情况下的时间复杂度是 O(n)。它与所有 3 遍历的最坏情况时间复杂度相同。

空间复杂度

由于递归调用所需的额外空间，该算法的空间复杂度为 O(n)。