我最近意识到,虽然在我的生活中使用了很多 BST,但我什至从未考虑过使用除中序遍历之外的任何东西(虽然我知道并知道使程序适应使用前序/后序遍历是多么容易)。
意识到这一点后,我拿出了一些旧的数据结构教科书,寻找前序和后序遍历有用性背后的原因——尽管他们并没有说太多。
什么时候实际使用预购/后购的例子有哪些?什么时候比有序更有意义?
我最近意识到,虽然在我的生活中使用了很多 BST,但我什至从未考虑过使用除中序遍历之外的任何东西(虽然我知道并知道使程序适应使用前序/后序遍历是多么容易)。
意识到这一点后,我拿出了一些旧的数据结构教科书,寻找前序和后序遍历有用性背后的原因——尽管他们并没有说太多。
什么时候实际使用预购/后购的例子有哪些?什么时候比有序更有意义?
在您了解在什么情况下对二叉树使用前序、中序和后序之前,您必须准确了解每种遍历策略的工作原理。使用以下树作为示例。
树的根是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
程序员选择的遍历策略取决于所设计算法的具体需求。目标是速度,因此请选择能够以最快速度为您带来所需节点的策略。
如果您知道在检查任何叶子之前需要探索根部,那么您选择预订,因为您将在所有叶子之前遇到所有根部。
如果您知道需要在任何节点之前探索所有叶子,则选择后序,因为您不会浪费任何时间检查根来寻找叶子。
如果您知道树在节点中具有固有序列,并且您希望将树展平回其原始序列,则应使用中序遍历。树将以与创建它的方式相同的方式展平。前序或后序遍历可能不会将树展开回用于创建它的序列。
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
}
预购:用于创建树的副本。例如,如果要创建树的副本,请将节点放入具有前序遍历的数组中。然后对数组中的每个值在新树上执行插入操作。您最终将获得原始树的副本。
In-order: : 用于在 BST 中以非递减顺序获取节点的值。
Post-order: : 用于从叶子到根删除一棵树
如果我想简单地以线性格式打印出树的分层格式,我可能会使用前序遍历。例如:
- ROOT
- A
- B
- C
- D
- E
- F
- G
前序和后序分别与自顶向下和自底向上递归算法相关。如果您想以迭代方式在二叉树上编写给定的递归算法,这就是您本质上要做的事情。
进一步观察,前序序列和后序序列一起完全指定了手头的树,产生了紧凑的编码(至少对于稀疏树)。
您可以在很多地方看到这种差异发挥了真正的作用。
我要指出的一个很好的方法是为编译器生成代码。考虑以下声明:
x := y + 32
为此生成代码的方式是(当然,天真地)首先生成用于将 y 加载到寄存器中的代码,将 32 加载到寄存器中,然后生成将两者相加的指令。因为在你操作它之前必须在寄存器中(让我们假设,你总是可以做常量操作数,但无论如何)你必须这样做。
一般来说,你可以得到的这个问题的答案基本上可以归结为:当处理数据结构的不同部分之间存在一些依赖关系时,差异真的很重要。您在打印元素、生成代码(外部状态有所不同,当然,您也可以单子查看)或在结构上进行其他类型的计算时看到这一点,这些计算涉及取决于首先处理的子项的计算.
有序:从任何解析树中获取原始输入字符串,因为解析树遵循运算符的优先级。首先遍历最深的子树。因此,父节点中的运算符的优先级低于子树中的运算符。