Liệt kê cây nhị phân Python

Trong một cây được đại diện bởi một danh sách các danh sách, chúng ta sẽ bắt đầu với cấu trúc dữ liệu danh sách của Python và viết các hàm được định nghĩa ở trên. Mặc dù việc viết giao diện dưới dạng một tập hợp các thao tác trong danh sách hơi khác so với các kiểu dữ liệu trừu tượng khác mà chúng tôi đã triển khai, nhưng thật thú vị khi làm như vậy vì nó cung cấp cho chúng tôi cấu trúc dữ liệu đệ quy đơn giản mà chúng tôi có thể xem và kiểm tra trực tiếp. Trong một danh sách dạng cây danh sách, chúng ta sẽ lưu trữ giá trị của nút gốc là phần tử đầu tiên của danh sách. Phần tử thứ hai của danh sách sẽ tự nó là một danh sách đại diện cho cây con bên trái. Phần tử thứ ba của danh sách sẽ là một danh sách khác đại diện cho cây con bên phải. Để minh họa kỹ thuật lưu trữ này, hãy xem một ví dụ. Hình 1 cho thấy một cây đơn giản và việc thực hiện danh sách tương ứng

Hình 1. một cây nhỏ

myTree = ['a',   #root
      ['b',  #left subtree
       ['d', [], []],
       ['e', [], []] ],
      ['c',  #right subtree
       ['f', [], []],
       [] ]
     ]

Lưu ý rằng chúng ta có thể truy cập các cây con của danh sách bằng cách lập chỉ mục danh sách tiêu chuẩn. Gốc của cây là myTree[0], cây con bên trái của gốc là

def BinaryTree(r):
    return [r, [], []]

0 và cây con bên phải là

def BinaryTree(r):
    return [r, [], []]

1. ActiveCode 1 minh họa việc tạo một cây đơn giản bằng danh sách. Sau khi cây được xây dựng, chúng ta có thể truy cập vào gốc và các cây con bên trái và bên phải. Một thuộc tính rất hay của cách tiếp cận danh sách các danh sách này là cấu trúc của danh sách đại diện cho một cây con tuân theo cấu trúc được xác định cho một cây; . Một cây con có một giá trị gốc và hai danh sách trống là một nút lá. Một tính năng hay khác của cách tiếp cận danh sách các danh sách là nó tổng quát hóa cho một cây có nhiều cây con. Trong trường hợp cây nhiều hơn cây nhị phân, cây con khác chỉ là một danh sách khác

Hãy chính thức hóa định nghĩa này về cấu trúc dữ liệu dạng cây bằng cách cung cấp một số hàm giúp chúng ta dễ dàng sử dụng danh sách dưới dạng cây. Lưu ý rằng chúng ta sẽ không định nghĩa một lớp cây nhị phân. Các hàm chúng ta sẽ viết sẽ chỉ giúp chúng ta thao tác với một danh sách chuẩn như thể chúng ta đang làm việc với một cái cây

def BinaryTree(r):
    return [r, [], []]

Hàm

def BinaryTree(r):
    return [r, [], []]

2 chỉ cần tạo danh sách có nút gốc và hai danh sách con trống cho các phần tử con. Để thêm một cây con bên trái vào gốc của cây, chúng ta cần chèn một danh sách mới vào vị trí thứ hai của danh sách gốc. Chúng ta phải cẩn thận. Nếu danh sách đã có thứ gì đó ở vị trí thứ hai, chúng ta cần theo dõi nó và đẩy nó xuống dưới dạng cây con bên trái của danh sách mà chúng ta đang thêm. Liệt kê 1 hiển thị mã Python để chèn con bên trái

Liệt kê 1

def insertLeft(root,newBranch):
    t = root.pop(1)
    if len(t) > 1:
        root.insert(1,[newBranch,t,[]])
    else:
        root.insert(1,[newBranch, [], []])
    return root

Lưu ý rằng để chèn một phần tử con bên trái, trước tiên chúng ta lấy danh sách (có thể trống) tương ứng với phần tử con bên trái hiện tại. Sau đó, chúng tôi thêm phần tử con bên trái mới, cài đặt phần tử con bên trái cũ làm phần tử con bên trái của phần tử mới. Điều này cho phép chúng ta ghép một nút mới vào cây ở bất kỳ vị trí nào. Mã cho

def BinaryTree(r):
    return [r, [], []]

0 tương tự như

def BinaryTree(r):
    return [r, [], []]

1 và được hiển thị trong Liệt kê 2

Liệt kê 2

def insertRight(root,newBranch):
    t = root.pop(2)
    if len(t) > 1:
        root.insert(2,[newBranch,[],t])
    else:
        root.insert(2,[newBranch,[],[]])
    return root

Để hoàn thiện tập hợp các hàm tạo cây này (xem Liệt kê 3), chúng ta hãy viết một vài hàm truy cập để lấy và đặt giá trị gốc, cũng như lấy các cây con bên trái hoặc bên phải

Liệt kê 3

def getRootVal(root):
    return root[0]

def setRootVal(root,newVal):
    root[0] = newVal

def getLeftChild(root):
    return root[1]

def getRightChild(root):
    return root[2]

ActiveCode 2 thực hành các hàm cây mà chúng ta vừa viết. Bạn nên thử nó cho chính mình. Một trong những bài tập yêu cầu bạn vẽ cấu trúc cây từ tập hợp các cuộc gọi này

Tự kiểm tra

Q-3. Cho các tuyên bố sau

x = BinaryTree('a')
insertLeft(x,'b')
insertRight(x,'c')
insertRight(getRightChild(x),'d')
insertLeft(getRightChild(getRightChild(x)),'e')

Câu trả lời nào là đại diện chính xác của cây?

• ['A B C D', [], []]]]
• Không hẳn, cây này thiếu nút 'e'
• ['a', ['c', [], ['d', ['e', [], []], []]], ['b', [], []]]
• Điều này là gần, nhưng nếu bạn cẩn thận, bạn sẽ thấy rằng con trái và con phải của gốc được hoán đổi
• ['a', ['b', [], []], ['c', [], ['d', ['e', [], []], []]]]
• Rất tốt
• ['a', ['b', [], ['d', ['e', [], []], []]], ['c', [], []]]
• Điều này là gần, nhưng tên con bên trái và bên phải đã được hoán đổi cùng với các cấu trúc bên dưới

Viết một hàm

def BinaryTree(r):
    return [r, [], []]

2 trả về một cây bằng cách sử dụng danh sách các hàm danh sách giống như thế này

Làm cách nào để tạo BST từ mảng?

Làm cách nào để chuyển đổi danh sách thành cây nhị phân trong Python?

Làm cách nào để tạo cây tìm kiếm nhị phân từ danh sách các số trong Python?

Danh sách liên kết có phải là cây nhị phân không?