Hướng dẫn python build tree from list - python xây dựng cây từ danh sách

Giả sử tôi có cây nhị phân sau:

và định nghĩa

def build_tree(values: list) -> ListNode:
    ...

class TreeNode:
    def __init__(self, x, left: = None, right: = None):
        self.val = x
        self.left = left
        self.right = right

Để xây dựng cây này, hiện tại tôi cần phải viết mã sau:

def build_tree() -> TreeNode:
    node0 = TreeNode(2, left=TreeNode(4), right=TreeNode(5))
    node1 = TreeNode(3, right=TreeNode(7))
    root = TreeNode(1, left=node0, right=node1)
    return root

Điều này rất không hiệu quả cho những cây lớn. LeetCode cho tôi cây làm danh sách Python. Đối với ví dụ trên, nó viết:

[1, 2, 3, 4, 5, None, 7]

Tôi rất thích tái cấu trúc

def build_tree(values: list) -> ListNode:
    ...

def build_tree(values: list) -> ListNode:
    ...

Bất kỳ ý tưởng về cách tạo chức năng này?

Đây là một ví dụ phức tạp hơn:

[4, 6, 2, None, 5, 1, 9, 2, 1, 3, 4, None, 7]

TreeNode trong Python là gì?

Python Treende Class A Treenode là một cấu trúc dữ liệu đại diện cho một mục của cây, bao gồm nhiều nút như vậy. Nút trên cùng của một cây được gọi là gốc rễ và mỗi nút (ngoại trừ nút gốc) được liên kết với một nút cha.

Giới thiệu

1. Bộ sưu tập dữ liệu trong Python có thể được tổ chức theo nhiều cách. Nhưng tùy thuộc vào những gì chúng tôi muốn làm với một bộ sưu tập, một số cách tiếp cận tốt hơn những cách khác.
2. Trong dự án này, chúng tôi sẽ xem xét ngắn gọn các danh sách đơn giản, danh sách được liên kết và cuối cùng là cây nhị phân. Trong mỗi trường hợp, chúng tôi muốn có thể thực hiện các hoạt động sau một cách hiệu quả.
3. Chèn một mục dữ liệu mới (giá trị) vào bộ sưu tập.

Xem nếu một giá trị nhất định là trong bộ sưu tập.

Xóa một giá trị khỏi bộ sưu tập.

Nó thường giúp nếu bộ sưu tập được sắp xếp để tìm kiếm có thể được tối ưu hóa. Nói chung, việc tìm kiếm các mục thường xuyên hơn nhiều để chèn hoặc loại bỏ các mục.

1. Để giữ mọi thứ đơn giản, chúng tôi sẽ cho rằng các bộ sưu tập của chúng tôi được sắp xếp. Điều đó có nghĩa là chúng ta phải có khả năng so sánh các mục với các toán tử ít hơn, bằng và lớn hơn.
2. Ngoài ra, để giữ cho mọi thứ đơn giản, chúng tôi sẽ sử dụng các ví dụ trong đó
3. Giá trị dữ liệu là số nguyên đơn giản

Giá trị là duy nhất.

Các danh sách và cây luôn được sắp xếp.

>>> collection = [3,6,9,17]
>>> collection
[3, 6, 9, 17]

Danh sách tích hợp Python đơn giản

>>> collection.append(25)
>>> collection
[3, 6, 9, 17, 25]

Cách dễ nhất để tạo một bộ sưu tập một danh sách là chỉ cần sử dụng danh sách Python tích hợp. Số nguyên bộ sưu tập này được sắp xếp.

>>> 9 in collection
True
>>> 8 in collection
False

Chúng ta có thể chèn một giá trị mới với phương thức phụ lục

>>> def contains(collection, value) :
...     if not collection           : return False    # collection empty
...     elif value == collection[0] : return True     # value is in the first slot
...     else : return contains(collection[1:], value) # value is somewhere further?
...
>>> contains(collection, 17)
True
>>> contains(collection, 10)
False

Chúng ta có thể kiểm tra xem một mục nhất định có trong bộ sưu tập không.

>>> def contains(collection, value) :
...     if not collection           : return False
...     elif value == collection[0] : return True
...     elif value <  collection[0] : return False     # only if sorted
...     else : return contains(collection[1:], value)

