I'm working on a project that needs to read preorder and inorder traversals, and print out the three orders (pre, in, post)

My tree is not correct at all, appreciate anyone who can help me on this. This tree is not a binary search one, so no need to compare the value.

My algorithm: preorder[0] is the root

preorder[1] is the root of the subtree

always get the nextkey from preorder

compare the indexes found in inorder.

for instance, if current index is less the previous

keyindex, it's in the left subtree

//instance: inorderArray

6 15 9 4 13 11

| | |

left root right

//instance: preorderArray

4 6 9 15 11 13

37 is inorderArray[2], it must be inserted right under 29 (inorderArray[1])

I don't know how to make T2 and T3 work correctly in this code. I need help!

//preArray: elements in preorder

//inArray: elements in inorder

//size: number of elements

void createTree(treeNode* &Rt, int preArray[], int inArray[], int size)

{

treeNode *T1, *T2, *T3; //T1 is new node to be inserted

//T2, T3 used to find the postion and linking nodes

int k; //loop counter

int rootIndex;

int keyIndex;

int keyIndexArray[size];

rootIndex = findRoot(inArray, size, preArray[0]);

//keyIndex = findRoot(inArray, size, preArray[0]);

keyIndexArray[0] = rootIndex;

cout << "keyIndexArray[0]: " << keyIndexArray[0] << endl;

//create root

Rt = new treeNode;

Rt->data = preArray[0];

cout << "Rt is: " << Rt->data << endl;

Rt->lchild_ = NULL;

Rt->rchild_ = NULL;

T2 = Rt;

T3 = Rt;

//traverse the preorderArray, and insert

for ( k = 1; k < size; k++)

{

keyIndex = findRoot(inArray, size, preArray[k]);

keyIndexArray[k] = keyIndex;

cout << "keyIndexArray[" << k <<"]: " << keyIndexArray[k] << endl;

cout << "keyIndex is: " << keyIndex << endl;

T1 = new treeNode;

T1->data = preArray[k];

cout << "the next key is: " << T1->data << endl;

T1->lchild_ = NULL;

T1->rchild_ = NULL;

while (T2 != NULL) //T2 is used to find the correct positon

{

T3 = T2;

if (keyIndexArray[k] < keyIndexArray[k-1])

T2 = T2->lchild_;

else

T2 = T2->rchild_;

}

//T3 is used for linking the nodes together, I don't know how

to fix this part. The condition for if is not correct. I can't think of

the way to set it right.

if (keyIndexArray[k] < keyIndexArray[k-1] && keyIndexArray[k] < rootIndex)

T3->lchild_ = T1;

else

T3->rchild_ = T1;

T2 = Rt;

}

}

//

//

void traverse(treeNode *p)

{

if ( p != NULL )

{

traverse(p->lchild_);

cout << p->data << " ";

traverse(p->rchild_);

}

}

Thanks for reading and help.