Python - Suchbaum

Ein binärer Suchbaum (BST) ist ein Baum, in dem alle Knoten den unten genannten Eigenschaften folgen. - Der linke Unterbaum eines Knotens hat einen Schlüssel, der kleiner oder gleich dem Schlüssel seines übergeordneten Knotens ist. Der rechte Unterbaum eines Knotens hat einen Schlüssel, der größer ist als der Schlüssel des übergeordneten Knotens. Somit teilt BST alle seine Unterbäume in zwei Segmente ein; der linke Unterbaum und der rechte Unterbaum und können definiert werden als -

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

Suchen Sie nach einem Wert in einem B-Baum

Bei der Suche nach einem Wert in einem Baum wird der eingehende Wert mit dem Wert verglichen, der die Knoten verlässt. Auch hier durchlaufen wir die Knoten von links nach rechts und schließlich mit dem Elternteil. Wenn der gesuchte Wert keinem der Exitign-Werte entspricht, geben wir eine nicht gefundene Nachricht zurück, andernfalls wird die gefundene Nachricht zurückgegeben.

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))

Wenn der obige Code ausgeführt wird, wird das folgende Ergebnis erzeugt:

7 Not Found
14 is found