Và nếu Python không có toán tử, chúng ta có thể tạo một chức năng như sau. Lưu ý rằng chức năng này là đệ quy. Nó cũng có thể được viết với một thời gian hoặc cho vòng lặp. Nhưng phiên bản này có thể phục vụ như một giới thiệu về các cấu trúc phức tạp hơn sau này.

def build_tree() -> TreeNode:
    node0 = TreeNode(2, left=TreeNode(4), right=TreeNode(5))
    node1 = TreeNode(3, right=TreeNode(7))
    root = TreeNode(1, left=node0, right=node1)
    return root

Hoặc, nếu chúng ta biết danh sách được sắp xếp, chúng ta có thể dừng sớm

Để loại bỏ một giá trị, chúng ta có thể tách danh sách xung quanh nó. Ở đây chúng ta sẽ sử dụng một vòng lặp để tìm điểm phân chia.

Danh sách liên kết

def build_tree() -> TreeNode:
    node0 = TreeNode(2, left=TreeNode(4), right=TreeNode(5))
    node1 = TreeNode(3, right=TreeNode(7))
    root = TreeNode(1, left=node0, right=node1)
    return root

Danh sách được liên kết của chúng tôi sẽ được xây dựng với các nút chứa cả giá trị và con trỏ đến nút tiếp theo.

def build_tree() -> TreeNode:
    node0 = TreeNode(2, left=TreeNode(4), right=TreeNode(5))
    node1 = TreeNode(3, right=TreeNode(7))
    root = TreeNode(1, left=node0, right=node1)
    return root

Chúng tôi có thể tạo danh sách được liên kết của chúng tôi bằng danh sách Python 2 phần tử đơn giản cho mỗi nút. Phần tử đầu tiên của một nút là giá trị của nó và phần tử thứ hai là các nút còn lại. Nút cuối cùng trong danh sách được liên kết sẽ có giá trị không có trong phần tử thứ hai. Đây là một ví dụ.

def build_tree() -> TreeNode:
    node0 = TreeNode(2, left=TreeNode(4), right=TreeNode(5))
    node1 = TreeNode(3, right=TreeNode(7))
    root = TreeNode(1, left=node0, right=node1)
    return root

Sử dụng một cách tiếp cận chức năng hơn làm cho mã chặt chẽ hơn chỉ với một dòng duy nhất cho mỗi trong ba điều kiện. Nó là một chút khó khăn hơn mặc dù.

Điều quan trọng là bạn hiểu những gì đang xảy ra trong dòng 37. Nó thay thế các dòng 23-32 trong phiên bản đầu tiên. Trong các cuộc gọi liên tiếp từ dòng 37, danh sách được chuyển qua cho đến khi tìm thấy điểm chèn. Sau đó, một danh sách phụ mới được thực hiện theo định hướng của giá trị mới và theo sau là phần còn lại của danh sách ban đầu. Và cuối cùng, tất cả các nút trước điểm chèn đã sao chép lại từ đầu. Những gì chúng ta có là một danh sách mới chia sẻ một đuôi của các nút với bản gốc. Dành thời gian của bạn.

def build_tree() -> TreeNode:
    node0 = TreeNode(2, left=TreeNode(4), right=TreeNode(5))
    node1 = TreeNode(3, right=TreeNode(7))
    root = TreeNode(1, left=node0, right=node1)
    return root

Nếu chúng ta in các giá trị trả về liên tiếp, chúng sẽ trông như thế này:

def build_tree() -> TreeNode:
    node0 = TreeNode(2, left=TreeNode(4), right=TreeNode(5))
    node1 = TreeNode(3, right=TreeNode(7))
    root = TreeNode(1, left=node0, right=node1)
    return root

Xóa một nút cũng có thể được thực hiện theo hai cách.

Cách tiếp cận đầu tiên trong việc xóa Node N là sửa đổi con trỏ nút trước đó để bỏ qua N. trong các dòng 40 và 41 của Delete1 () Các trường hợp đặc biệt (đầu tiên và cuối cùng) được xử lý.

def build_tree() -> TreeNode:
    node0 = TreeNode(2, left=TreeNode(4), right=TreeNode(5))
    node1 = TreeNode(3, right=TreeNode(7))
    root = TreeNode(1, left=node0, right=node1)
    return root

