struct Node{
Node * left, right;
int data;
}
… If you simply output as “data,leftId,rightId | data,leftId,rightId | …” then the graph structure i.e. link is lost. Therefore, I feel the stream need to identify each node: “Id,data,leftId,rightId|…”
Next question is how to assign the id values. Easiest — use node address as a string id!
Suppose there’s a treewalk algo walk(Node * root, void ( *callback ) (Node *)), i will call it like
walk(root, serialize1node); // where serialize1node is the callback.
Note the position of the asterisk:
- It’s on the right of type name Type1 — read left to right .. pointer to Type1
- It’s on the left of variable name var2 — read left to right .. var2 is a pointer to …
https://github.com/tiger40490/repo1/blob/cpp1/cpp/binTree/serialize_bbg.cpp is my tested solution
—-idea from my friend Deepak: pre-order tree walk and output one line per node {payload, direction from root, direction from Level 1 ancestor, direction from Level 2 ancestor..}
- first node in the file is always the root
- the output file always includes the higher level nodes before the lower-level nodes
- delimiter needed between nodes
—-If the tree is a BSTree, then this idea is based on the fact that a reading a series of unsorted nodes can construct a BSTree. For this solution, we have no requirement on the payload values. They can be booleans.
first pass — in-order walk to build a hash table of {node address -> integer id}. If we treat the Id’s as payload, then the tree is a BST.
2nd pass — BFT the original tree. For each node, we write original payload, id to the file, without writing the links or addresses. File looks like T,5|T,4|T,6|T,2|…
When we reconstruct the tree, we read each node from the file, and insert that node into our new tree, using the id value to decide where.
