найти предзаказ некоторых цифр с их уровнями в BST - PullRequest
Новая
       4

найти предзаказ некоторых цифр с их уровнями в BST

0 голосов
/ 27 декабря 2010

У меня есть список, который имеет, например, 5 цифр, каждая из которых имеет свой собственный уровень в 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}?

Учтите, что в моем списке 10000 цифр.

спасибо

1 Ответ

0 голосов
/ 28 декабря 2010

Чтобы пройти BST в предзаказе, вы должны 1. Посетите корень (то есть ваш номер) 2. Пройдите по левому поддереву. 3. Пройдите правое поддерево.

Каждое поддерево рекурсивно обходится одинаково (корень, левый и правый).

В вашем примере у вас нет четкого указания, какое число слева или справа от какого. Как только вы достигнете 10000 цифр в вашем списке, у вас будет много чисел на одном уровне (скажем, на уровне 20), и если ваш список не структурирован лучше, чем BST, которым вы не будете управлять.

Просто говоря, что цифра: 65 находится на уровне: 20, у вас нет указания, находится ли она слева от цифры: 70 на уровне: 19 или справа от цифры: 60 на уровне: 19.

ОБНОВЛЕНИЕ (как указано Анил):

Положение каждого узла в дереве можно определить, проанализировав два уровня над ним. Как описано Анил, самый низкий общий предок будет определять, должно ли число A на уровне X быть слева от номера B или числа C на уровне X-1, в зависимости от того, меньше ли их общий родительский узел на уровне X-2, или больше чем А.

Учитывая, что предварительный заказ является первым по глубине, боюсь, вам придется многократно повторять (или рекурсивно обрабатывать) список. Если у вас нет никаких ограничений памяти, вы можете сначала построить дерево.

...