x*********s
发帖数: 2604 | 1 how to serialize and deserialize a n ary tree? | g*****x
发帖数: 799 | 2 如果是binary的话inorder+preorder或inorder+postorder
n-nary存(node, parent) pair貌似可以，不知道有什么更好的方法 | P********l
发帖数: 452 | | p******r
发帖数: 2999 | 4 序列化成前序和中序
【在 x*********s 的大作中提到】
: how to serialize and deserialize a n ary tree?
| g*****x
发帖数: 799 | | s*********l
发帖数: 103 | 6
注意二叉树不同节点内容可能有重复，比如
inorder: [1,1,1,1,1,1,1]
preorder: [1,1,1,1,1,1,1]
【在 g*****x 的大作中提到】
: 如果是binary的话inorder+preorder或inorder+postorder
: n-nary存(node, parent) pair貌似可以，不知道有什么更好的方法
| j********x
发帖数: 2330 | 7 Do a pre-order traversal, after the traversing of a subtree, record the size
of the subtree with that node. Got some thing like this:
serialized_node,size_of_the_sub_tree_rooted_at_this_node,node,size
A recursive deserialization process is easy to get.
As for two traversal, I dont get it. Meaning to store two arrays of node
keys? But a serious problem is that we need to traverse twice of the tree.
Not good. | P********l
发帖数: 452 | 8
size
More explanation on the "serialized_node"? Seems you saved redundant info.
No. Only one traversal can obtain both arrays.
The problem of the method is in deserialization. One traversal needs to look
up ids in another one to recover the tree.
I don't think the two traversal method is practical for serialization.
【在 j********x 的大作中提到】
: Do a pre-order traversal, after the traversing of a subtree, record the size
: of the subtree with that node. Got some thing like this:
: serialized_node,size_of_the_sub_tree_rooted_at_this_node,node,size
: A recursive deserialization process is easy to get.
: As for two traversal, I dont get it. Meaning to store two arrays of node
: keys? But a serious problem is that we need to traverse twice of the tree.
: Not good.
|
|
