随笔 - 89  文章 - 118  trackbacks - 0
<2008年8月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
31123456

留言簿(16)

随笔分类(56)

随笔档案(89)

文章分类

推荐博客

搜索

  •  

最新随笔

最新评论

阅读排行榜

已知前序和中序:

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的工程,有兴趣的朋友点此下载。代码参考于《编程之美》。
posted on 2008-08-27 17:51 胡满超 阅读(883) 评论(0)  编辑 收藏 引用 所属分类: 算法

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理