Want to save the binary tree to the disk for the game "20 questions"

Question

In short, I would like to explore / develop an elegant method for saving a binary tree to disk (shared tree, not necessarily BST). Here is a description of my problem:

I am implementing the "20 questions" game. I wrote a binary tree whose internal nodes are questions and the leaves are answers. The left child of a node is the path you will follow if someone answered yes to your current question and the correct child does not. Please note that this is not a binary search tree, but simply a binary tree, whose left child is yes and no to its right.

The program adds node to the tree if it encounters a leaf that is null, asking the user to distinguish its answer from the one the computer was thinking about.

This is neat because the tree creates itself when the user plays. What is wrong is that I have no good way to save the tree to disk.

I was thinking about saving the tree as an array representation (for node i, the left child has 2i + 1 and 2i + 2 on the right, (i-1) / 2 for the parent), but it does not clear and I get a lot of lost space.

Any ideas for an elegant solution to save a sparse binary tree to disk?

Answer 1

You can save it recursively:

void encodeState(OutputStream out,Node n) { if(n==null) { out.write("[null]"); } else { out.write("{"); out.write(n.nodeDetails()); encodeState(out, n.yesNode()); encodeState(out, n.noNode()); out.write("}"); } } 

Create your own texty output format. I am sure that I do not need to describe a method for reading the result.

This is a bypass of the depth. It works too first.

Answer 2

I would do a level traversal. That is, you basically run the algorithm for the width search algorithm at the beginning.

You have:

• Create a qeueue with the root element inserted into it
• Remove the item from the queue, name it E
• Add left and right E children to the queue. If there are no left or right, just put a null representation of the node.
• write node E to disk.
• Repeat step 2.

Ordering sequence: F, B, G, A, D, I, C, E, H

What you will store on disk: F, B, G, A, D, NullNode, I, NullNode, NullNode, C, E, H, NullNode

Downloading back from disk is even easier. Just read the nodes you saved on disk from left to right. This will give you each level of the left and right nodes. That is, the tree will be filled from top to bottom from left to right.

Step 1:

 F 

Step 2:

  FB 

Step 3:

  FBG 

Step 4:

  FBG A 

And so on...

Note. After presenting the NULL node, you will no longer need to list your children on disk. When loading back, you will learn to go to the next node. Therefore, for very deep trees, this solution will still be effective.

Answer 3

An easy way to achieve this is to move the tree that displays each element as you do it. Then, to load the tree back, simply go to your list by inserting each item back into the tree. If your tree does not balance on its own, you can reorder the list so that the final tree is reasonably balanced.

Answer 4

Not sure if it's elegant, but simple and straightforward: Assign a unique identifier to each node, whether it's a stem or leaf. Simple integer counting.

When saving to disk, move the tree, saving each link identifier node, yes, link identifier no, and the text of the question or answer. For null references, use null as the null value. You can either add a flag to indicate whether there is a question or answer, or, more simply put, to check whether both links are null. You should get something like this:

 1,2,3,"Does it have wings?" 2,0,0,"a bird" 3,4,0,"Does it purr?" 4,0,0,"a cat" 

Note that if you use the sequential integer approach, storing the node identifier may be redundant, as shown here. You can simply put them in order by ID.

To recover from disk, read the line and then add it to the tree. You will probably need a table or array to store nodes with a direct link, for example. when processing node 1, you will need to track 2 and 3 until you can fill in these values.

Answer 5

I would save the tree as follows:

 <node identifier> node data [<yes child identfier> yes child] [<no child identifier> no child] <end of node identifier> 

where the child nodes are just recursive instances above. The bits in [] are optional, and the four identifiers are just constant / enum values.

Answer 6

The most arbitrary simple way is just the basic format that you can use to represent any chart.

 <parent>,<relation>,<child> 

Ie:

 "Is it Red", "yes", "does it have wings" "Is it Red", "no" , "does it swim" 

There is not much redundancy here, and the formats are mainly accessible to people, the only duplication of data is that for each direct child object there must be a copy of the parent.

The only thing you really need to observe is that you don't accidentally generate a loop;)

If that is not what you want.

The problem is rebuilding later. If I create a “does it have wings” object when reading the first line, I need to somehow find it when I later came across the reading line “does it have wings”, “yes”, “Does it have a beak?”

That's why I traditionally just use graph structures in memory for such a thing with pointers going all over the place.

 [0x1111111 "Is It Red" => [ 'yes' => 0xF752347 , 'no' => 0xFF6F664 ], 0xF752347 "does it have wings" => [ 'yes' => 0xFFFFFFF , 'no' => 0x2222222 ], 0xFF6F664 "does it swim" => [ 'yes' => "I Dont KNOW :( " , ... etc etc ] 

Then the child / parent relationship is just metadata.

Answer 7

In java, if you want to make a serializable class, you can simply write the class object to disk and read it using input / output streams.

Answer 8

Here is the C ++ code using PreOrder DFS:

 void SaveBinaryTreeToStream(TreeNode* root, ostringstream& oss) { if (!root) { oss << '#'; return; } oss << root->data; SaveBinaryTreeToStream(root->left, oss); SaveBinaryTreeToStream(root->right, oss); } TreeNode* LoadBinaryTreeFromStream(istringstream& iss) { if (iss.eof()) return NULL; char c; if ('#' == (c = iss.get())) return NULL; TreeNode* root = new TreeNode(c, NULL, NULL); root->left = LoadBinaryTreeFromStream(iss); root->right = LoadBinaryTreeFromStream(iss); return root; } 

In main() you can do:

 ostringstream oss; root = MakeCharTree(); PrintVTree(root); SaveBinaryTreeToStream(root, oss); ClearTree(root); cout << oss.str() << endl; istringstream iss(oss.str()); cout << iss.str() << endl; root = LoadBinaryTreeFromStream(iss); PrintVTree(root); ClearTree(root); /* Output: A BC DEF GHI ABD#G###CEH##I##F## ABD#G###CEH##I##F## A BC DEF GHI */ 

DFS is easier to understand.

 ********************************************************************************* 

But we can use BFS scan level using queue

 ostringstream SaveBinaryTreeToStream_BFS(TreeNode* root) { ostringstream oss; if (!root) return oss; queue<TreeNode*> q; q.push(root); while (!q.empty()) { TreeNode* tn = q.front(); q.pop(); if (tn) { q.push(tn->left); q.push(tn->right); oss << tn->data; } else { oss << '#'; } } return oss; } TreeNode* LoadBinaryTreeFromStream_BFS(istringstream& iss) { if (iss.eof()) return NULL; TreeNode* root = new TreeNode(iss.get(), NULL, NULL); queue<TreeNode*> q; q.push(root); // The parents from upper level while (!iss.eof() && !q.empty()) { TreeNode* tn = q.front(); q.pop(); char c = iss.get(); if ('#' == c) tn->left = NULL; else q.push(tn->left = new TreeNode(c, NULL, NULL)); c = iss.get(); if ('#' == c) tn->right = NULL; else q.push(tn->right = new TreeNode(c, NULL, NULL)); } return root; } 

In main() you can do:

 root = MakeCharTree(); PrintVTree(root); ostringstream oss = SaveBinaryTreeToStream_BFS(root); ClearTree(root); cout << oss.str() << endl; istringstream iss(oss.str()); cout << iss.str() << endl; root = LoadBinaryTreeFromStream_BFS(iss); PrintVTree(root); ClearTree(root); /* Output: A BC DEF GHI ABCD#EF#GHI######## ABCD#EF#GHI######## A BC DEF GHI */