二叉树元素的递归printf

Question

我回到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);
    }
}

Answer 1

首先下降左侧,然后打印节点本身,然后下降右侧,这是使该操作按顺序遍历树的原因.如果你printf按照你的建议在左下降之前移动了那将使它成为预先遍历的.如果你先做两次下降,那将是下订单.所有三种可能性都访问所有节点,但有三种不同的顺序.

考虑一下简单的树

  *
 / \
a   +
   / \
  b   c

如果你按预先的顺序遍历这棵树,你就得到了

* a + b c

为了,

a * b + c

后序,

a b c + *

您想要的这些可能性中的哪一个取决于您正在做什么.