BST-Traversierung

Grundsätzlich gibt es drei Methoden der Baumdurchquerung: Pre-Order, In-Order und Post-Order Traversierung. Der Unterschied zwischen den drei Methoden liegt in der Reihenfolge der Elemente. Schauen wir uns an, wie wir dies im Code erreichen.
In diesem Kapitel arbeiten wir mit dem folgenden Baum:

Die Pre-Order Traversierung

Die Pre-Order Traversierung ergibt die natürliche Reihenfolge. Zuerst besuchen wir den Wurzelknoten und dann rekursiv die linken und rechten Teilbäume jedes Teilbaums.


              12345678910111213141516171819202122232425262728293031323334353637
            
class Tree:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

root = Tree(26, 
            left=Tree(12, 
                      left=Tree(7), 
                      right=Tree(24)), 
            right=Tree(52, 
                       left=Tree(39), 
                       right=Tree(85)))

# The pre-order traversal yields the natural ordering of the elements in the tree
def pre_order_traversal(subtree_root):
    # Initialize an empty string to store the node values
    nodes = []

    # Define the recursive function to traverse the tree
    def traverse(node):
        # If the node is not None, append its value to the list
        if node is not None:
            nodes.append(str(node.value))
            # Recursively traverse the left and right subtrees
            traverse(node.left)
            traverse(node.right)

    # Start the traversal from the root
    traverse(subtree_root)

    # Join the node values with the arrow separator
    result = ' -> '.join(nodes)
    return result

# Perform pre-order traversal and print the result
print(pre_order_traversal(root))

Wir setzen die append-Anweisung vor die rekursiven Aufrufe, um dies zu erreichen.

Der In-Order-Traversal

Der In-Order-Traversal ist wahrscheinlich der gebräuchlichste, da er die sortierte Reihenfolge der Elemente im Baum ergibt.


              12345678910111213141516171819202122232425262728293031323334353637383940
            
class Tree:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

root = Tree(26, 
            left=Tree(12, 
                      left=Tree(7), 
                      right=Tree(24)), 
            right=Tree(52, 
                       left=Tree(39), 
                       right=Tree(85
                       )))

# The in-order traversal yields the sorted order of the elements in the tree
def in_order_traversal(subtree_root):
    # Initialize an empty string to store the node values
    nodes = []

    # Define the recursive function to traverse the tree
    def traverse(node):
        # If the node is not None, recursively traverse the left subtree
        if node.left:
            traverse(node.left)
        # Append the node value to the list
        nodes.append(str(node.value))
        # If the node is not None, recursively traverse the right subtree
        if node.right:
            traverse(node.right)

    # Start the traversal from the root
    traverse(subtree_root)

    # Join the node values with the arrow separator
    result = ' -> '.join(nodes)
    return result

# Perform in-order traversal and print the result
print(in_order_traversal(root))

Bei der Implementierung einer In-Order-Traversierung setzen wir die append-Anweisung in die Mitte zwischen zwei rekursiven Aufrufen der linken und rechten Teilbäume.

Die Post-Order-Traversierung

Die dritte Möglichkeit, einen Binären Suchbaum zu durchlaufen, ist die Verwendung der Post-Order-Traversierung. Der Post-Order-Traversierungsalgorithmus besucht zuerst den linken und den rechten Teilbaum und dann den Wurzelknoten für jeden Teilbaum im ursprünglichen Baum.


              1234567891011121314151617181920212223242526272829303132333435363738394041
            
class Tree:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

root = Tree(26, 
            left=Tree(12, 
                      left=Tree(7), 
                      right=Tree(24)), 
            right=Tree(52, 
                       left=Tree(39), 
                       right=Tree(85
                       )))

# The post-order traversal prints the elements in order from bottom to the top
# from left to the right
def post_order_traversal(subtree_root):
    # Initialize an empty string to store the node values
    nodes = []

    # Define the recursive function to traverse the tree
    def traverse(node):
        # If the node is not None, recursively traverse the left subtree
        if node.left:
            traverse(node.left)
        # If the node is not None, recursively traverse the right subtree
        if node.right:
            traverse(node.right)
        # Append the node value to the list
        nodes.append(str(node.value))

    # Start the traversal from the root
    traverse(subtree_root)

    # Join the node values with the arrow separator
    result = ' -> '.join(nodes)
    return result

# Perform post-order traversal and print the result
print(post_order_traversal(root))

Wir fügen die Knoten nach den rekursiven Aufrufen hinzu, um die Post-Order-Traversierung zu implementieren.

War alles klar?

Danke für Ihr Feedback!

Abschnitt 4. Kapitel 5