編碼的二進制樹結構JSON格式

Question

我有一個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 

Answer 1

- 編輯 -

你想在每個節點持有什麼樣的價值？如果它只是一個int作爲您的例子表明，它應該是很容易的：

一個節點有一個id，一個或更多的孩子，和值： { 「1」：{「孩子」：」 2「：」值「：1111}， 」2「：{」children「：[」3「，」4「]，」value「：2222}， 」3「：{」children「 「值」：3333}， 「4」：{「孩子」：空，「值」：4444}}

Answer 2

什麼你需要做的是讓你的類序列化爲字典的數據結構和字符串。我沒有找到任何這樣做的一般方法，所以我通常做的是讓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 

Answer 3

如果您熟悉堆棧，您可以看到下面的代碼。

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