树遍历（中序、前序和后序）及其示例

什么是树遍历？

在树数据结构中，遍历意味着以某种特定方式访问节点。遍历有两种类型。通常，这种遍历基于二叉树。二叉树意味着每个节点最多可以有 2 个节点。

二叉树是一种众所周知的数据结构。还有二叉搜索树 (BST)。这种遍历有多种用途。层次遍历用于计算两个节点之间的深度。还有一种称为“AVL”的树，需要计算节点的高度。我们可以在数组中表示二叉树，但为了优化内存，我们将使用结构和指针来引用下一个节点。

树遍历的类型

正如我们讨论过的二叉树，现在我们讨论遍历的各个类型。根据类型，有两种类型的遍历。之前我们提到了层序或广度优先遍历的必要性。现在 深度优先遍历 例如，后序用于删除节点（我们稍后会讨论），前序用于复制二叉树，而“中序”将以非减的方式遍历树。

广度优先遍历
深度优先遍历
前序遍历
后序遍历
中序遍历

广度优先遍历

这也被称为层序遍历。让我们考虑下面的树来演示层序遍历。

因此，我们将从根节点“1”开始。它将被标记为级别 1。然后算法将转到当前节点的所有子节点。我们现在将访问节点 2 和 3。它们将被标记为级别 2。

之后，由于我们在第 2 级有 2 个节点，我们也会访问它们的子节点。因此，我们将访问 5,6,8,7、3、XNUMX、XNUMX 并将它们标记为第 XNUMX 级。这里有一件事情没有提到，

节点级别 = 父节点级别 + 1

1 级：1

2级：2 3

3级：5 6 8 7

类似的算法也用于 BFS（广度优先搜索).

这是层次遍历的伪代码：

level_order(node)
Q → Queue()
Q.push(node)
while !Q.empty():
    current_node = Q.pop()
    print current_node.value
# Checking if the current node have any child or not
if current_node.left is not NULL:
    Q.push(current_node.left)
if current_node.right is not NULL:
    Q.push(current_node.right)

中序遍历二叉树

让我们举一个和之前一样的例子。在这种类型的遍历中，我们首先访问左子树，然后访问根，然后访问右子树。为了便于记忆，我们可以按顺序说成左-根-右。

对于整棵树，假设根为 1。现在算法将遵循：

访问节点 1 的左子树。
当前节点为 2（因为它是 1 的左子树）

访问 2 的左子树。此时当前节点为 5。
移至 5，它没有子节点，因此节点 5 将被标记为已访问。它将返回父节点；即 2。
由于 2 的左子树已被访问，因此现在 2 也将被访问。
这款算法将会把当前节点移动到节点 2 的右子树，也就是节点 6。访问完节点 6 之后，它会移动到其父节点 2。
由于访问了节点 2，现在我们将访问 2 的父节点，即节点 1。
之后，我们将访问右子树。

所以最终的遍历将如下所示：

按顺序：5 → 2 → 6 → 1 → 8 → 3 → 7

以下是中序遍历的伪代码：

InOrder(node):
  if node is not null:
    InOrder(node.left)
  print node.value
    InOrder(node.right)

这是中序遍历的递归算法。对于二叉搜索树 (BST)，中序遍历给出排序后的值数组。

后序遍历

在这个遍历中，我们将首先遍历最左子树，然后在根之后遍历最右子树。所有遍历都将按后序进行。让我们演示一个例子：

这里，对于根 = 1，

我们先去左子树。所以根将变成 2。
然后 2 有左子树，所以我们将转到节点 5。现在根是 5。
它没有左子树，也没有右子树。所以，现在我们将节点 5 标记为已访问，然后转到其父节点。

现在根节点为 2，其左子树已完全访问。现在我们将移至其右子树。因此根节点变为 6。
由于节点 6 没有左子树和右子树，我们将节点 6 标记为已访问并移动到其父节点 2。
现在，节点 2 的左子树和右子树都已被访问。它也将被标记为已访问。
我们将移动到节点 2 的父节点，即节点 1。
对于根 1，我们将访问左子树。现在类似地，我们将访问右子树。

