学步园

问题来源：《编程之美》3.9 重建二叉树

给定一棵二叉树，假设每个节点都用唯一的字符来表示，具体结构如下：

struct Node
{
    struct Node *pLeft;
    struct Node *pRight;
    char chValue;
};

假设已经有了前序遍历和中序遍历的结果，希望通过一个算法重建这棵树。

给定函数的定义如下：

void ReBuild(char *pPreOrder, char *pInOrder, int nTreeLen, Node **pRoot)

参数：

pPreOrder： 以NULL为结尾的前序遍历结果的字符串数组

pInOrder: 以NULL为结尾的中序遍历结果的字符串数组

nTreeLen: 遍历结果字符串数组的大小

pRoot: 返回Node **类型，根据前序和中序遍历结果重新构建树的根节点。

前序遍历的每一个节点，都是当前子树的根节点，同时，以对应的节点为边界，就会把中序遍历的结果分为左子树和右子树。

例如：

前序遍历：a b d c e f

中序遍历: d b a e c f

前序遍历第一个节点a, 在中序遍历的字符串中找到，然后将中序遍历的字符串分为两部分，前一部分 db 刚好是以a为根节点的左子树的中序遍历结果，后一部分ecf是以a为根节点的右子树的中序遍历结果，同时可以计算出左子树和右子树的长度，这样就可以递归重建出二叉树。

程序描述如下：

void ReBuild(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;

    //如果当前树长度为1，那么已经是最后一个节点了
    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;

    //重建左子树
    if(nLeftLen > 0)
        ReBuild(pPreOrder + 1, pInOrder, nLeftLen, &((*pRoot)->pLeft));
    
    //重建右子树
    if(nRightLen > 0)
        ReBuild(pPreOrder + nLeftLen + 1, pInOrder + nLeftLen + 1, nRightLen, &((*pRoot)->pRight));
}

示例调试代码如下：

int main()
{
    char szPreOrder[] = {'a', 'b', 'd', 'y', 'c', 'e', 'f'};
    char szInOrder[] = {'y', 'd', 'b', 'a', 'e', 'c', 'f'};

    Node *pRoot = NULL;
    ReBuild(szPreOrder, szInOrder, sizeof(szPreOrder)/sizeof(char), &pRoot);

    printf("\n");
}

从上面的测试代码来看，个人认为使用

if(pPreOrder == NULL || pInOrder == NULL) {
        return;
    }

来检查边界条件不太靠谱，因为最后我们执行pPreOrder + 1 时，指针后移之后所指向的位置有可能会是野指针，也就是不为NULL，下面是我个人所写代码，使用左右子树的长度才终止递归，经测试，在前序遍历和中序遍历都正确的情况下，重建的二叉树也是正确的，有不同意见欢迎指点。

#include <stdlib.h>
#include <stdio.h>

struct Node
{
    struct Node *pLeft;
    struct Node *pRight;
    char chValue;
};

//以前序遍历的方式生成二叉树
void rebuild(char *pPreOrder, char *pInOrder, int nTreeLen, struct Node **pRoot)
{
    if(nTreeLen == 0) {
        (*pRoot) = NULL;
        return;
    }
    else {
        *pRoot = (struct Node *)malloc(sizeof(struct Node)); //为新的节点分配内存

        int leftLen;
        for(leftLen = 0; leftLen < nTreeLen; ++leftLen) {      //在中序遍历结果中寻找根节点的位置，根节点将其左子树和右子树遍历结果分开
            if(pInOrder[leftLen] == pPreOrder[0])
                break;
        }

        if(*pRoot) {
            (*pRoot)->chValue = pPreOrder[0];
            rebuild(pPreOrder+1, pInOrder, leftLen, &(*pRoot)->pLeft);     //递归建立左子树，注意遍历结果指针的移动及长度的变化
            rebuild(pPreOrder+leftLen+1, pInOrder+leftLen+1, nTreeLen-leftLen-1, &(*pRoot)->pRight);  //递归建立右子树
        }
        
    }
}

//打印二叉树，测试程序的正确性
void printList(struct Node *pRoot)
{
    if(pRoot != NULL) {
        //printf("%c", (pRoot)->chValue);
        printList((pRoot)->pLeft);
        printf("%c", (pRoot)->chValue);
        printList((pRoot)->pRight);
        //printf("%c", (pRoot)->chValue);
    }
}

int main()
{
    char szPreOrder[] = {'a', 'b', 'd', 'y', 'c', 'e', 'f'};
    char szInOrder[] = {'y', 'd', 'b', 'a', 'e', 'c', 'f'};

    struct Node *pRoot = NULL;
    rebuild(szPreOrder, szInOrder, sizeof(szPreOrder)/sizeof(char), &pRoot);
 
    printList(pRoot);
    printf("\n");
}

我的微博：http://weibo.com/caryaliu