python - 使用一个输入参数在python中序列化一棵二叉树

Question

我有以下用于序列化和反序列化二叉树的代码

这是一个简化版的互动练习。

我只想使用原始的 python 结构无需额外的 pkg 加载和递归。

非常感谢任何指向站点的指针。

我不确定这个网站是否一直要求提供更多详细信息。

def serialize(Node):
    """ONLY_USE_PRIMITIVE_PYTHON_CONSTRUCT_AND_RECURSION"""
    return str

def deserialize(str):
    """ONLY_USE_PRIMITIVE_PYTHON_CONSTRUCT_AND_RECURSION"""
    return Node


class Node:
    def __init__(self,data):
        self.left = None
        self.right = None
        self.data = data
    #def printTree(self):
    #    print(self.data)
    def insert(self,data):
        if self.data:
            if self.data > data :
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif self.data < data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data
    def printTree(self):
        if self.left:
            self.left.printTree()
        if self.right:
            self.right.printTree()
        print(self.data)

def serialize(Node, serial):
    if Node != None:
        serial.append(Node.data)
        serialize(Node.left, serial)
        serialize(Node.right, serial)
    else:
        serial.append('x')

def deserialize(serial):
    root = Node(None)
    ptr=0
    data_len=len(serial)

    if(data_len>0 and serial[ptr]!='x'):
        root.insert(serial[ptr])
        ptr=ptr+1
    elif (data_len==0 or serial[ptr]=='x'):
        return root


    while(ptr<data_len):
        if(serial[ptr]=='x'):
            ptr=ptr+1
        else:
            root.insert(serial[ptr])
            ptr=ptr+1

    return root

Answer 1

我假设data 是整数值。即使情况并非如此，调整下面的代码也不会那么困难。

序列化的方式当然有很多种。如果您需要避免 deserialize 函数的第二个参数，那么如果您知道右 child 的数据在串行字符串中的哪个偏移量开始，将会很有帮助。

所以这里有一个建议:

def serialize(node):
    if node is None:
        return ""
    left = serialize(node.left)
    right = serialize(node.right)
    return str(node.data) + ":" + str(len(left)) + ":" + left + right

def deserialize(serial):
    if serial == "":
        return None
    data, leftsize, content = serial.split(":", 2)
    node = Node(int(data))
    node.left = deserialize(content[0:int(leftsize)])
    node.right = deserialize(content[int(leftsize):])
    return node