Original Post
I am suppose to create a binary tree from two char arrays that are in a text file. The text file contains an int at the beginning which indicates the number of chars in each array followed by the arrays which are in prefix and infix notation respectively. I am then suppose to construct the tree, output the postfix notation of the tree and the height of the tree. My program seems to be omitting the last two chars in the array and I don''t know what is causing this. Could somebody please take a look and tell me what im doing wrong, thanks.
Data File:
9
a b e c d g f i h
e b d c a f i g h
Code:
#include <iostream>
using namespace std;
struct node
{
char data;
node *leftChild, *rightChild;
};
node *treeFromPreandIn(char a[], int L1, int R1, char b[], int L2, int R2);
void postOrder(node *t);
int height(node *t);
int max(int num1, int num2);
int main()
{
node *postRoot;
int size, high;
cin>>size;
char pre[size+2], in[size+2];
for(int i = 1; i <= size; i++)
{
cin>>pre;
}
for(int i = 1; i <= size; i++)
{
cin>>in[i];
}
postRoot = treeFromPreandIn(pre, 1, size + 2, in, 1, size + 2);
high = height(postRoot);
cout<<"Post: ";
postOrder(postRoot);
cout< R1 + 1)
return NULL;
else
{
node *t1;
t1 = new node;
t1->data = a[L1];
t1->leftChild = NULL;
t1->rightChild = NULL;
for(int i = 1; i <= R1; i++)
{
if(b[i] == a[L1])
{
pos = i;
break;
}
}
t1->leftChild = treeFromPreandIn(a, L1 + 1, pos, b, L2, pos - 1);
t1->rightChild = treeFromPreandIn(a, L1 + pos, R1, b, pos + 1, R2);
return t1;
}
}
void postOrder(node *t)
{
if(t != NULL)
{
postOrder(t->leftChild);
postOrder(t->rightChild);
cout<data<<" ";
}
}
int height(node *t)
{
if(t == NULL)
return 0;
else
{
int L1 = height(t->leftChild);
int R1 = height(t->rightChild);
return (1 + max(L1, R1));
}
}
int max(int num1, int num2)
{
if(num1 > num2)
return num1;
else
return num2;
}