Python - drzewo binarne

Drzewo reprezentuje węzły połączone krawędziami. Jest to nieliniowa struktura danych. Posiada następujące właściwości.

Jeden węzeł jest oznaczony jako węzeł główny.
Każdy węzeł inny niż główny jest powiązany z jednym węzłem nadrzędnym.
Każdy węzeł może mieć przypisany numer węzła chid.

Tworzymy drzewiastą strukturę danych w Pythonie, używając omówionej wcześniej koncepcji węzła os. Wyznaczamy jeden węzeł jako węzeł główny, a następnie dodajemy więcej węzłów jako węzły potomne. Poniżej znajduje się program do tworzenia węzła głównego.

Utwórz root

Po prostu tworzymy klasę Node i dodajemy przypisaną wartość do węzła. To staje się drzewem z tylko węzłem głównym.

class Node:

    def __init__(self, data):

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


    def PrintTree(self):
        print(self.data)

root = Node(10)

root.PrintTree()

Wykonanie powyższego kodu daje następujący wynik -

Wstawianie do drzewa

Aby wstawić do drzewa, używamy tej samej klasy węzłów utworzonej powyżej i dodajemy do niej metodę wstawiania. Metoda wstawiania porównuje wartość węzła z węzłem nadrzędnym i decyduje się dodać ją jako lewy lub prawy węzeł. Na koniec do wydrukowania drzewa używana jest metoda PrintTree.

class Node:

    def __init__(self, data):

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

    def insert(self, data):
# Compare the new value with the parent node
        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

# Print the tree
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()

# Use the insert method to add nodes
root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)

root.PrintTree()

Wykonanie powyższego kodu daje następujący wynik -

3 6 12 14

Przechodzenie po drzewie

Po drzewie można przejść, decydując się na sekwencję odwiedzania każdego węzła. Jak wyraźnie widać, możemy zacząć od węzła, a następnie odwiedzić najpierw lewe poddrzewo, a następnie prawe poddrzewo. Lub możemy również odwiedzić najpierw prawe poddrzewo, a następnie lewe poddrzewo. W związku z tym istnieją różne nazwy tych metod przechodzenia po drzewie. Szczegółowo omawiamy je w rozdziale poświęconym implementacji algorytmów przechodzenia po drzewie. Algorytmy przechodzenia po drzewie