Python - Pohon Biner

Pohon mewakili simpul yang dihubungkan oleh tepi. Ini adalah struktur data non-linier. Ini memiliki properti berikut.

  • Satu node ditandai sebagai node Root.
  • Setiap node selain root dikaitkan dengan satu node induk.
  • Setiap node dapat memiliki nomor arbiatry dari node chid.

Kami membuat struktur data pohon di python dengan menggunakan konsep os node yang dibahas sebelumnya. Kami menetapkan satu node sebagai node root dan kemudian menambahkan lebih banyak node sebagai node anak. Di bawah ini adalah program untuk membuat node root.

Buat Root

Kami baru saja membuat kelas Node dan menambahkan nilai ke node. Ini menjadi pohon dengan hanya satu simpul akar.

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

Ketika kode di atas dijalankan, itu menghasilkan hasil sebagai berikut -

10

Memasukkan ke dalam Pohon

Untuk menyisipkan ke dalam pohon kita menggunakan kelas simpul yang sama yang dibuat di atas dan menambahkan metode sisipkan padanya Metode sisipkan membandingkan nilai simpul ke simpul induk dan memutuskan untuk menambahkannya sebagai simpul kiri atau simpul kanan. Terakhir, metode PrintTree digunakan untuk mencetak pohon.

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

Ketika kode di atas dijalankan, itu menghasilkan hasil sebagai berikut -

3 6 12 14

Melintasi Pohon

Pohon dapat dilintasi dengan memutuskan urutan kunjungan setiap node. Seperti yang dapat kita lihat dengan jelas, kita dapat memulai dari sebuah simpul kemudian mengunjungi sub-pohon kiri pertama dan sub-pohon kanan berikutnya. Atau kita juga bisa mengunjungi sub-pohon kanan pertama dan sub-pohon kiri berikutnya. Oleh karena itu, ada beberapa nama berbeda untuk metode penjelajahan pohon ini. Kami mempelajarinya secara mendetail di bab yang menerapkan algoritme penjelajahan pohon di sini. Algoritma Penjelajahan Pohon