在BST中找到一些带有其水平的数字的前置位 [英] finding a preorder of some digits with their levels in BST

问题描述

我有一个列表，例如5位数字，每个数字在BST中具有其自己的等级:

I have a list that has e.g. 5 digits which each digit has its own level in BST :

列表->

[digit :6  level:1, digit :3  level:2, digit :5   level:3, digit :2 level:3, digit:1   level:4]

如何找到它的预购订单{6,3,2,1,5}?

how can I find its preorder which is { 6,3,2,1,5} ?

考虑我上面的列表中有10000位数字.

Consider that I have 10000 digits in my list above.

谢谢

推荐答案

要以预定顺序遍历BST，您必须 1.访问根(即您的电话号码) 2.遍历左侧子树. 3.遍历右侧子树.

To traverse a BST in preorder you have to 1. Visit the root (i.e. your number) 2. Traverse the left subtree. 3. Traverse the right subtree.

以相同的方式(根，左和右)递归遍历每个子树.

Each subtree is recursively traversed in the same way (root, left and right).

在您的示例中，您没有清楚地指示哪个数字在哪个左侧或右边.一旦到达列表的10000位，您将在同一级别(例如20级)拥有许多数字，除非列表的结构更好地表示了您不会管理的BST.

In your example you don't have a clear indication of which number is to the left or right of which. Once you get to your 10000 digits of your list, you will have many numbers at the same level (say level 20) and unless your list is structured in a better way that represents the BST you wont manage.

只需说数字:65在级别20，您就不会指示它是在数字:70在级别19的左侧还是在数字:60在级别19的右侧.

Just by saying digit: 65 is at level:20, you have no indication whether it is to the left of digit:70 at level:19 or to the right of digit: 60 at level: 19.

更新(如Anil所示):

UPDATE (as indicated by Anil):

可以通过分析树上每个节点的两个层次来确定树中每个节点的位置.如Anil所述，最低的共同祖先将确定X级别的数字A应该在B级别的左侧还是X-1级别的数字C，具体取决于它们在X-2级别的公共父节点是较小还是较小.大于A.

The position of each node in the tree can be determined by analysing the two levels above it. As described by Anil, the lowest common ancestor will determine whether a number A at level X should be to the left of number B or number C at Level X-1, depending on whether their common parent node at level X-2 is smaller or greater than A.

鉴于预订是深度优先的，恐怕您将不得不多次遍历(或递归处理)列表.如果您对内存没有任何限制，则可以先构建树.

Given that pre-order is depth-first you'll have to iterate (or recursively process) through the list multiple times i'm afraid. If you don't have any limitations of memory you could build the tree first.

这篇关于在BST中找到一些带有其水平的数字的前置位的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！