4

我回到 K&R 是为了阅读一章，并注意到我之前省略的一个示例。本章涵盖了二叉树数据类型的主题。我了解在节点中存储新条目，但打印功能让我感到困惑。为什么要先打印左侧部分？

如果它printf是函数中的第一个命令，然后是左和右，它会起作用吗？

如果不是——那为什么？

/* treeprint: in-order print of tree p */
void treeprint(struct tnode *p)
{
    if (p != NULL) {
        treeprint(p->left);
        printf("%4d %s\n", p->count, p->word);
        treeprint(p->right);
    }
}
4

3 回答 3

9

首先从左侧下降，然后打印节点本身，然后从右侧下降，是使此操作按顺序遍历树的原因。如果您printf按照您的建议在左下降之前移动了它，那将使其成为预遍历。如果您先进行两次下降，那将是post-order。所有三种可能性都访问所有节点，但是以三种不同的顺序。

考虑简单的树

  *
 / \
a   +
   / \
  b   c

如果您按顺序遍历这棵树，您将得到

* a + b c

为了，

a * b + c

下单后，

a b c + *

您想要这些可能性中的哪一种取决于您在做什么。

于 2012-09-17T19:54:17.927 回答
1

当然它会“工作”。你只会在输出上得到不同的排序。您也可以在打印两个子节点后打印该节点。（想象一下，如果你有一棵树有多个孩子，而不仅仅是两个。）

真正的问题是树节点的值是否遵循任何特殊规则，因此任何特定的遍历顺序是否特别有意义。例如，对于二叉搜索树，左-自-右顺序以排序顺序打印出值。

于 2012-09-17T19:51:05.670 回答
0

您可以通过不同的方式遍历二叉树：预排序、中排序和后排序。

printf 可能是一个完全不同的过程（节点数据的计算）。有些问题需要不同的在树上行走的方式，例如，如果您正在平衡一棵二叉树，您将在访问两个子树后计算平衡因子。

因此，printf 可以被认为是其他类型的过程/函数的占位符，以处理不同类型的问题。

于 2012-09-17T19:55:40.850 回答