什么时候使用Preorder,Postorder和Inorder二叉search树遍历策略

我最近意识到,虽然在我的生活中使用了BST的丰富,但我从来没有想过使用除Inorder遍历之外的任何东西(虽然我意识到并知道如何使程序适应前/后顺序遍历)。

在意识到这一点之后,我拿出了一些旧的数据结构教科书,并在前序遍历和后序遍历的有用性之后寻找推理 – 虽然他们没有多说。

实际上什么时候使用前序/后序? 什么时候比有序更有意义?

5 Solutions collect form web for “什么时候使用Preorder,Postorder和Inorder二叉search树遍历策略”

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

在你能够理解在什么情况下使用二叉树的预订,顺序和后序之前,你必须准确理解每个遍历策略是如何工作的。 以下面的树为例。

树的根是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

何时使用预订,按序或后期?

程序员select的遍历策略取决于正在devise的algorithm的具体需求。 目标是速度,所以select能够为您带来最快节点的策略。

  1. 如果你知道在检查任何叶子之前你需要探索根,那么你需要预先订购,因为你会在所有的叶子之前遇到所有的根。

  2. 如果您知道需要在任何节点之前浏览所有叶子,请select后续顺序,因为您不会浪费任何时间检查根目录来search叶子。

  3. 如果知道树在节点中具有固有的序列,并且想要将树平坦化为其原始序列,则应该使用按顺序遍历。 树会像创build它一样被平放。 预订或后序遍历可能不会将树放回到用来创build它的序列中。

预订,按序和后序recursionalgorithm(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 } 

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

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

有很多地方你会发现这个区别起到了真正的作用。

我将指出一个很好的例子就是编译器的代码生成。 考虑一下声明:

 x := y + 32 

你将会为此生成代码的方式是(当然天真地)首先生成用于将y加载到寄存器中的代码,将32加载到寄存器中,然后生成用于添加这两者的指令。 因为在操纵它之前必须在寄存器中(假设,你总是可以做不变的操作数,但无论如何),你必须这样做。

一般来说,你可以得到这个问题的答案基本上可以简化为:当处理数据结构的不同部分之间存在一定的依赖关系时,差异真的很重要。 您在打印元素时看到这一点,在生成代码时(外部状态有所不同,当然也可以单独查看),或者在涉及计算的结构上进行其他types的计算(取决于首先处理的子元素) 。

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

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

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

后序::当你想从树叶到树根中删除树时

前后顺序分别涉及自顶向下和自下而上的recursionalgorithm。 如果你想以迭代的方式在二叉树上写一个给定的recursionalgorithm,这就是你将要做的事情。

进一步观察到,前后序列一起完全指定了手中的树,产生了紧凑的编码(至less对于稀疏树)。