Hướng dẫn how do you implement a tree in python? - làm thế nào để bạn triển khai một cái cây trong python?

Xin chào, bạn có thể thử Itertree (tôi là tác giả).

Gói đi theo hướng của gói AnyTree nhưng với một chút tiêu điểm khác nhau. Hiệu suất trên các cây khổng lồ (> 100000 mặt hàng) tốt hơn nhiều và nó liên quan đến các trình lặp để có cơ chế lọc hiệu quả.

>>>from itertree import *
>>>root=iTree('root')

>>># add some children:
>>>root.append(iTree('Africa',data={'surface':30200000,'inhabitants':1257000000}))
>>>root.append(iTree('Asia', data={'surface': 44600000, 'inhabitants': 4000000000}))
>>>root.append(iTree('America', data={'surface': 42549000, 'inhabitants': 1009000000}))
>>>root.append(iTree('Australia&Oceania', data={'surface': 8600000, 'inhabitants': 36000000}))
>>>root.append(iTree('Europe', data={'surface': 10523000 , 'inhabitants': 746000000}))
>>># you might use __iadd__ operator for adding too:
>>>root+=iTree('Antarktika', data={'surface': 14000000, 'inhabitants': 1100})

>>># for building next level we select per index:
>>>root[0]+=iTree('Ghana',data={'surface':238537,'inhabitants':30950000})
>>>root[0]+=iTree('Niger', data={'surface': 1267000, 'inhabitants': 23300000})
>>>root[1]+=iTree('China', data={'surface': 9596961, 'inhabitants': 1411780000})
>>>root[1]+=iTree('India', data={'surface': 3287263, 'inhabitants': 1380004000})
>>>root[2]+=iTree('Canada', data={'type': 'country', 'surface': 9984670, 'inhabitants': 38008005})    
>>>root[2]+=iTree('Mexico', data={'surface': 1972550, 'inhabitants': 127600000 })
>>># extend multiple items:
>>>root[3].extend([iTree('Australia', data={'surface': 7688287, 'inhabitants': 25700000 }), iTree('New Zealand', data={'surface': 269652, 'inhabitants': 4900000 })])
>>>root[4]+=iTree('France', data={'surface': 632733, 'inhabitants': 67400000 }))
>>># select parent per TagIdx - remember in itertree you might put items with same tag multiple times:
>>>root[TagIdx('Europe'0)]+=iTree('Finland', data={'surface': 338465, 'inhabitants': 5536146 })

Cây được tạo ra có thể được kết xuất:

>>>root.render()
iTree('root')
     └──iTree('Africa', data=iTData({'surface': 30200000, 'inhabitants': 1257000000}))
         └──iTree('Ghana', data=iTData({'surface': 238537, 'inhabitants': 30950000}))
         └──iTree('Niger', data=iTData({'surface': 1267000, 'inhabitants': 23300000}))
     └──iTree('Asia', data=iTData({'surface': 44600000, 'inhabitants': 4000000000}))
         └──iTree('China', data=iTData({'surface': 9596961,  'inhabitants': 1411780000}))
         └──iTree('India', data=iTData({'surface': 3287263, 'inhabitants': 1380004000}))
     └──iTree('America', data=iTData({'surface': 42549000, 'inhabitants': 1009000000}))
         └──iTree('Canada', data=iTData({'surface': 9984670, 'inhabitants': 38008005}))
         └──iTree('Mexico', data=iTData({'surface': 1972550, 'inhabitants': 127600000}))
     └──iTree('Australia&Oceania', data=iTData({'surface': 8600000, 'inhabitants': 36000000}))
         └──iTree('Australia', data=iTData({'surface': 7688287, 'inhabitants': 25700000}))
         └──iTree('New Zealand', data=iTData({'surface': 269652, 'inhabitants': 4900000}))
     └──iTree('Europe', data=iTData({'surface': 10523000, 'inhabitants': 746000000}))
         └──iTree('France', data=iTData({'surface': 632733, 'inhabitants': 67400000}))
         └──iTree('Finland', data=iTData({'surface': 338465, 'inhabitants': 5536146}))
     └──iTree('Antarktika', data=iTData({'surface': 14000000, 'inhabitants': 1100}))

