đại diện cho cây tìm kiếm nhị phân trong python

Question

làm thế nào để tôi đại diện cho cây tìm kiếm nhị phân trong python?

Answer 1

class Node(object): 

    def __init__(self, payload): 
    self.payload = payload 
    self.left = self.right = 0 

    # this concludes the "how to represent" asked in the question. Once you 
    # represent a BST tree like this, you can of course add a variety of 
    # methods to modify it, "walk" over it, and so forth, such as: 

    def insert(self, othernode): 
    "Insert Node `othernode` under Node `self`." 
    if self.payload <= othernode.payload: 
     if self.left: self.left.insert(othernode) 
     else: self.left = othernode 
    else: 
     if self.right: self.right.insert(othernode) 
     else: self.right = othernode 

    def inorderwalk(self): 
    "Yield this Node and all under it in increasing-payload order." 
    if self.left: 
     for x in self.left.inorderwalk(): yield x 
    yield self 
    if self.right: 
     for x in self.right.inorderwalk(): yield x 

    def sillywalk(self): 
    "Tiny, silly subset of `inorderwalk` functionality as requested." 
    if self.left: 
     self.left.sillywalk() 
    print(self.payload) 
    if self.right: 
     self.right.sillywalk() 

v.v ... về cơ bản giống như bất kỳ ngôn ngữ nào khác sử dụng tham chiếu hơn là con trỏ (như Java, C#, v.v ...).

Sửa:

Tất nhiên, sự tồn tại của sillywalk là ngớ ngẩn thực sự, bởi vì chính xác cùng chức năng là một đoạn bên ngoài singe-liner trên đầu trang của walk phương pháp:

for x in tree.walk(): print(x.payload) 

và với walk, bạn có thể có được bất kỳ chức năng nào khác trên luồng nút theo thứ tự, trong khi, với sillywalk, bạn có thể có được chỉ về diddly-squat. Nhưng, hey, OP nói yield là "đáng sợ" (Tôi tự hỏi có bao nhiêu từ khóa 30 khác của Python 2.6 xứng đáng với những từ sợ hãi như vậy trong phán đoán của OP? -) vì vậy tôi hy vọng print là không!

Đây là tất cả hoàn toàn vượt ra ngoài câu hỏi thực tế, trên đại diện BSTs: rằng câu hỏi hoàn toàn được trả lời trong __init__ - một thuộc tính payload để giữ trọng tải của nút, left và right thuộc tính để giữ một trong hai None (nghĩa , nút này không có hậu duệ ở bên đó) hoặc Node (đỉnh của cây con của hậu duệ ở bên thích hợp). Tất nhiên, ràng buộc BST là mọi hậu duệ bên trái của mỗi nút (nếu có) có trọng tải nhỏ hơn hoặc bằng với trọng số của nút đang được đề cập, mọi quyền (một lần nữa, nếu có) có trọng tải lớn hơn - tôi đã thêm insert chỉ để cho thấy tầm quan trọng của việc duy trì ràng buộc đó, walk (và bây giờ là sillywalk) để chỉ ra tầm quan trọng của việc thu thập tất cả các nút theo thứ tự tăng tải trọng. Một lần nữa, ý tưởng chung giống hệt như cách bạn muốn đại diện cho BST bằng bất kỳ ngôn ngữ nào sử dụng tham chiếu thay vì con trỏ, ví dụ như C# và Java.