Блог

Главная - Вопросы по программированию - Проверьте, находится ли заданное значение в дереве двоичного поиска

Проверьте, находится ли заданное значение в дереве двоичного поиска

#python

Вопрос:

Это код, который мне дали, и мне нужно внести в него изменения. Функция ищет значение в данном BST и возвращает значение True, если цель находится в дереве. Вот код:

 def member_prim(tnode, target):
    """
    Purpose:
        Check if target is stored in the binary search tree.
    Pre-Conditions:
        :param tnode: a treenode with the BST property
        :param target: a value
    Post-Conditions:
        none
    Return
        :return: True if target is in the tree
    """

    if tnode is None:
        return False
    elif target < tnode.data:
        right = tnode.right
        return member_prim(right, target)
    else:
        tnode.right = tnode.left
        return member_prim(tnode.right, target)

Я внес несколько изменений в код, и вот что я сделал:

 if tnode is None:
    return False
elif tnode.data is not target:
    return False
elif target > tnode.data:
    right = tnode.right
    return member_prim(right, target)
else:
    tnode.right = tnode.left
    return member_prim(tnode.right, target)

Тем не менее, он выдает ошибку атрибута, говоря, что объект «treenode» не имеет атрибута «данные».

Вот класс treenode:

 class treenode(object):

    def __init__(self, data, left=None, right=None):
        """
        Purpose:
            Create a new treenode for the given data.
        Pre-conditions:
            data:  Any data value to be stored in the treenode
            left, right:  Another treenode (or None, by default)
        Post-condition:
            none
        """
        self.data = data
        self.left = left
        self.right = right

Пожалуйста, дайте мне знать, где я ошибся и как я могу это исправить.

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

1. Пожалуйста, объедините свой код в один фрагмент, который также включает фактическое построение дерева примеров, и вызов member_prim которого вызывает ошибку.

2. Если target < tnode.data , разве вы не должны проверять левое поддерево ? Почему вы проверяете правильное поддерево member_prim(right, target) ?

3. tnode.right = ... : почему эта функция мутирует дерево? Предполагается, что он должен только пересекать его, а не изменять, верно? Код, который «был дан» вам, уже неверен. Почему бы не поискать правильный код из надежного источника? Например, Википедия

Ответ №1:

 class treenode(object):

def __init__(self, data, left=None, right=None):
    """
    Purpose:
        Create a new treenode for the given data.
    Pre-conditions:
        data:  Any data value to be stored in the treenode
        left, right:  Another treenode (or None, by default)
    Post-condition:
        none
    """
    self.data = data
    self.left = left
    self.right = right

def trav(root, target):
    if not root:
        return False
    if root.data == target:
        return True
    if root.data > target:
        return trav(root.left, target)
    if root.data < target:
        return trav(root.right, target)

Этот код покажет вам, присутствует ли целевое значение или нет.

Метки: ,