Ví dụ. Lọc có thể được thực hiện như thế này:

>>>item_filter = Filter.iTFilterData(data_key='inhabitants', data_value=iTInterval(0, 20000000))
>>>iterator=root.iter_all(item_filter=item_filter)
>>>for i in iterator:
>>>    print(i)
iTree("'New Zealand'", data=iTData({'surface': 269652, 'inhabitants': 4900000}), subtree=[])
iTree("'Finland'", data=iTData({'surface': 338465, 'inhabitants': 5536146}), subtree=[])
iTree("'Antarktika'", data=iTData({'surface': 14000000, 'inhabitants': 1100}), subtree=[])

Cây là các cấu trúc dữ liệu phi tuyến tính đại diện cho các nút được kết nối bởi các cạnh. Mỗi cây bao gồm một nút gốc làm nút cha và nút bên trái và nút phải làm nút con. are non-linear data structures that represent nodes connected by edges. Each tree consists of a root node as the Parent node, and the left node and right node as Child nodes.

Cây nhị phân

Một cây có nhiều yếu tố có nhiều nhất là hai đứa trẻ được gọi là cây nhị phân. Mỗi yếu tố trong một cây nhị phân chỉ có thể có hai đứa con. Một đứa trẻ bên trái của nút phải có giá trị thấp hơn giá trị cha mẹ của nó và đứa con bên phải của nút phải có giá trị lớn hơn giá trị cha mẹ của nó.

%0 node_127 node_214 node_1->node_2 node_335 node_1->node_3 node_159309474347810 node_2->node_1593094743478 node_15930947425849 node_2->node_1593094742584 node_159309480342531 node_3->node_1593094803425 node_159309477358442 node_3->node_1593094773584

Thực hiện

Ở đây chúng tôi đã tạo một lớp node và gán một giá trị cho nút.

# node class
class Node:
    def __init__(self, data):
        # left child
        self.left = None
        # right child
        self.right = None
        # node's value
        self.data = data
    # print function
    def PrintTree(self):
        print(self.data)
root = Node(27)
root.PrintTree()

Mã trên sẽ tạo nút 27 dưới dạng nút cha.

Chèn

Phương thức insert so sánh giá trị của nút với nút cha và quyết định có nên thêm nó dưới dạng nút bên trái hay nút phải hay không.

Hãy nhớ rằng: nếu nút lớn hơn nút cha, nó được chèn dưới dạng nút bên phải; Nếu không, nó đã chèn trái.

Cuối cùng, phương pháp PrintTree được sử dụng để in cây.

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(27)
root.insert(14)
root.insert(35)
root.insert(31)



root.insert(10)
root.insert(19)
root.PrintTree()

Mã trên sẽ tạo nút gốc là 27, con trái là 14 và con phải là 35.

Đang tìm kiếm

Trong khi tìm kiếm một giá trị trong cây, chúng ta cần đi qua nút từ trái sang phải và với cha mẹ.

class Node:
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data
# Insert method to create nodes
    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
# findval method to compare the value with nodes
    def findval(self, lkpval):
        if lkpval < self.data:
            if self.left is None:
                return str(lkpval)+" is not Found"
            return self.left.findval(lkpval)



 elif lkpval > self.data:
 if self.right is None:
 return str(lkpval)+" is not Found"
 return self.right.findval(lkpval)
 else:
 return str(self.data) + " is found"
# Print the tree
 def PrintTree(self):
 if self.left:
 self.left.PrintTree()
 print(self.data),
 if self.right:
 self.right.PrintTree()
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(31)
root.insert(10)
root.insert(19)
print(root.findval(7))
print(root.findval(14))

Ở đây nó tạo ra cây 10 19 14 27 31 35 nút. Trong cây này, 7 nút không có ở đó nên nó cung cấp cho đầu ra như 7 không tìm thấy. 14 là rễ con trái.

THẺ LIÊN QUAN

Cây nhị phân

Tạo nút

Chèn một nút

Tìm kiếm một nút

cộng đồng

Làm thế nào để bạn thực hiện một cây?

Làm cách nào để tạo sơ đồ cây trong Python?

Làm thế nào để bạn tạo một cây dữ liệu trong Python?

Làm thế nào để cây hoạt động trong Python?