class node{
public:
int data;
node *left;
node right;
node(int d)
{
this->data = d;
this->left = NULL;
this->right = NULL;
}
};
node buildTree(int *inorder, int *preorder, int start, int end)
{
static int i = 0;
if (start > end)
{
return NULL;
}
node *root = new node(preorder[i]);
int index = -1;
for (int j = start; j <= end; j++)
{
if (inorder[j] == preorder[i])
{
index = j;
break;
}
}
i++;
root->left = buildTree(inorder, preorder, start, index - 1);
root->right = buildTree(inorder, preorder, index + 1, end);
return root;
}
void bfs(node root)
{
queue<node>q;
q.push(root);
q.push(NULL);
while (!q.empty())
{
node *f = q.front();
if (f == NULL)
{
cout << endl;
q.pop();
if (!q.empty())
{
q.push(NULL);
}
}
else
{
q.pop();
cout << f->data << " ";
if (f->left != NULL)
{
q.push(f->left);
}
if (f->right != NULL)
{
q.push(f->right);
}
}
}
return;
}
int main()
{
int preorder[] = { 3, 2, 8, 4, 1, 6, 7, 5 };
int inorder[] = { 1, 2, 3, 4, 8, 5, 6, 7 };
int n = sizeof(preorder) / sizeof(int);
node *root = buildTree(inorder, preorder, 0, n - 1);
bfs(root);
return 0;
}