Drzewo binarne

Drzewa: drzewo binarne i drzewo poszukiwań - Informatyka - liceum klasa 3, zakres rozszerzony (Python)

**Drzewo binarne** składa się z **węzłów**. Każdy węzeł ma klucz i co najwyżej dwoje dzieci: lewe i prawe. Węzeł bez rodzica to **korzeń**, węzeł bez dzieci to **liść**. **Wysokość** drzewa to liczba węzłów na najdłuższej drodze od korzenia do liścia. Większość funkcji na drzewach jest rekurencyjna: wynik dla węzła składamy z wyników dla poddrzew.

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

tree = Node(8, Node(3, Node(1), Node(6, Node(4), Node(7))), Node(10, None, Node(14)))

def size(node):
    if node is None:
        return 0
    return 1 + size(node.left) + size(node.right)

def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))

print("węzłów:", size(tree), "wysokość:", height(tree))

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Informatyka - liceum klasa 3, zakres rozszerzony·Zaloguj się, aby zapisać postęp na koncie.