Giả sử, chúng ta được cung cấp các nút của cây n-ary trong một mảng. Chúng ta phải tìm và trả về nút gốc của cây bằng cách tái tạo lại nó. Cây đầy đủ phải được hiển thị từ nút trả về theo ký hiệu đặt hàng trước.
Vì vậy, nếu đầu vào giống như
thì đầu ra sẽ là
[14, 27, 32, 42, 56, 65]
Chúng tôi sẽ sử dụng gốc của cây để hiển thị trình tự trước của cây. Vì vậy, đầu ra là một đơn đặt hàng trước của cây.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
indgree:=một bản đồ mới chứa các giá trị số nguyên
-
đối với mỗi nút trong cây, hãy thực hiện
-
đối với mỗi con trong con trỏ con của nút, thực hiện
-
indgree [value of child]:=indgree [value of child] + 1
-
-
-
đối với mỗi nút trong cây, hãy thực hiện
-
nếu không xác định được [giá trị của nút] bằng 0, thì
-
nút trả lại
-
-
-
trả về null
Ví dụ (Python)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
import collections
class Node:
def __init__(self, value, child = None) -> None:
self.val = value
self.children = []
if child != None:
for value in child:
self.children.append(value)
def solve(tree):
indegree = collections.defaultdict(int)
for node in tree:
for child in node.children:
indegree[child.val] += 1
for node in tree:
if indegree[node.val] == 0:
return node
return None
def treeprint(node, tree):
if node == None:
tree.append("None")
return tree
if tree == None:
tree = []
tree.append(node.val)
for child in node.children:
treeprint(child, tree)
return tree
node6 = Node(65)
node5 = Node(56)
node4 = Node(42, [node5, node6])
node3 = Node(32)
node2 = Node(27)
node1 = Node(14, [node2, node3, node4])
tree = [node2, node1, node5, node3, node6, node4]
root = solve(tree)
print(treeprint(root, None)) Đầu vào
node6 = Node(65) node5 = Node(56) node4 = Node(42, [node5, node6]) node3 = Node(32) node2 = Node(27) node1 = Node(14, [node2, node3, node4]) tree = [node2, node1, node5, node3, node6, node4]
Đầu ra
[14, 27, 32, 42, 56, 65]