已知前序和中序：
struct NODE
{
NODE *pLeft;
NODE *pRight;
char chValue;
};
int CharInStrFirstPos(char ch, char *str, int nLen)
{
char *pOrgStr = str;
while (nLen > 0 && ch != *str)
{
str++;
nLen--;
}
return (nLen > 0) ? (str - pOrgStr) : -1;
}
void ReBuild_PreIn(char *pPreOrder, char *pInOrder, int nTreeLen, NODE **pRoot)
{
if (pPreOrder == NULL || pInOrder == NULL)
{
return;
}
NODE *pTemp = new NODE;
pTemp->chValue = *pPreOrder;
pTemp->pLeft = NULL;
pTemp->pRight = NULL;
if (*pRoot == NULL)
{
*pRoot = pTemp;
}
if (nTreeLen == 1)
{
return;
}
int nLeftLen = CharInStrFirstPos(*pPreOrder, pInOrder, nTreeLen);
assert(nLeftLen != -1);
int nRightLen = nTreeLen - nLeftLen -1;
if (nLeftLen > 0)
{
ReBuild_PreIn(pPreOrder + 1, pInOrder, nLeftLen, &((*pRoot)->pLeft));
}
if (nRightLen > 0)
{
ReBuild_PreIn(pPreOrder + nLeftLen + 1, pInOrder + nLeftLen + 1,
nRightLen, &((*pRoot)->pRight));
}
}
已知后序和中序：
void ReBuild_AftIn(char *pAftOrder, char *pInOrder, int nTreeLen, NODE **pRoot)
{
if (pAftOrder == NULL || pInOrder == NULL)
{
return;
}
NODE *pTemp = new NODE;
pTemp->chValue = *pAftOrder;
pTemp->pLeft = NULL;
pTemp->pRight = NULL;
if (*pRoot == NULL)
{
*pRoot = pTemp;
}
if (nTreeLen == 1)
{
return;
}
int nLeftLen = CharInStrFirstPos(*pAftOrder, pInOrder, nTreeLen);
assert(nLeftLen != -1);
int nRightLen = nTreeLen - nLeftLen -1;
if (nLeftLen > 0)
{
ReBuild_AftIn(pAftOrder + nRightLen + 1, pInOrder, nLeftLen, &((*pRoot)->pLeft));
}
if (nRightLen > 0)
{
ReBuild_AftIn(pAftOrder + 1, pInOrder + nLeftLen + 1,
nRightLen, &((*pRoot)->pRight));
}
}
我上传了一个工VC的工程，有兴点此下载趣的朋友。代码参考于《编程之美》。