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

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

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
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +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.

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    So, for binary tree as children are fixed (2), so insertion of NULL helps us to construct tree, which is not so in other case. Please say yes if its correct.

    BTW if there is n-ary tree with n children (0 for leaves), same procedure of serialise and deserialise work (just preorder with NULL)?

    → Ответить