Editing 3010 - Bst

Un arbore binar de căutare ('''BST – Binary Search Tree''') este un arbore binar cu proprietatea că valoarea memorată într-un nod este mai mare decât valoarea memorată în orice nod din subarborele său stâng și este mai mică sau egală decât valoarea memorată în orice nod din subarborele său drept.

==Cerința==

Dându-se un șir de '''n''' numere naturale, să se ordoneze crescător utilizând un '''BST'''.

==Date de intrare==

Fișierul de intrare '''bstin.txt''' conține pe prima linie numărul '''n''', iar pe a doua linie '''n''' numere naturale separate prin spații.

==Date de ieșire==

Fișierul de ieșire '''bstout.txt''' va conține pe prima linie, separate prin spațiu, cele '''n''' numere din șir, ordonate crescător.

==Restricții și precizări==

*'''1 ≤ n ≤ 100.000'''
*numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât '''1.000.000.000'''
*Această problemă este destinată învățării arborilor de căutare, deci recomandarea este să memorați mai întâi numerele într-un '''BST''', apoi, cu o parcurgere în inordine să afișați șirul de numere ordonat crescător
*Se știe că există cazuri când un '''BST''' poate avea multe nivele și în consecință complexitatea sortării să fie chiar '''O(n x n).''' Un exemplu este atunci când șirul inițial este ordonat descrescător. Dar este garantat că testele au fost generate aleator, deci numărul de nivele din arbore va fi aproximativ egal cu '''log2n'''.

==Exemplul 1:==

'''bstin.txt'''

 10
 20 7 13 200 15 100 25 3 17 39

'''bstout.txt'''

 Datele de intrare corespund restrictiilor impuse
 3 7 13 15 17 20 25 39 100 200

==Exemplul 2:==

'''bstin.txt'''

 bst

'''bstout.txt'''

 Datele de intrare nu corespund restrictiilor impuse

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key


def insert(root, key):
    if root is None:
        return Node(key)
    else:
        if root.val < key:
            root.right = insert(root.right, key)
        else:
            root.left = insert(root.left, key)
    return root


def inorder(root, fisier_out):
    if root:
        inorder(root.left, fisier_out)
        fisier_out.write(str(root.val) + " ")
        inorder(root.right, fisier_out)


def validare(nr):
    if len(nr) > 100000:
        raise ValueError
    for numar in nr:
        if numar < 0 or numar > 1000000000:
            raise ValueError
    file_out.write("Datele de intrare corespund restrictiilor impuse\n")


if __name__ == '__main__':
    file_in = open("bstin.txt", "r")
    file_out = open("bstout.txt", "w")
    try:
        n = int(file_in.readline())
        arr = list(map(int, file_in.readline().split()))
        validare(arr)
        r = Node(arr[0])
        for i in range(1, n):
            r = insert(r, arr[i])
        inorder(r, file_out)
        file_out.write('\n')
    except ValueError:
        file_out.write("Datele de intrare nu corespund restrictiilor impuse")
    except IndexError:
        file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>