Bagaimana untuk melaksanakan pokok binari dalam Python

Pelaksanaan python pokok binari

Pelaksanaan python pokok binari boleh dilaksanakan menggunakan pengaturcaraan berorientasikan objek dengan mentakrifkan kelas nod pokok binari. Setiap nod mengandungi elemen data, penunjuk nod anak kiri dan kanan dan beberapa kaedah operasi, seperti memasukkan nod, mencari nod, memadamkan nod, dsb.

Berikut ialah contoh pelaksanaan pokok binari yang mudah:

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

    def insert(self, data):
        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

    def find(self, data):
        if data < self.data:
            if self.left is None:
                return str(data) + " Not Found"
            return self.left.find(data)
        elif data > self.data:
            if self.right is None:
                return str(data) + " Not Found"
            return self.right.find(data)
        else:
            return str(self.data) + " is found"

    def inorder_traversal(self, root):
        res = []
        if root:
            res = self.inorder_traversal(root.left)
            res.append(root.data)
            res = res + self.inorder_traversal(root.right)
        return res

Dalam kod di atas, kelas Node mentakrifkan nod, yang mengandungi data elemen data dan penunjuk nod anak kiri dan kanan ke kiri dan betul. Kaedah sisipan digunakan untuk memasukkan nod ke dalam pokok binari, kaedah cari digunakan untuk mencari sama ada nod tertentu wujud dalam pokok binari, dan kaedah inorder_traversal digunakan untuk melakukan traversal tertib bagi pokok binari.

Begini cara menggunakan kelas Node ini untuk mencipta pokok binari:

root = Node(50)
root.insert(30)
root.insert(20)
root.insert(40)
root.insert(70)
root.insert(60)
root.insert(80)

# 查找节点

print(root.find(70)) # Output: 70 is found
print(root.find(90)) # Output: 90 Not Found

# 中序遍历
print(root.inorder_traversal(root)) # Output: [20, 30, 40, 50, 60, 70, 80]

Dalam kod di atas, akar nod akar pertama kali dibuat, kemudian kaedah sisipan digunakan untuk memasukkan nod ke dalam pokok, dan akhirnya menggunakan Kaedah find mencari nod dan menggunakan kaedah inorder_traversal untuk melakukan traversal tertib bagi pokok binari.

Selain kaedah sisipan, carian dan traversal, pokok binari juga mempunyai kaedah operasi lain, seperti memadamkan nod, menentukan sama ada ia adalah pokok carian binari, mengira kedalaman pokok, dsb. Berikut ialah kod contoh pokok binari yang lebih lengkap:

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

    def insert(self, data):
        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

    def find(self, data):
        if data < self.data:
            if self.left is None:
                return None
            return self.left.find(data)
        elif data > self.data:
            if self.right is None:
                return None
            return self.right.find(data)
        else:
            return self

    def delete(self, data):
        if self is None:
            return self

        if data < self.data:
            self.left = self.left.delete(data)
        elif data > self.data:
            self.right = self.right.delete(data)
        else:
            if self.left is None:
                temp = self.right
                self = None
                return temp
            elif self.right is None:
                temp = self.left
                self = None
                return temp
            temp = self.right.minimum()
            self.data = temp.data
            self.right = self.right.delete(temp.data)
        return self

    def minimum(self):
        if self.left is None:
            return self
        return self.left.minimum()

    def is_bst(self):
        if self.left:
            if self.left.data > self.data or not self.left.is_bst():
                return False

        if self.right:
            if self.right.data < self.data or not self.right.is_bst():
                return False

        return True

    def height(self, node):
        if node is None:
            return 0

        left_height = self.height(node.left)
        right_height = self.height(node.right)

        return max(left_height, right_height) + 1

    def inorder_traversal(self, root):
        res = []
        if root:
            res = self.inorder_traversal(root.left)
            res.append(root.data)
            res = res + self.inorder_traversal(root.right)
        return res

Dalam contoh ini, kami telah menambah kaedah padam untuk memadamkan nod yang ditentukan untuk mencari nod terkecil dalam pepohon; untuk menentukan semasa Sama ada pokok itu adalah pokok carian binari kaedah ketinggian digunakan untuk mengira kedalaman pokok.

Kami boleh menggunakan kod berikut untuk menguji kaedah baharu:

# 创建二叉树
root = Node(50)
root.insert(30)
root.insert(20)
root.insert(40)
root.insert(70)
root.insert(60)
root.insert(80)

# 删除节点
print("Deleting node 20:")
root.delete(20)
print(root.inorder_traversal(root))

# 判断是否为二叉搜索树
print("Is it a BST?:", root.is_bst())

# 计算树的深度
print("Tree height:", root.height(root))

Dengan cara ini, kami telah menyelesaikan pelaksanaan pokok binari yang agak lengkap, dan juga menunjukkan cara menggunakan pengaturcaraan berorientasikan objek dalam Idea Python untuk melaksanakan struktur data.

Akhir sekali, kod pelaksanaan kelas pokok binari yang lengkap dilampirkan:

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

    def insert(self, data):
        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

    def find(self, data):
        if data < self.data:
            if self.left is None:
                return None
            return self.left.find(data)
        elif data > self.data:
            if self.right is None:
                return None
            return self.right.find(data)
        else:
            return self

    def delete(self, data):
        if self is None:
            return self

        if data < self.data:
            self.left = self.left.delete(data)
        elif data > self.data:
            self.right = self.right.delete(data)
        else:
            if self.left is None:
                temp = self.right
                self = None
                return temp
            elif self.right is None:
                temp = self.left
                self = None
                return temp
            temp = self.right.minimum()
            self.data = temp.data
            self.right = self.right.delete(temp.data)
        return self

    def minimum(self):
        if self.left is None:
            return self
        return self.left.minimum()

    def is_bst(self):
        if self.left:
            if self.left.data > self.data or not self.left.is_bst():
                return False

        if self.right:
            if self.right.data < self.data or not self.right.is_bst():
                return False

        return True

    def height(self, node):
        if node is None:
            return 0

        left_height = self.height(node.left)
        right_height = self.height(node.right)

        return max(left_height, right_height) + 1

    def inorder_traversal(self, root):
        res = []
        if root:
            res = self.inorder_traversal(root.left)
            res.append(root.data)
            res = res + self.inorder_traversal(root.right)
        return res

if __name__ == '__main__':
    # 创建二叉树
    root = Node(50)
    root.insert(30)
    root.insert(20)
    root.insert(40)
    root.insert(70)
    root.insert(60)
    root.insert(80)

    # 删除节点
    print("Deleting node 20:")
    root.delete(20)
    print(root.inorder_traversal(root))

    # 判断是否为二叉搜索树
    print("Is it a BST?:", root.is_bst())

    # 计算树的深度
    print("Tree height:", root.height(root))

Selepas menjalankan kod, anda boleh mendapatkan output berikut:

Memadamkan nod 20 :
[30, 40, 50, 60, 70, 80]
Adakah ia BST?: Benar
Ketinggian pokok: 3

Contoh ini termasuk memasukkan dan mencari , memadam, melintasi, menentukan sama ada ia adalah pokok carian binari dan mengira kedalaman pokok itu, dsb.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan pokok binari dalam Python. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!