среда, 23 марта 2016 г.

Построение дерева цифрового поиска

Ниже приведена иллюстрация построения дерева цифрового поиска на Python (см. алгоритм в посте http://blog.coolsoftware.ru/2016/03/blog-post.html):

f = open("f1.txt")
lines = f.read().split()
f.close()
 
def sort(array):
    equal = []
    greater = []
    less = []
    if len(array) <= 1:
        return array
    linem = array[int((len(array)-1)/2)]
    for line in array:
        if linem < line:
            greater.append(line)
        elif linem > line:
            less.append(line)
        elif linem == line:
            equal.append(line)
    return sort(less) + equal + sort(greater)
 
sorted_lines = sort(lines) 
print(sorted_lines)
 
def node(C, P):
    print(P + C)
    return P + " "
 
def R(P, K, I0, J0):
    I = I0
    Si = sorted_lines[I]
    Li = len(Si)
    if K >= Li and I == J0:
        return
    if K < Li:
        C = Si[K]
    else:
        C = "{0}"
    X = node(C, P)
    J = I
    while True:
        if J == J0 or sorted_lines[J+1][K] != C:
            R(X, K+1, I, J)
            if J == J0:
                break
            I = J + 1
            Si = sorted_lines[I]
            Li = len(Si)
            C = Si[K]
            X = node(C, P)
        J = J + 1
 
N = len(sorted_lines)
X = node("[ROOT_NODE]", "")
R(X, 0, 0, N-1)

f1.txt:

BC
ABBA
ABC
ABA
ABB
BAC
A

Вывод:

['A', 'ABA', 'ABB', 'ABBA', 'ABC', 'BAC', 'BC']
[ROOT_NODE]
 A
  {0}
  B
   A
   B
    {0}
    A
   C
 B
  A
   C
  C

===
Перепечатка материалов блога разрешается с обязательной ссылкой на blog.coolsoftware.ru

Комментариев нет:

Отправить комментарий