Блог пользователя rahul_1234

Serialise and Deserialise
Автор rahul_1234, история, 9 лет назад, По-английски

For serialising and deserialising a binary tree( or a n-ary tree ) only preorder traversal with # for Null is used in the given Link but I think both inorder and preorder are required to construct tree.

Please tell me what is that I am missing?

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

In a regular tree, both preorder and postorder are required, because you don't know how many children each node has.

In a binary tree, you know that every node will have exactly two children (they can be null). After you read two children from input, you know you need to backtrack to your parent. If you read the deserialise code this should be clear — you recursively scan in the children, and return to the parent of a node if you finished scanning both children.

→ Ответить