Suppose we have two array inorder and preorder containing the elements in the said format.
Using these two arrays how can i generate the binary tree??
Any help on the algorithm to be followed will be highly appreciated.
For eg:
inorder is : 2 3 4 5 6 7 8
preorder is : 5 3 2 4 7 6 8
then the Binary tree shld be
________5
________/\
_______3_7
_______/\_/\
______2_4 6_8
How can i form this binary tree??
i know the algorithm by hand but how do i implement it in C??
> i know the algorithm by hand but how do i implement it in C??
That's basically all programming is.
If you know how to do something on paper (the hard part), writing the code for that is pretty easy.
Post your idea and your attempt at the code.
Just a hint since I see a lot of code in here that is huge for what it is trying to do:
Build the tree recursively using the pre-order array(The in order array will cause you to have an unbalanced tree). The function to do this is 5 lines or less.
You already have an example.. try to use that to work out an algorithm
For eg:
inorder is : 2 3 4 5 6 7 8
preorder is : 5 3 2 4 7 6 8
then the Binary tree shld be
________5
________/\
_______3_7
_______/\_/\
______2_4 6_8
Hint: 5 is the root of the tree ..
5 is the first element in the pre-order array.
5 is somewhere in the middle of the in-order array .. so the elements to the left of 5 are a part of the left subtree and the elements to the right of 5 are a part of the right subtree.
resrsdghertgfsgt
hi... i have given u an code that generates a tree from a given inorder and preorder array...
#define NULL 0
typedef struct btree
{
int data;
struct btree *left;
struct btree *right;
}node;
node *root;
void create(int,int []);
void inorder(node *),preorder(node *);
void main()
{
int i=0,p[30],in[30];
node *list;
clrscr();
printf("enter the preorder\n");
while(1) //getting array for preorder elements
{
scanf("%d",&p[i]);
i++;
if(p[i-1]==-99)
break;
}
printf("enter the inorder\n");
i=0;
while(1) //getting array for inorder elements
{
scanf("%d",&in[i]);
i++;
if(in[i-1]==-99)
break;
}
printf("\nthe given inorder is\n");
for(i=0;in[i]!=-99;i++)
printf("%5d",in[i]);
printf("\nthe giver preorder is\n");
for(i=0;p[i]!=-99;i++)
printf("%5d",p[i]);
root=(node*)malloc(sizeof(node));
root->data=p[0]; //by default first elemnt of tree is p[0]
root->right=root->left=NULL;
for(i=1;p[i]!=-99;i++)
create(p[i],in);//creating tree for each element of preorder using inorder array
printf("\n\n\nINORDER TRAVERSAL OF THE TREE\n");
inorder(root);
printf("\n\n\nPREORDER TRAVERSAL OF THE TREE\n");
preorder(root);
getch();
}
void create(int key,int a[])
{
node *i=root,*j;
while(1)
{
if(find(i->data,a,key))//finding the position of p[i](here key)to be inserted in tree
{
if(i->left==NULL)
{
i->left=(node*)malloc(sizeof(node));
i=i->left;
i->data=key;
i->left=i->right=NULL;
break;
}
else
i=i->left;
}
else
{
if(i->right==NULL)
{
i->right=(node*)malloc(sizeof(node));
i=i->right;
i->data=key;
i->left=i->right=NULL;
break;
}
else
i=i->right;
}
}
}
int find(int t,int a[],int key)
{
int i,j;
for(i=0;a[i]!=-99;i++)
if(a[i]==t)
break;
for(j=0;j<i;j++)
if(a[j]==key)
return 1;
return 0;
}
void inorder(node *root)
{
if(root!=NULL)
{
inorder(root->left);
printf("%6d",root->data);
inorder(root->right);
}
}
void preorder(node *root)
{
if(root!=NULL)
{
printf("%6d",root->data);
preorder(root->left);
preorder(root->right);
}
}try ur problem wit this solution.
Tell me whether it is useful for U :-)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
struct Tree
{
char chr;
Tree *left, *right;
};
queue<Tree *> q;
char PreOrder[500];
char InOrder[500];
bool flag[500];
int Pid;
int PLen, ILen;
Tree *ReBuild(int a, int b)
{
int id;
int k;
Tree *node;
Pid ++;
node = new Tree;
node->chr = PreOrder[Pid];
for (int i = a; i <= b; i ++) //对于前序遍历序列的元素，在中序遍历序列中寻找它的位置
if (InOrder[i] == PreOrder[Pid])
id = i;
flag[id] = true;
for (k = id - 1; k >= a; k --) //构造该根的左子树
if (flag[k] == true)
break;
if (k == id - 1) //注意边界地方的讨论
node->left = NULL;
else if (k == a - 1)
node->left = ReBuild(a, id - 1);
else
node->left = ReBuild(k, id - 1);
for (k = id + 1; k <= b; k ++) //构造该根的右子树
if (flag[k] == true)
break;
if (k == id + 1) //注意边界地方的讨论
node->right = NULL;
else if (k == b + 1)
node->right = ReBuild(id + 1, b);
else
node->right = ReBuild(id + 1, k);
return node;
}
void visit()
{
Tree *temp;
while (!q.empty())
{
temp = q.front();
printf("%c", temp->chr);
if (temp->left != NULL)
q.push(temp->left);
if (temp->right != NULL)
q.push(temp->right);
q.pop();
}
printf("\n");
}
void destroy(Tree *node)
{
if (node == NULL)
return ;
if (node->left)
destroy(node->left);
if (node->right)
destroy(node->right);
delete node;
}
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
int T;
Tree *root;
scanf("%d", &T);
while (T --)
{
memset(flag, false, sizeof(flag));
scanf("%s%s", PreOrder, InOrder);
Pid = -1;
root = ReBuild(0, strlen(InOrder) - 1);
q.push(root);
visit(); //广度优先遍历
destroy(root);
}
return 0;
}Hey thanks for providing code. . .
I'll check it and will get back to you soon.
here i have another code without recursion:
template <typename Comparable>
struct BinaryNode
{
Comparable element;
BinaryNode *left;
BinaryNode *right;
BinaryNode(){
left = right = NULL;
}
BinaryNode( const Comparable & theElement, BinaryNode *lt, BinaryNode *rt )
: element( theElement ), left( lt ), right( rt ) { }
};
void binTree( BinaryNode<char>*&root, string s, string t)
//Build a binary tree root so that its preorder traversal is s and its inorder traversal is t.
//scan preorder from left to right using inorder to seperate left and right subtrees.
{
root = new BinaryNode<char>(s[0],NULL,NULL);
/*int p[s.length()];
for(int i = 0 ; i < s.length();i++)
for(int j = 0 ; j < t.length(); j++)
if(s[i] == t[j])
p[i] = j;*/
BinaryNode<char>* parent;
BinaryNode<char>* current;
for(unsigned int i = 1; i < s.length(); i++)
{
current = root;
BinaryNode<char>* target = new BinaryNode<char>(s[i],NULL,NULL);
while(current){
if(t.find(target->element) < t.find(current->element) )
{
parent = current;
current = current->left;
}
else if(t.find(target->element) > t.find(current->element)){
parent = current;
current = current->right;
}
else;
}
if(t.find(target->element) < t.find(parent->element))
parent->left = target;
else
parent->right = target;
}
}
template<typename Comparable>
void levelTraversal(BinaryNode<Comparable>* sub_root,void(*visit)(Comparable & x)){
queue<BinaryNode<Comparable>*> q ;
//must justify sub_root is not empty, otherwise there's an exception
if(sub_root != NULL){
q.push(sub_root);
while(!q.empty()){
if(q.front()->left != NULL)
q.push(q.front()->left);
if(q.front()->right != NULL)
q.push(q.front()->right);
(*visit)(q.front()->element);
q.pop();
}
}
}
template<typename Comparable>
void printTree( BinaryNode<Comparable> *t )
{
if( t != NULL )
{
printTree( t->left);
cout << t->element << endl;
printTree( t->right);
}
}
template<typename T>
void print(T & x){
cout << x << " ";
}
int main(){
string pre = "gdhbeiafjc";
string in = "abdgheicfj";
BinaryNode<char>* root = new BinaryNode<char>();
binTree(root,pre,in);
printTree(root);
levelTraversal(root,print<char>);
}i think this one is much more understandable and it is my original implementation. string_name.find(char) returns the int postion of the char which simplify the code a lot..
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.