面对现实,超越自己
逆水行舟,不进则退
posts - 269,comments - 32,trackbacks - 0
本文转自:http://www.cppblog.com/humanchao/default.html?page=2

已知前序和中序:

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 2012-05-24 13:57 王海光 阅读(715) 评论(1)  编辑 收藏 引用 所属分类: 算法

FeedBack:
# re: 重建二叉树(编程之美)[未登录]
2012-05-25 09:08 | 春秋十二月
像数据结构与算法之类的东西,可以参考stl的思想,实现工业强度的代码,便于扩展重用。  回复  更多评论
  

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