登 录
已知前序遍历和中序遍历的结果,重建这棵二叉树
#include <iostream> #include <string> using namespace std; //------------------------------------------------------------------ // 前序遍历结果:a b d c e f // 中序遍历结果:d b a e c f //------------------------------------------------------------------ const int TREELEN = 6; struct NODE { NODE* pLeft; NODE* pRight; char chValue; }; void Rebuild(char* pPreOrder, char* pInOrder, int nTreeLen, NODE** pRoot) { //检查边界条件 if (pPreOrder==NULL || pInOrder==NULL) { return; } //获得前序遍历的第一个结点,即为ROOT NODE *pTemp = new NODE; pTemp->chValue = *pPreOrder; pTemp->pLeft = NULL; pTemp->pRight = NULL; //节点为空,把当前节点复制到根节点 if (nTreeLen == 1) { return; } //寻找子树长度 char* pOrgInOrder = pInOrder; char* pLeftEnd = pInOrder; int nTempLen = 0; //找到左子树结尾 while (*pPreOrder!=*pLeftEnd) { if (pPreOrder==NULL || pLeftEnd==NULL) { return; } nTempLen++; if (nTempLen > nTreeLen) { break; } pLeftEnd++; } //寻找左子树长度 int nLeftLen = 0; nLeftLen = (int)(pLeftEnd-pOrgInOrder); //寻找右子树长度 int nRightLen = 0; nRightLen = nTreeLen - nLeftLen - 1; //rebuild左子树 if (nLeftLen>0) { Rebuild(pPreOrder+1, pInOrder, nLeftLen, &((*pRoot)->pLeft)); } //rebuild右子树 if (nRightLen>0) { Rebuild(pPreOrder+nLeftLen+1, pInOrder+nLeftLen+1, nRightLen, &((*pRoot)->pRight)); } } int main() { char szPreOrder[TREELEN]={'a', 'b', 'd', 'c', 'e', 'f'}; char szInOrder[TREELEN]={'d', 'b', 'a', 'e', 'c', 'f'}; NODE* pRoot = NULL; Rebuild(szPreOrder,szInOrder,TREELEN,&pRoot); }
抱歉!评论已关闭.