4

预购:在此处输入图像描述

下单:在此处输入图像描述

为了:在此处输入图像描述

我有一棵二叉树,其中分配给节点的前序号、后序号和中序号(0 到 11)。如何在每个节点中使用序号、前序号和后序号来获取以给定节点 u 为根的子树的大小,u 在恒定时间内?

编辑:

例如,要确定 w 是否在 u 的子树中,需要 u 的前序号、u 的后序号、w 的前序号和 u 的后序号w。

因为如果 w 的预购数量大于 u 的预购数量,并且 w 的后购数量小于 u 的后购数量。然后我们可以得出结论 w 在 u 的子树中。

4

1 回答 1

3

酷拼图!我希望它不是一个任务,因为我要破坏它。

`pre_order(u.right) - pre_order(u.left) + post_order(u.right) - post_order(u.left) + 1 == 子树中的节点数。

pre_order(u.right) - pre_order(u.left)计算左孩子中的节点数,因为从左孩子开始到右孩子开始的“距离”是左孩子的大小。

类似地,post_order(u.right) - post_order(u.left)计算右孩子的节点数,因为左孩子的末端和右孩子的末端之间的差异是右孩子的大小。

添加 1 包括树本身的根。显然,如果那一侧没有孩子,则任何一项都可能为零。


上面显示的树中的节点没有名称。我的理解是,上图中的数字代表pre_order(x)orpost_order(x)或的值in_order(x),其中x是一个我们不知道名字的节点,但是它在树中的位置对观众来说是显而易见的。

在“现实生活”中,每个节点将包括:(可选名称)、in_order 值、pre_order 值、post_order 值、(可选)左孩子、(可选)右孩子,以及可选的其他信息。

考虑最右下角的节点;post_order(u)==8,post_order(u.left)是未定义的,因为是pre_order(u.left)in_order(u.right)等等,因为它没有孩子。

u考虑这样的节点pre_order(u)==post_order(u)==in_order(u)==3,那么post_order(u.left)==1pre_order(u.right)==5

于 2013-10-22T05:16:59.260 回答