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