Python - Chuyển đổi danh sách danh sách thành dict dạng cây

Với một danh sách lồng nhau, chúng tôi muốn chuyển đổi nó thành một từ điển có các phần tử có thể được coi là một phần của cấu trúc dữ liệu cây. Trong bài viết này, chúng ta sẽ thấy hai cách tiếp cận để chuyển đổi một danh sách lồng nhau thành để thêm từ điển có các phần tử đại diện cho một cây như cấu trúc dữ liệu.

Sử dụng Slicing

Chúng tôi đảo ngược các mục trong danh sách cắt aby và sau đó kiểm tra xem mục đó có trong danh sách hay không. Nếu nó không hiện diện, chúng tôi bỏ qua nó, nếu không chúng tôi thêm nó vào cây.

Ví dụ

def CreateTree(lst):
   new_tree = {}
   for list_item in lst:
      currTree = new_tree

      for key in list_item[::-1]:
         if key not in currTree:
            currTree[key] = {}
         currTree = currTree[key]
      return new_tree
# Given list
listA = [['X'], ['Y', 'X'], ['Z', 'X'], ['P', 'Z', 'X']]
print(CreateTree(listA))

Chạy đoạn mã trên cho chúng ta kết quả sau -

Đầu ra

{'X': {'Y': {}, 'Z': {'P': {}}}}

Sử dụng rút gọn và địa lý

Chúng tôi sử dụng functools và mô-đun toán tử để giảm bớt các chức năng và địa lý. Sử dụng các hàm này, chúng ta xác định hai hàm để lấy các mục từ danh sách và đặt các mục vào một cấu trúc cây. Ở đây, chúng tôi cũng sử dụng cách tiếp cận cắt để đảo ngược các phần tử của danh sách và sau đó áp dụng hai hàm đã tạo để tạo từ điển có các phần tử nằm trong cấu trúc cây.

Ví dụ

from functools import reduce
from operator import getitem

def getTree(tree, mappings):
   return reduce(getitem, mappings, tree)

def setTree(tree, mappings):
   getTree(tree, mappings[:-1])[mappings[-1]] = dict()

# Given list
lst = [['X'], ['Y', 'X'], ['Z', 'X'], ['P', 'Z', 'X']]
tree = {}
for i in lst:
   setTree(tree, i[::-1])
print(tree)

Chạy đoạn mã trên cho chúng ta kết quả sau -

Đầu ra

{'X': {'Y': {}, 'Z': {'P': {}}}}