Python - Chuyển danh sách lồng nhau thành từ điển dạng cây

Cho một danh sách lồng nhau, cần chuyển đổi thành từ điển (dictionary) mà các phần tử có thể coi như cấu trúc dữ liệu cây. Bài viết giới thiệu hai cách chuyển danh sách lồng nhau thành từ điển dạng cây.

Sử dụng Slicing

Đảo ngược các mục trong danh sách con bằng slicing, kiểm tra nếu khóa chưa có trong cây thì thêm vào.

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

# Danh sách cho trước
listA = [['X'], ['Y', 'X'], ['Z', 'X'], ['P', 'Z', 'X']]
print(CreateTree(listA))

Kết quả:

Đầu ra

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

Sử dụng reduce và getitem

Dùng functools.reduce và operator.getitem để truy xuất và thiết lập nút trong cây. Cũng dùng slicing đảo ngược thứ tự.

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()

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

Kết quả:

Đầu ra

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