CODEWITHSUNDEEP
pythondata-structuresencodingbinary-tree
georgehu
georgehu

Reputation: 190

Encoding a binary tree structure to json format

I have a python binary tree class like this:

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

and I have tree traversal function like this:

  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

now I'm getting stuck in generating a data format like the below nested structure:

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

the tree structure is:

1

|

2

(left)3 (right)4

Upvotes: 0

Views: 4078

Answers (3)

Gapton
Gapton

Reputation: 2134

what value do you want to hold in each node? if it is just an int as your example showed, it should be easy enough:

a node has an id, one or more children, and a value:

{
"1" : { "children" : ["2"] ,     "value" : 1111 },
"2" : { "children" : ["3","4"] , "value" : 2222 },
"3" : { "children" : null ,      "value" : 3333 },
"4" : { "children" : null ,      "value" : 4444 }
}

Upvotes: 2

ZSFS
ZSFS

Reputation: 81

If you are familiar with stack, you can see code below.

"""
@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

Upvotes: 0

Ron Reiter
Ron Reiter

Reputation: 3934

What you'll need to do is to make your class serializable into a data structure of dictionaries and strings. I didn't find any general way of doing this, so what I usually do is make the BinaryTree implement some sort of or "flattening" and "parsing" function. A good way of doing this is this:

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

Upvotes: 4

Related Questions