Python - Albero di ricerca

Un albero di ricerca binario (BST) è un albero in cui tutti i nodi seguono le proprietà indicate di seguito: il sottoalbero di sinistra di un nodo ha una chiave minore o uguale alla chiave del suo nodo padre. Il sottoalbero destro di un nodo ha una chiave maggiore della chiave del suo nodo padre. Pertanto, BST divide tutti i suoi sottoalberi in due segmenti; il sottoalbero sinistro e il sottoalbero destro e può essere definito come -

left_subtree (keys)  ≤  node (key)  ≤  right_subtree (keys)

Cerca un valore in un albero B.

La ricerca di un valore in un albero implica il confronto del valore in entrata con il valore in uscita dai nodi. Anche qui attraversiamo i nodi da sinistra a destra e poi finalmente con il genitore. Se il valore cercato non corrisponde a nessuno dei valori exitign, restituiamo il messaggio non trovato altrimenti viene restituito il messaggio trovato.

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data

# Insert method to create nodes
    def insert(self, data):

        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data
# findval method to compare the value with nodes
    def findval(self, lkpval):
        if lkpval < self.data:
            if self.left is None:
                return str(lkpval)+" Not Found"
            return self.left.findval(lkpval)
        elif lkpval > self.data:
            if self.right is None:
                return str(lkpval)+" Not Found"
            return self.right.findval(lkpval)
        else:
            print(str(self.data) + ' is found')
# Print the tree
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()


root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)
print(root.findval(7))
print(root.findval(14))

Quando il codice sopra viene eseguito, produce il seguente risultato:

7 Not Found
14 is found