I have a preorder traversal of a binary tree that is stored in an array and I would like to recreate the binary tree based on this traversal. My array looks like this: {NNNLLNLLNLNLNNLLNLL}, where N represents a node and L represents a leaf. I would like to do this recursively but I am having trouble coming up with an algorithm. Any suggestions would be very appreciated.
2
-
An importannt question: Why do you need it stored in a binary tree in that specific order? What kind of data is it?Lloyd Crawley– Lloyd Crawley2013-10-28 02:09:02 +00:00Commented Oct 28, 2013 at 2:09
-
It's for a huffman encoding tree.Kalmar– Kalmar2013-10-28 02:28:52 +00:00Commented Oct 28, 2013 at 2:28
Add a comment
|
2 Answers
This should work assuming every node has 2 or 0 descendants (a tree that satisfies this property is called full or strict binary tree)
void create_from_traversal(Node* root, int& index) {
if (traversal[index] == 'L') {
root->left = root->right = NULL;
return;
}
root->left = new Node();
create_from_traversal(root->left, ++index);
root->right = new Node();
create_from_traversal(root->right, ++index);
}
Complete example with check:
#include <string>
#include <iostream>
class Node {
public:
Node* left;
Node* right;
};
std::string traversal = "NNNLLNLLNLNLNNLLNLL";
void create_from_traversal(Node* root, int& index) {
if (traversal[index] == 'L') {
root->left = root->right = NULL;
return;
}
root->left = new Node();
create_from_traversal(root->left, ++index);
root->right = new Node();
create_from_traversal(root->right, ++index);
}
void print_traversal(Node* root) {
if (root->left == NULL) {
std::cout << "L";
return;
}
std::cout << "N";
print_traversal(root->left);
print_traversal(root->right);
}
int main() {
Node* root = new Node();
int index = 0;
create_from_traversal(root, index);
// Does it work?
print_traversal(root); // Output should be equal to given traversal
std::cout << std::endl;
}
Output:
NNNLLNLLNLNLNNLLNLL
1 Comment
Joe Z
This code passes the example I gave below of a right-weighted tree,
NLNNNLLLL.You need one more traversal before you can reconstruct the tree. Given any two traversals among the three (Pre, Post, In) you can reconstruct. But given only one it is not possible to uniquely reconstruct the tree.
2 Comments
LeartS
You are right, unless it's a strict binary tree, in that case it's possible to reconstruct the (unique) tree with the algorithm I provided.
rajaditya_m
Absolutely. +1'd your answer :)