标记的圆圈是右子树。现在我们将像访问左子树一样访问右子树。之后，我们将访问节点。所以最终的遍历将是：

帖子顺序：5 → 6 → 2 → 8 → 7 → 3 → 1

以下是后序遍历的伪代码：

PostOrder(node):
    if node is not null:
       PostOrder(node.left)
       PostOrder(node.right)
       print node.value

预序遍历

对于前序遍历，算法将首先访问根节点，然后分别移动到左子树和右子树。为了便于理解，我们可以将前序遍历访问想象成 根 → 左-右。

因此，我们选择节点 1 作为根。

根据算法，首先会发现根，然后是左子树，然后是右子树。
因此，我们将访问根 1。然后我们将移动到其左子树。根变为 2。
我们将访问节点 2 并移至其左子树。因此，根变为 3。
我们访问节点 3，然后移至其父节点。现在访问节点 2 及其左子树。是时候访问右子树了。
我们将移动到右子树，根变为 4。我们将访问 4。由于 4 没有子节点，我们将移动到其父节点。
现在 root 为 2，并且它与它的左子树和右子树一起被访问。因此，我们将移动到它的父节点。现在 root 变为 1。
类似地，我们将访问右子树。

预订顺序：1 → 2 → 3 → 4 → 5 → 6 → 7

以下是后序遍历的伪代码：

PreOrder(node):
   if node is not null:
     print node.value
         PreOrder(node.left)
         PreOrder(node.right)

在实施 Python

class Node:
    def __init__(self, item):
    self.left = None
self.right = None
self.val = item
# creating a tree data structure
def inorder(root):
#checking if the root is null or not
if root:
    inorder(root.left)
# recursively calling left subtree
print(str(root.val) + " ", end = '')
inorder(root.right)
# recursively calling right subtree
def postorder(root):
    if root:
    postorder(root.left)
postorder(root.right)
print(str(root.val) + " ", end = '')
def preorder(root):
    if root:
    print(str(root.val) + " ", end = '')
preorder(root.left)
preorder(root.right)
def levelOrder(root):
    queue = list()
queue.append(root)
while len(queue) & gt;
0:
    current = queue[0]
queue = queue[1: ]
print(str(current.val) + " ", end = "")
if current.left:
    queue.append(current.left)
if current.right:
   queue.append(current.right)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print("\nLevelOrder traversal:\t", end = " ")
levelOrder(root)
print("\nInorder traversal:\t", end = " ")
inorder(root)
print("\nPreorder traversal:\t", end = " ")
preorder(root)
print("\nPostorder traversal:\t", end = " ")
postorder(root)

输出：

LevelOrder traversal:  1 2 3 4 5 6 7
Inorder traversal:     4 2 5 1 6 3 7
Preorder traversal:    1 2 4 5 3 6 7
Postorder traversal:   4 5 2 6 7 3 1

用 C 语言实现

#include <stdio.h>
#include <stdlib.h>
struct node {
   int value;
   struct node* left;
   struct node* right;
};
// Inorder traversal
void InOrder(struct node* root) {
   if (root == NULL) return;
   InOrder(root->left);
   printf("%d ", root->value);
   InOrder(root->right);
}
// PreOrder traversal
void PreOrder(struct node* root) {
  if (root == NULL) return;
  printf("%d ", root->value);
  PreOrder(root->left);
  PreOrder(root->right);
}
// PostOrder traversal
void PostOrder(struct node* root) {
  if (root == NULL) return;
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ", root->value);
}
// Create a new Node
struct node* createNode(int value) {
  struct node* newNode = malloc(sizeof(struct node));
  newNode->value = value;
  newNode->left = NULL;
  newNode->right = NULL;
  return newNode;
}
int main() {
  struct node* root = createNode(1);
  root->left = createNode(2);
  root->right = createNode(3);
  root->left->left = createNode(4);
  root->left->right = createNode(5);
  root->right->left = createNode(6);
  root->right->right = createNode(7);
  printf("Inorder traversal:\t");
  InOrder(root);
  printf("\PreOrder traversal:\t");
  PreOrder(root);
  printf("\nPostOrder traversal:\t");
  PostOrder(root);
}