Delete2 () là một sự chấp thuận đơn giản hơn. Về cơ bản, nó xây dựng một danh sách mới với các nút còn lại vẫn theo đúng thứ tự. Nếu chúng ta biết các giá trị là duy nhất và được sắp xếp thì danh sách được liên kết mới kết quả thực sự có thể hợp nhất với điểm ban đầu của điểm xóa. Điều này rất giống với chèn2 () ở trên.

def build_tree() -> TreeNode:
    node0 = TreeNode(2, left=TreeNode(4), right=TreeNode(5))
    node1 = TreeNode(3, right=TreeNode(7))
    root = TreeNode(1, left=node0, right=node1)
    return root

Hàm showList () in danh sách với các giá trị nút được tách biệt bởi "->", như trong ví dụ trên.

def build_tree() -> TreeNode:
    node0 = TreeNode(2, left=TreeNode(4), right=TreeNode(5))
    node1 = TreeNode(3, right=TreeNode(7))
    root = TreeNode(1, left=node0, right=node1)
    return root

Các danh sách mô-đun.py cũng có thể được chạy độc lập để thử nghiệm các phiên bản đệ quy của chèn và xóa

def build_tree() -> TreeNode:
    node0 = TreeNode(2, left=TreeNode(4), right=TreeNode(5))
    node1 = TreeNode(3, right=TreeNode(7))
    root = TreeNode(1, left=node0, right=node1)
    return root

Tuples cho các danh sách được liên kết

Với các phiên bản chức năng của chèn (), chứa () và xóa (), chúng ta không còn phải sửa đổi các nút hiện có. Danh sách 2 phần tử có thể được thay thế bằng 2 bộ dữ liệu phần tử. Đây là một ý tưởng tốt vì hai lý do. Một, bộ dữ liệu sử dụng bộ nhớ ít hơn nhiều so với danh sách và hai, không thể sửa đổi các nút là một điều rất tốt. Thực hiện các sửa đổi cho các cấu trúc danh sách có thể dẫn đến các lỗi tinh tế, đặc biệt là nếu các danh sách được chia sẻ bởi các luồng đồng thời.

Các chương trình Python danh sách.py ​​và Tuples.py có thể được xem một cách riêng biệt. Họ khá giống nhau.

Tệp zip. Tải xuống toàn bộ gói

Cây nhị phân

Cây nhị phân về cơ bản là các danh sách liên kết hai chiều. Mỗi nút có giá trị và con trỏ cho hai cây con, một bên trái và một bên phải. Cả hai cây con có thể là giá trị không có hoặc là nút gốc cho một cây nhị phân khác. Subtree bên trái chỉ chứa các nút có giá trị nhỏ hơn giá trị của nút cha. Subtree bên phải chỉ chứa các nút có giá trị lớn hơn. Vì điều này đúng với mọi nút, toàn bộ mạng của các nút được sắp xếp.

Như chúng tôi đã làm ở trên, chúng tôi sẽ sử dụng giá trị nút Node để xác định nó. Vì vậy, "Node 70" là nút chứa giá trị của 70. Tất nhiên, giống như trong các danh sách được liên kết, các giá trị trong thế giới thực không phải là số nguyên. Họ có thể có bất kỳ hình thức.

Một cây nhị phân là một cấu trúc dữ liệu đệ quy. Đây là một ví dụ. Lưu ý rằng trong mọi giá trị cây con bên trái ít hơn bất kỳ nút nào ở trên và các nút bên phải lớn hơn.

Bạn có thể thấy làm thế nào các nút 20 và 70 không có cây con tay phải và cách các nút 10, 40, 60 và 90 không có cây con nào cả.

Cây được cân bằng. Mặc dù có chín nút trong cây, mỗi nút có thể đạt được từ gốc trong ba bước hoặc ít hơn.

Đại diện Python của cây này là như sau.

[1, 2, 3, 4, 5, None, 7]

Như với các danh sách được liên kết, chúng tôi muốn có thể làm như sau:

1. Tìm nếu cây chứa một giá trị
2. chèn một nút mới và giá trị của nó
3. Xóa giá trị nút.

