Деревья бинарного поиска и данные с Python

У меня есть функция двоичного дерева с 3 кусками данных в каждом узле. Они классифицируются по идентификационным номерам. Они также содержат "Имя" и "Марка"

Определенная функция, с которой у меня проблемы - это функция поиска имени, она выглядит так:

def findName(tree,name):
    if tree==None:
        return None
    elif tree['name']==name:
        return True
    else:
        findName(tree['right'],name)
        findName(tree['left'],name)

Я всегда могу найти первое имя в дереве, но не могу найти ничего дальше. Если я введу findName(tree['right'],name) в режиме ожидания Python я получаю истину, если имя находится в дереве.

Источник

3 ответа

Решение

Единственный способ для функции на самом деле вернуть некоторые данные, если она сама использует return заявление. Ваш else: Люкс не содержит return заявления.

Источник

В противном случае вы должны сделать что-то вроде:

return findName(tree['right'],name) or findName(tree['left'],name)

так что он ищет в обеих ветвях, и если он найдет его в любой из этих ветвей, возвращаемое значение будет True

Источник

Я полагаю, что имеются бинарные модули дерева поиска с открытым исходным кодом; Если ваша цель - узнать о BST, непременно напишите свой собственный, но если вы работаете над чем-то, что поддается открытому исходному коду, вы можете попробовать стандартный модуль, который уже был протестирован и отлажен.

У меня есть что-то вроде BST для Python по адресу http://stromberg.dnsalias.org/~strombrg/treap/. На самом деле это вариант BST, который не требует, чтобы ключи передавались в BST в случайном порядке - он использует случайное значение на каждом узле для разброса объектов. Для программиста это похоже на словарь, за исключением того, что ключи возвращаются отсортированными, когда вы выполняете их, и поиск не так быстр, как словарь (хэш).

Полагаю, что трепы были обнаружены еще в конце 80-х годов, так что это сравнительно недавняя версия CS. Это очень хорошо структурированная структура данных; чем больше разных способов доступа к одним и тем же данным, тем лучше вы, скорее всего, будете трепаться.

На самом деле, из того, что вы описали, вы могли бы даже лучше использовать словарь (хэш-таблицу), где ключами являются ваши имена.

Источник
Другие вопросы по тегам