何时使用Preorder，Postorder和二进制搜索树遍历策略 [英] When to use Preorder, Postorder, and Inorder Binary Search Tree Traversal strategies

问题描述

最近我意识到，虽然我在生活中使用了BST，但我从来没有想过使用过任何东西，只是进行了顺序的遍历（当我知道并且知道使用前/后期的程序来调整程序的容易程度）遍历）

在意识到这一点后，我退出了我的一些旧的数据结构教科书，并在预订和后期遍历的有用性方面寻找推理，他们没有说太多。

几乎什么时候使用preorder / postorder有几个例子？什么时候比按顺序更有意义？

解决方案

何时使用预订，按顺序，以及后订单遍历策略

在您了解什么情况下可以使用二进制树进行预订，按顺序和后期订单之前，您必须了解每个遍历策略的工作原理。以下面的树为例。

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

预订遍历：

摘要： root（ 7 ）以最右侧的节点结束（ 10 ）

遍历顺序：7，1 ，0，3，2，5，4，6，9，8，10

按顺序遍历：

摘要：在最左侧的节点（ 0 ）开始，结束于最右边的节点（ 10 ）

遍历顺序：0，1，2，3，4，5，6，7，8，9，10

strong> Post-order遍历：

摘要：以最左侧的节点（ 0 ）开头，以root结尾（ 7 ）

遍历顺序：0，2，4，6，5，3，1，8，10，9，7， / p>

何时使用预订，按顺序或后订单？

程序员选择的遍历策略取决于正在设计的算法的具体需求。目标是速度，所以选择带给您需要最快节点的策略。

1. 如果你知道你需要在检查任何叶子之前探索根，您选择预订，因为您将在所有叶子之前遇到所有根。




2. 如果您知道您需要在任何节点之前浏览所有树叶，则选择后订单，因为您不浪费任何时候检查根寻找叶子。




3. 如果你知道树在节点中有固有的顺序，并且你想将树平展回应该使用其原始序列，而不是顺序遍历。树将以与创建的相同的方式变平。预订或后续遍历可能不会将树退回到用于创建树的顺序。

< h2>预订，排序和顺序（C ++）的递归算法：

  struct Node {
 int数据; 
 Node * left，* right; 
}; 
 void preOrderPrint（Node * root）
 {
 print（root-> name）; //记录根
 if（root-> left！= NULL）preOrderPrint（root-> left）; //遍历左边如果存在
 if（root-> right！= NULL）preOrderPrint（root-> right）; //遍历右边如果存在
} 
 
 void inOrderPrint（Node * root）
 {
 if（root.left！= NULL）inOrderPrint（root-> left）; //遍历左边如果存在
 print（root-> name）; //记录root 
 if（root.right！= NULL）inOrderPrint（root-> right）; //遍历右边如果存在
} 
 
 void postOrderPrint（Node * root）
 {
 if（root-> left！= NULL）postOrderPrint（root-左）; //遍历左边如果存在
 if（root-> right！= NULL）postOrderPrint（root-> right）; //遍历右边如果存在
 print（root-> name）; //记录根
} 
  

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.

What are some examples of when to use preorder/postorder practically? When does it make more sense than in-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.

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

Pre-order traversal:

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

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

In-order traversal:

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

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

Post-order traversal:

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

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

When to use Pre-Order, In-order or Post-Order?

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. 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.

2. 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.

3. 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.

Recursive Algorithms for Pre-order, In-order and Post-order (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
}

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