Анализ кода, если дерево двоичного поиска является деревом двоичного поиска - PullRequest
Новая
       5

Анализ кода, если дерево двоичного поиска является деревом двоичного поиска

0 голосов
/ 24 мая 2018

Я искал код, если Бинарное дерево - это BST, и я был озадачен тем, как оно выполняет сравнение.

def is_bst(cur_node, prev_node_list):
    if (not cur_node):
        return True

    #Check if the left sub-tree is a BST
    if (not TreeNode.is_bst(cur_node.left, prev_node_list)): 
        return False

    #If data in cur_node is <= previous node then it is not a BST
    prev_node = prev_node_list[0]
    if (prev_node and cur_node.data <= prev_node.data):
        return False

    #Update previous node to current node
    prev_node_list[0] = cur_node

    #Check if the right sub-tree is a BST
    return TreeNode.is_bst(cur_node.right, prev_node_list)

Мне было интересно, что делает 

if (prev_node and cur_node.data <= prev_node.data):
  return False

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

1 Ответ

0 голосов
/ 24 мая 2018

Код посещает все элементы в отсортированном порядке.То есть сначала левые узлы, затем текущий узел, чем правый узел.Если вы замените проверку предыдущим узлом оператором print, вы получите элементы от наименьшего к наибольшему (если дерево было действительным).

Теперь достаточно проверить, отсортированы ли эти посещенные элементы.

Чтобы ответить на ваш вопрос: текущий узел проверяется после левого узла.Сначала код переходит на самый левый листовой узел.

...