二叉树遍历

Harshit Jindal 2023年1月30日 2021年2月28日
  1. 二元树遍历
  2. 二元树遍历图解
  3. 二叉树遍历算法
  4. 二叉树遍历的实现
  5. 二叉树遍历算法的复杂度
二叉树遍历

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

深度优先遍历有 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 纳入我们的遍历之前,我们必须访问它的右边节点 21 的右侧节点 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)

Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

相关文章 - Data Structure

相关文章 - Binary Tree