何时使用前序、后序和中序二叉搜索树遍历策略 [英] When to use Preorder, Postorder, and Inorder Binary Search Tree Traversal strategies

问题描述

我最近意识到，虽然在我的生活中使用了大量的 BST，但我什至从未考虑过使用中序遍历以外的任何东西(虽然我知道并知道调整程序以使用 pre/post-order遍历).

I realized recently that while having used BST's plenty in my life, I've never even contemplated using anything but Inorder traversal (while I am aware of and know how easy it is to adapt a program to use pre/post-order traversal).

意识到这一点后，我拿出了一些旧的数据结构教科书，并寻找前序和后序遍历的有用性背后的推理 - 不过他们并没有说太多.

Upon realizing this, I pulled out some of my old data-structures textbooks and looked for reasoning behind the usefulness of pre-order and post-order traversals - they didn't say much though.

什么时候实际使用前序/后序的例子有哪些?什么时候比按顺序更有意义?

推荐答案

何时使用 Pre-Order、In-Order 和 Post-Order 遍历策略

在了解在什么情况下对二叉树使用前序、中序和后序之前，你必须准确了解每种遍历策略的工作原理.以下面的树为例.

When to use Pre-Order, In-Order, and Post-Order Traversal Strategy

Before you can understand under what circumstances to use pre-order, in-order and post-order for a binary tree, you have to understand exactly how each traversal strategy works. Use the following tree as an example.

树的根是7，最左边的节点是0，最右边的节点是10.

The root of the tree is 7, the left most node is 0, the right most node is 10.

前序遍历:

总结:从根节点 (7) 开始，到最右边的节点 (10) 结束

Summary: Begins at the root (7), ends at the right-most node (10)

遍历序列:7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10

Traversal sequence: 7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10

有序遍历:

总结:从最左边的节点 (0) 开始，到最右边的节点 (10) 结束

Summary: Begins at the left-most node (0), ends at the rightmost node (10)

遍历序列:0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Traversal Sequence: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

后序遍历:

总结:从最左边的节点 (0) 开始，到根节点 (7) 结束

Summary: Begins with the left-most node (0), ends with the root (7)

遍历序列:0, 2, 4, 6, 5, 3, 1, 8, 10, 9, 7

Traversal sequence: 0, 2, 4, 6, 5, 3, 1, 8, 10, 9, 7

程序员选择的遍历策略取决于所设计算法的具体需求.目标是速度，因此请选择能够以最快速度获得所需节点的策略.

The traversal strategy the programmer selects depends on the specific needs of the algorithm being designed. The goal is speed, so pick the strategy that brings you the nodes you require the fastest.

1. 如果您知道在检查任何叶子之前需要探索根部，请选择预购，因为您会在所有叶子之前遇到所有根部.

1. If you know you need to explore the roots before inspecting any leaves, you pick pre-order because you will encounter all the roots before all of the leaves.

如果您知道需要在任何节点之前探索所有叶子，请选择后序，因为您不会浪费任何时间检查根以寻找叶子.

If you know you need to explore all the leaves before any nodes, you select post-order because you don't waste any time inspecting roots in search for leaves.

如果您知道树在节点中具有固有序列，并且您想将树展平回其原始序列，则应使用有序遍历.树将按照创建时的相同方式展平.前序或后序遍历可能不会将树展开回用于创建它的序列.

If you know that the tree has an inherent sequence in the nodes, and you want to flatten the tree back into its original sequence, than an in-order traversal should be used. The tree would be flattened in the same way it was created. A pre-order or post-order traversal might not unwind the tree back into the sequence which was used to create it.

前序、中序和后序 (C++) 的递归算法:

struct Node{
    int data;
    Node *left, *right;
};
void preOrderPrint(Node *root)
{
  print(root->name);                                  //record root
  if (root->left != NULL) preOrderPrint(root->left);  //traverse left if exists
  if (root->right != NULL) preOrderPrint(root->right);//traverse right if exists
}

void inOrderPrint(Node *root)
{
  if (root.left != NULL) inOrderPrint(root->left);   //traverse left if exists
  print(root->name);                                 //record root
  if (root.right != NULL) inOrderPrint(root->right); //traverse right if exists
}

void postOrderPrint(Node *root)
{
  if (root->left != NULL) postOrderPrint(root->left);  //traverse left if exists
  if (root->right != NULL) postOrderPrint(root->right);//traverse right if exists
  print(root->name);                                   //record root
}

这篇关于何时使用前序、后序和中序二叉搜索树遍历策略的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！