何时使用预购,后序和有序二进制搜索树遍历策略

Question

我最近意识到,虽然在我的生活中使用了BST,但我甚至都没有考虑过使用任何东西而是使用Inorder遍历(虽然我知道并且知道调整程序使用前/后顺序遍历是多么容易).

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

什么时候实际使用预订/后期订单的一些例子？什么时候比按顺序更有意义？

Answer 1

何时使用预订,有序和后订单遍历策略

在您了解在什么情况下使用二叉树的预订,有序和后期订单之前,您必须准确理解每个遍历策略的工作原理.以下面的树为例.

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

预订遍历:

摘要:从根(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

订单后遍历:

摘要:从最左边的节点(0)开始,以根(7)结束

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

何时使用预订,有序或下订单？

程序员选择的遍历策略取决于所设计算法的具体需求.目标是速度,因此选择能够为您提供最快速所需节点的策略.

1. 如果您知道在检查任何树叶之前需要探索根部,那么您需要选择预订,因为您将在所有树叶之前遇到所有树根.

2. 如果您知道需要在任何节点之前探索所有叶子,则选择下订单,因为您不会浪费任何时间检查根以搜索叶子.

3. 如果您知道树在节点中具有固有序列,并且您希望将树展平为其原始序列,则应使用有序遍历.树将以与创建时相同的方式展平.预订或后序遍历可能无法将树展开回到用于创建它的序列中.

预订,有序和后序的递归算法(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
}

Answer 2

预订/有序/订购后用法:简单的单词

预订:用于创建树的副本示例:如果要创建树的副本并且需要数组中的节点值,并且当您将这些值从索引0插入到新树的结尾时,您将获得副本

顺序::以非递增顺序获取节点的值

后订单::当您想要从叶到根删除树时

Answer 3

如果我想简单地以线性格式打印出树的分层格式,我可能会使用preorder遍历.例如:

- ROOT
    - A
         - B
         - C
    - D
         - E
         - F
             - G

Answer 4

前序和后序分别与自上而下和自下而上的递归算法相关。如果您想以迭代方式在二叉树上编写给定的递归算法，那么这就是您本质上要做的事情。

此外，观察到前序序列和后序序列一起完全指定了手头的树，从而产生紧凑的编码（至少对于稀疏树）。