أشجار البحث الثنائية وعمليات المرور

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

def insert(root, key):
    if root is None:
        return Node(key)
    node = root
    while True:
        if key == node.key:
            return root
        side = "left" if key < node.key else "right"
        child = getattr(node, side)
        if child is None:
            setattr(node, side, Node(key))
            return root
        node = child

def contains(root, key):
    while root is not None:
        if key == root.key:
            return True
        root = root.left if key < root.key else root.right
    return False

root = None
for key in [5, 2, 7, 2]:
    root = insert(root, key)
print(contains(root, 7))
print(contains(root, 8))

True
False

لا ينشئ تكرار المفتاح 2 عقدة أخرى. ويتبع البحث طريقا واحدا يعتمد طوله على الشجرة التي بُنيت.

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

def inorder(root):
    output, stack = [], []
    current = root
    while current is not None or stack:
        while current is not None:
            stack.append(current)
            current = current.left
        current = stack.pop()
        output.append(current.key)
        current = current.right
    return output

root = Node(5, Node(2, Node(1), Node(3)), Node(7))
print(inorder(root))
print(inorder(None))

[1, 2, 3, 5, 7]
[]

يمثل المكدس الصريح الأسلاف الذين لم ينته المرور منهم، ويجنب هذه العملية الاعتماد على عمق العودية.