预购:
下单:
为了:
我有一棵二叉树,其中分配给节点的前序号、后序号和中序号(0 到 11)。如何在每个节点中使用序号、前序号和后序号来获取以给定节点 u 为根的子树的大小,u 在恒定时间内?
编辑:
例如,要确定 w 是否在 u 的子树中,需要 u 的前序号、u 的后序号、w 的前序号和 u 的后序号w。
因为如果 w 的预购数量大于 u 的预购数量,并且 w 的后购数量小于 u 的后购数量。然后我们可以得出结论 w 在 u 的子树中。
预购:
下单:
为了:
我有一棵二叉树,其中分配给节点的前序号、后序号和中序号(0 到 11)。如何在每个节点中使用序号、前序号和后序号来获取以给定节点 u 为根的子树的大小,u 在恒定时间内?
编辑:
例如,要确定 w 是否在 u 的子树中,需要 u 的前序号、u 的后序号、w 的前序号和 u 的后序号w。
因为如果 w 的预购数量大于 u 的预购数量,并且 w 的后购数量小于 u 的后购数量。然后我们可以得出结论 w 在 u 的子树中。
酷拼图!我希望它不是一个任务,因为我要破坏它。
`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)==1
和pre_order(u.right)==5
。