Sprawdzenie czy jest to BST

0

Napisałem kod, który sprawdza czy jest to BST czy mógłby ktoś sprawdzić czy jest on poprawny oraz jak zastąpić ta wartości min i max żeby były uniwersalne dla każdego przypadku (póki co wstawiłem jakieś przykładowe).

 def sprawdzenie(root, min = -1000, max = 1000):
    if root == None:
        return True
    if (root.val <= min or root.val >= max):
        return False
    return sprawdzenie(root.left, min, root.val) and sprawdzenie(root.right, root.val, max)
0

Ale co ten kod ma wspólnego z tym co miałeś zrobić? Mnie się wydawało ze jedyny warunek dla BST jest taki że na lewo mniejsze a na prawo większe...

0

@Shalom: No i przechodzę po całym drzewie i sprawdzam te wartości czy się zgadzają. Czy powinienem robić to inaczej jakoś?

1

No jak dla mnie to robisz tam jakiś WTF co najwyżej, z tymi min i max. Po co one tam?
Warunek jest:

def check(root):
	if root is None:
	    return True
	if root.left is not None and root.val < root.left.val:
	    return False # większy na lewo
	if root.right is not None and root.val > root.right.val:
	    return False # mniejszy na prawo
	return check(root.left) and check(root.right)
0

A czy to jest poprawne sposób na odwracanie list?

 def reverse(lis, prev = None):
    if lis.next != None:
        reverse(lis.next, lis)
    lis.next = prev
0

Przetestuj? ;] Na pierwszy rzut oka jest ok, ale robienie tego rekurencją to hardkor.

0

Dokładnie przetestuj :)

Moje takie przemyślenie:
Rekurencja nie jest "zbyt" dobrym sposobem do przeszukiwania/sprawdzania drzew w Pythonie, lepiej to zrobić iteracyjnie.

Dlaczego ?
Spróbuj wywołać swój program w taki sposób żeby było ponad 1000 wywołań rekurencyjnych. Myślę że dostaniesz "RuntimeError: maximum recursion depth exceeded" ?
Python ma wbudowane w sobie ograniczenie rekursji można to sprawdzić: sys.setrecursionlimit . Oczywiście można to zmienić ale nie jest to zbyt dobry pomysł bo może to niekiedy skutkować np: exit code 139 no i SIGSEGV.

1 użytkowników online, w tym zalogowanych: 0, gości: 1