Python-сообщество

bones · Фев. 27, 2014 14:04:30

добрый всем день.
подскажите, пожалуйста, начинающему программисту. Нужно написать функцию по поиску значений по бинарному дереву. У меня получилось, что функция ‘find’ ищет значение только в главной ноде ( . как сделать, чтобы искала по всему дереву и в левой и в правой частях?
спасибо

def print_tree(t):
    if t == None:
        return
    if t['type'] == 'leaf':
        print(t['value'])
    else:
        print_tree(t['left'])
        print(t['value'])
        print_tree(t['right'])
def leaf(v):
    return {'type': 'leaf', 'value':v}
def node(v, l, r):
    return {'type': 'node', 'value':v,'left':l, 'right':r}
def find(t, v):
    for c in n:
        if t['value'] == v:
            print( 'match')
        else:
            print('no match')
l1 = leaf(2)
l2 = leaf(8)
n1 = node(5, l1, l2)
l3 = leaf(47)
n2 = node(20,None, l3)
n = node(11, n1, n2)
find(n,11)

Отредактировано bones (Фев. 27, 2014 14:11:48)

Singularity · Фев. 27, 2014 20:52:56

Попробуй это

def find(t, v):
    if t['value'] == v:
        return v
    if (v > t['value']) or (t.get('right') and t['right']['type'] == 'node' and v >= t['right']['value']):
        find(t['right'])
    if (v < t['value']) or (t.get('left') and t['left']['type'] == 'node' and v <= t['left']['value']):
        find(t['left'])
    return None

http://code.activestate.com/recipes/286239-binary-ordered-tree
http://www.laurentluce.com/posts/binary-search-tree-library-in-python

py.user.next · Фев. 27, 2014 22:18:57

bones
У меня получилось

def leaf(v):
    return {'type': 'leaf', 'value':v}
def node(v, l, r):
    return {'type': 'node', 'value':v,'left':l, 'right':r}

лист - это такой же узел, как и все остальные
к любому листу можно добавить потомка, от любого узла можно убрать потомков
поэтому это разделение не нужно

Singularity
Попробуй это
        find(t['right'])

забыл return

bones · Март 1, 2014 14:13:49

Спасибо всем, кто помог.
У меня самого получилось так:

def find(t, v):
    try:
        if t['value'] == int(v):
            print('match!')
        else:    
            if int(v) < t['value']:
                find(t['left'], v)
            if int(v) > t['value']:
                find(t['right'], v)
    except:
        KeyError
        print('no match')
find(n, v=input('введите число: '))

Python-сообщество

Уведомления

#1 Фев. 27, 2014 14:04:30

бинарное дерево

#2 Фев. 27, 2014 20:52:56

бинарное дерево

#3 Фев. 27, 2014 22:18:57

бинарное дерево

#4 Март 1, 2014 14:13:49

бинарное дерево

Board footer