Question:
struct NODE {
NODE* pLeft;
NODE* pRight;
char chValue;
};
e.g.
preorder traversal : a b d c e f
inorder traversal : d b a e c f
Answer:
#include <iostream>
using namespace std;
struct NODE {
NODE* pLeft;
NODE* pRight;
char chValue;
};
void PrintPreOrder(NODE* pRoot) {
if (!pRoot)
return;
cout << pRoot->chValue;
PrintPreOrder(pRoot->pLeft);
PrintPreOrder(pRoot->pRight);
}
void PrintInOrder(NODE* pRoot) {
if (!pRoot)
return;
PrintInOrder(pRoot->pLeft);
cout << pRoot->chValue;
PrintInOrder(pRoot->pRight);
}
void Rebuild(char* pPreOrder, char* pInOrder, int nTreeLen, NODE** pRoot) {
if (pPreOrder == 0 || pInOrder == 0)
return;
NODE* pTemp = new NODE;
pTemp->pLeft = 0;
pTemp->pRight = 0;
pTemp->chValue = *pPreOrder;
if (*pRoot == 0)
*pRoot = pTemp;
if (nTreeLen == 1)
return;
char* pOrgInOrder = pInOrder;
char* pLeftEnd = pInOrder;
int nTempLen = 0;
while (*pPreOrder != *pLeftEnd) {
nTempLen++;
if (nTempLen > nTreeLen)
break;
pLeftEnd++;
}
int nLeftLen = (int)(pLeftEnd - pOrgInOrder);
int nRightLen = nTreeLen - nLeftLen - 1;
if (nLeftLen > 0)
Rebuild(pPreOrder+1, pInOrder, nLeftLen, &(pTemp->pLeft));
if (nRightLen > 0)
Rebuild(pPreOrder+nLeftLen+1, pInOrder + nLeftLen + 1, nRightLen, &(pTemp->pRight));
}
int main() {
char* pPreOrder = "abdcef";
char* pInOrder = "dbaecf";
NODE* pRoot = 0;
int nTreeLen = 6;
Rebuild(pPreOrder, pInOrder, nTreeLen, &pRoot);
PrintPreOrder(pRoot);
cout << endl;
PrintInOrder(pRoot);
cout << endl;
return 0;
}