Tôi đang cố gắng tạo một cây dựa trên đầu vào nhất định. Ở đó sẽ có gốc, bao gồm các nút con và các nút con con. Tôi có thể triển khai một cây nơi tôi có thể thêm các nút con vào một nút chính cụ thể (tôi đã biết gốc). Tuy nhiên, tôi đang cố gắng tìm ra cách được khuyến nghị để triển khai cây trong đó trước tiên chúng ta phải tìm nút gốc từ tập hợp đầu vào đã cho. Ví dụ:
Có n dòng,
Giá trị trong mỗi dòng đại diện cho nút chính của số dòng đó.
4 ( n = 4, n dòng tiếp theo)
1 ( 1 là nút chính của 1, ở đây số dòng là 1)
1 (1 là nút chính của 2, số dòng ở đây là 2)
2 (2 là nút chính của 3, số dòng ở đây là 3)
1 (1 là nút chính gồm 4, số dòng ở đây là 4)
Vì vậy, cái cây sẽ trông như thế nào,
1
/ |
hai mươi bốn
|
3
Ở đây, chúng ta có thể thấy nút gốc là 1. Nhưng chúng ta không thể đoán được nút gốc cho đến khi biết tất cả các giá trị đầu vào. Trước khi triển khai cây, trước tiên tôi có nên tìm ra nút gốc từ đầu vào không? Hoặc có cách nào khác?
Đoạn mã sau thêm một nút vào cây:
nút lớp:
# Hàm tiện ích tạo nút cây mới
def __init__(self,key):
self.key = key
self.child = []
def printNodeLevelWise(root):
nếu root là Không có:
trở lại
xếp hàng = []
queue.append(root)
while(len(hàng đợi) >0):
n = len(hàng đợi)
trong khi(n > 0):
# Loại bỏ một mục khỏi hàng đợi và in nó
p = hàng đợi[0]
hàng đợi.pop(0)
in(p.key,)
# Xếp hàng tất cả các phần tử con của mục bị loại bỏ
đối với chỉ mục, giá trị trong liệt kê (p.child):
hàng đợi.append(giá trị)
n -= 1
in("")
gốc = Nút (1)
root.child.append(Node(2))
root.child.append(Node(4))
root.child[0].child.append(Node(3))
printNodeLevelWise(root)
Đoạn mã trên sẽ triển khai cây này:
1
/ |
hai mươi bốn
|
3
Nhưng cách được đề xuất để đạt được điều tương tự từ đầu vào đã cho là gì?
Giả định:
- "master" có nghĩa là "cha mẹ" và
- Khi một dòng có một tham chiếu tự - như vậy Tôi xuất hiện trong danh sách chính Tôi dòng - đó là gốc
...sau đó bạn có thể tiến hành như thế này:
nút = {} # từ điển của tất cả các nút được khóa theo giá trị của chúng
gốc=Không có
n = int(input()) # lấy số lượng nút
cho vải lanh trong phạm vi (1, n+1):
parentnum = int(input()) # lấy "master" cho dòng này
# tạo các nút liên quan chưa tồn tại:
nếu không phải là linenum trong các nút:
nút[linenum] = Nút(linenum)
nếu không phải là cha mẹ trong các nút:
nút[parentnum] = Nút(parentnum)
if parentnum == linenum: # a tự tham chiếu chỉ ra gốc
gốc = nút [parentnum]
else: # thiết lập mối quan hệ cha-con
nút[parentnum].child.append(nodes[linenum])
Tôi là một lập trình viên xuất sắc, rất giỏi!