Mã để tìm một giá trị là đơn giản. Hàm chứa () bắt đầu ở nút gốc và đi qua cây với mỗi bước sang trái hoặc phải. Nếu nó hạ cánh trên nút với giá trị đích, nó sẽ trả về đúng. Đạt được kết thúc trả về sai. Giá trị cuối cùng được truyền lại thông qua loạt lợi nhuận và cuối cùng bật ra ở phía trên.

[1, 2, 3, 4, 5, None, 7]

Và đây là hành động…

[1, 2, 3, 4, 5, None, 7]

Chèn một nút mới

Chèn một nút mới ở đâu đó trong cây đòi hỏi trước tiên đòi hỏi phải tìm đúng nơi để chèn. Sau đó, chúng tôi xây dựng một danh sách các nút mới được liên kết đưa chúng tôi trở lại một gốc mới và giữ càng nhiều bản gốc càng tốt. Với mỗi lần trả lại bằng các dòng 25,27,28,30,32, chúng tôi tạo một nút mới được liên kết với các dòng bên dưới nó.

[1, 2, 3, 4, 5, None, 7]

Dưới đây là sơ đồ kết quả của việc thêm giá trị 65. Các nút màu vàng là từ cây gốc và bạn có thể kiểm tra điều này bằng cách nhìn vào ID của chúng. Các nút màu đỏ là mới và dẫn trở lại đỉnh vào cây. Cây ban đầu tiếp tục tồn tại. Cây mới có một gốc mới nhưng hợp nhất với bản gốc nơi nó có thể.

Vì vậy, chúng ta thấy rằng cây ban đầu vẫn còn nguyên vẹn và được tham chiếu bởi Oldtree

[1, 2, 3, 4, 5, None, 7]

Xóa các nút

Xóa một nút có phần phức tạp hơn. Sau đây cho thấy hiệu quả của việc xóa nút 40.

Về cơ bản, khi gốc của một cây con bị xóa, một trong các nút khác phải thay thế nó. Nút gốc mới phải duy trì các điều kiện. Nút tối thiểu ở cây con bên phải hoạt động tốt vì giá trị của nó vẫn lớn hơn bất cứ thứ gì ở cây con bên trái và nhỏ hơn bất kỳ nút nào khác ở bên phải. Một quy trình thậm chí đơn giản hơn có thể được sử dụng nếu một trong hai cây con trống.

Nếu chúng tôi đã tìm thấy nút để xóa (dòng 44) và nếu cả hai nhánh trái và phải thì chúng tôi tìm thấy giá trị tối thiểu ở phía bên phải bằng hàm minval. Một nút mới được tạo (dòng 48) và một nhánh mới được xây dựng (màu đỏ) trở lại đầu.

Nếu nhánh trái hoặc bên phải trống thì nhánh khác có thể chỉ cần thay thế nút bị xóa (dòng 49,50). Các dòng 51 đến 54 đi qua cây để tìm nút để xóa. Đây là mã.

[1, 2, 3, 4, 5, None, 7]

Cân bằng một cái cây

Một cây cân bằng tối ưu có thể rất hiệu quả về thời gian. Trong một cây cân bằng với 1024 nút, mỗi nút trong vòng 10 bước của gốc (210 là 1024). Xóa và chèn tạo các cây mới chỉ bằng cách xây dựng các đường dẫn mới có độ dài 10 trên 11. Nhưng hiệu quả này có thể bị phá vỡ nếu chuỗi chèn không phải là ngẫu nhiên.

Trong hình tiếp theo, 2 nút đã được chèn. Họ bỏ cây hơi mất cân bằng. Thay vì tất cả các nút ở trong vòng 3 bước từ gốc, nút 62 cách đó năm bước

Sau khi tái cân bằng, tất cả các nút lại ở trong 3 bước từ gốc.

Dưới đây là các chức năng để thực hiện điều này. Ý tưởng là chuyển đổi cây thành một danh sách python được sắp xếp. Điều này được thực hiện trong các giá trị bằng cách đơn giản là đi qua cây từ trái sang phải đệ quy. Khi danh sách hoàn thành, gốc tối ưu cho cây nhị phân nằm giữa danh sách. Lấy các giá trị ở bên trái của gốc của chúng tôi và tạo một cây con cho liên kết bên trái của nó. Các giá trị bên phải tạo ra một cây con cho liên kết bên phải của nó. Làm điều này đệ quy và một cây cân bằng chỉ đơn giản là mở ra.

