Кодирование бинарной древовидной структуры в формат json - PullRequest
Новая
       32

Кодирование бинарной древовидной структуры в формат json

0 голосов
/ 22 сентября 2011

У меня есть класс бинарного дерева Python: 

class BinaryTree:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

    def __unicode__(self):
        return '%s' % self.data

и у меня есть функция обхода дерева, подобная этой: 

  def tree_traversal(tree):
        if tree:
            for node_data in tree_traversal(tree.left):
                yield node_data
            for node_data in tree_traversal(tree.right):
                yield node_data

теперь я застреваю в создании формата данных, подобного вложенной структуре ниже: 

{'id':1,children:[{'id':2, children:[{'id':3, 'id':4}]}]}

древовидная структура: 

1

|

2

(left)3 (right)4

Ответы [ 3 ]

4 голосов
/ 22 сентября 2011

Вам нужно сделать сериализуемый класс в структуре данных словарей и строк. Я не нашел никакого общего способа сделать это, поэтому я обычно делаю так, чтобы BinaryTree реализовывал какую-то функцию «выравнивания» и «разбора». Хороший способ сделать это так: 

import json

class BinaryTree:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

    def flatten(self):
        return {
            "data" : self.data, 
            "left" : self.left.flatten() if self.left else None,
            "right" : self.right.flatten() if self.right else None,
        }

    @classmethod
    def from_dictionary(cls, d):
        obj = cls(d["data"])

        if d.has_key("left") and d["left"] is not None:
            obj.left = cls.from_dictionary(d["left"])

        if d.has_key("right") and d["right"] is not None:
            obj.right = cls.from_dictionary(d["right"])

        return obj

if __name__ == "__main__":
    binary_tree = BinaryTree.from_dictionary({"data": "hello", "left": {"data" :  "yo"}})
    json_data = json.dumps(binary_tree.flatten())
    print "JSON: %s" % json_data
    binary_tree_from_json = BinaryTree.from_dictionary(json.loads(json_data))

    print binary_tree_from_json.data
    print binary_tree_from_json.left.data
2 голосов
/ 22 сентября 2011

- отредактировано -

какое значение вы хотите сохранить в каждом узле?если это просто int, как показывает ваш пример, это должно быть достаточно просто:

узел имеет идентификатор, одного или нескольких дочерних элементов и значение: {"1": {"children": ["2 "]," value ": 1111}," 2 ": {" children ": [" 3 "," 4 "]," value ": 2222}," 3 ": {" children ": null," value": 3333}," 4 ": {" children ": null," value ": 4444}}

0 голосов
/ 26 июня 2017

Если вы знакомы со стеком, вы можете увидеть код ниже. 

"""
@param root: The root of binary tree.
@return: Preorder in list which contains node values.
"""
def preorderTraversal(self, root):
    if root is None:
        return []
    stack = [root]
    preorder = []
    while stack:
        node = stack.pop()
        preorder.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return preorder
...