Бинарное дерево поиска в Python


Создать двоичный поиск представлением дерева в заданном массиве целых чисел.

Как я могу улучшить этот код?

# Creating Node object class
class Node(object):
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

# Creating Tree class
class BST(object):
    def __init__(self, val):
        self.root = Node(val)

    def insert(self, value):
        current = self.root
        while current:
            if value < current.value:
                if current.left == None:
                    current.left = Node(value)
                    break
                else:
                    current = current.left
            else:
                if current.right == None:
                    current.right = Node(value)
                    break
                else:
                    current = current.right


# inputs 
t = BST(22)
t.insert(30)
t.insert(10)
t.insert(80)
t.insert(90)
t.insert(9)
t.insert(23)
t.insert(14)
t.insert(6)
t.insert(40)
t.insert(60)
t.insert(3)


513
2
задан 9 апреля 2018 в 03:04 Источник Поделиться
Комментарии
3 ответа

Для проверки, является ли нечто Noneиспользуйте is и is not операторы на месте ==.

Вы также не нужны break заявления как весь код короткое замыкание на if-else блоки. не помогает из-за логической ошибки

Переписать:

class BST(object):
def __init__(self, val):
self.root = Node(val)

def insert(self, value):
current = self.root
while current:
if value < current.value:
if current.left is None:
current.left = Node(value)
break
else:
current = current.left
else:
if current.right is None:
current.right = Node(value)
break
else:
current = current.right

В конце концов, вы должны использовать if __name__ охранник для настройки входов/тестовый раздел.

Остальное все выглядит хорошо.

2
ответ дан 9 апреля 2018 в 05:04 Источник Поделиться

Вы также можете рассмотреть очень элегантный, рекурсивное решение:

def insert(self, value, node=self.root):
if node == null:
return Node(value)
if value < node.value:
node.left = self.insert(value, node.left)
else
node.right = self.insert(value, node.right)

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

3
ответ дан 9 апреля 2018 в 06:04 Источник Поделиться

Есть некоторые повторения, что @zlenyk разоблачил в своем рекурсивном ответ, что вы все еще можете использовать в вашем повторяющийся ответ:

def insert(self, value):
current = self.root

while current:
if value < current.value:
side = 'left'
else:
side = 'right'
next = getattr(current, side, None)
if next is None:
setattr(current, side, Node(value))
current = next

хотя это может быть яснее, как:

def insert(self, value):
current = self.root

def traverse(current, direction):
next = getattr(current, side, None)
if next is None:
setattr(current, side, Node(value))
return next

while current:
if value < current.value:
traverse(current, 'left')
else:
traverse(current, 'right')

или, может быть, что последний бит должен быть:

    while current:
side = { True: 'left', False: 'right' }[value < current.value]
traverse(current, side)

...а может и нет. Вашего звонка, конечно. Это зависит от того, если вы хотите оптимизировать скорость, обслуживание, или умность ;)

1
ответ дан 10 апреля 2018 в 03:04 Источник Поделиться