Các giá trị chức năng xây dựng danh sách python được sắp xếp. Việc sắp xếp xảy ra tự động bằng cách cây bị đi qua. Chức năng cân bằng2 cũng đệ quy và một nút rễ phụ được chèn ở mỗi lần lặp.

[1, 2, 3, 4, 5, None, 7]

Nếu số lượng nút là sức mạnh của 2 thì cây sẽ được cân bằng hoàn hảo. Nếu không, sẽ có một một phần được lấp đầy trong hàng ở phía dưới từ phải sang trái.

Đồ họa cho cây nhị phân

Chương trình test.py sử dụng Bintree.py và Display.py để tạo đồ họa tương tự như các bản trên (được tạo bởi phiên bản pygame trước đó).

Đến lượt, Display.py sử dụng đồ họa của John Zelle.py để tạo Windows. Bạn cần phải cài đặt tkinter nhưng bạn không còn cần pygame nữa. Các mô -đun Python trong dự án và đồ họa.py tương thích với cả Python 2.7 và Python 3. Bạn cũng có thể sử dụng.

$ python test.py (hoặc python3 test.py)

Điều này sẽ vẽ một cửa sổ với cây trên, 3 nút ở phía dưới và mục nhập văn bản cho một số. Nút Thêm/Del sẽ chèn số hoặc xóa nó. Nút cân bằng sẽ cân bằng lại cây và nút thoát khá rõ ràng.

Dưới đây là mã cho mô -đun hiển thị.

Cửa sổ khá lớn (600 pixel). Có danh sách toàn cầu cho các nút và cho các mục tạm thời rút ra. Một hộp nhập duy nhất cho phép bạn nhập một số cho một nút để thêm hoặc delelte.

[1, 2, 3, 4, 5, None, 7]

Các mục tĩnh trong cửa sổ là 3 nút gần phía dưới và hộp nhập văn bản.

[1, 2, 3, 4, 5, None, 7]

Chức năng chờ đợi của người dùng. Bạn có thể thêm một số vào hộp nhập. Nhấp vào chuột trong trực tràng của nút sẽ trả về nhãn của nút (dòng 29) hoặc giá trị của mục nhập văn bản. (dòng 28). Các nhấp chuột khác bị bỏ qua.

[1, 2, 3, 4, 5, None, 7]

Các chức năng dưới đây là khá nhiều đĩa nồi hơi và đơn giản nếu bạn quen thuộc với mô-đun Đồ họa Zelle. (liên kết cần thiết)

def build_tree(values: list) -> ListNode:
    ...

DRAPEDODE () thú vị hơn. Nó đệ quy vẽ các cây con, từ trên xuống, trái và phải. Các dòng kết nối các nút và văn bản của một nút được vẽ màu vàng nếu một phần của cây trước (dòng 66) hoặc màu đỏ nếu mới tạo (67). IDS là danh sách ID Python để gắn thẻ các nút trước đó

def build_tree(values: list) -> ListNode:
    ...

Tải xuống và giải nén Bintree.zip

Các gói

Các thuật toán cơ bản này để thao tác các cây nhị phân khá thẳng về phía trước và khá nhanh và hiệu quả. Họ tìm thấy việc sử dụng ở nhiều nơi.

Cuối cùng, khi có thể, các cấu trúc dữ liệu đệ quy phải luôn được xử lý với các thuật toán đệ quy. Các ngôn ngữ hiện đại, như Python, làm cho điều này khá đơn giản. Và, mặc dù có một đường cong học tập, nó chắc chắn là đáng để nỗ lực.

Nếu bạn có nhận xét hoặc đề xuất, bạn có thể gửi email cho tôi tại Mail cho tôi

Bản quyền © 2019-2021 Chris Meyers và Fred Obermann

* * *

Làm thế nào để bạn chuyển đổi một danh sách thành một cây trong Python?

Đầu ra. ....

Làm thế nào để bạn tạo một cây nhị phân từ một danh sách các số?

TreeNode trong Python là gì?