二叉树之重建

一、结点结构
        在二叉树的链接存储中，通常采用的方法是：每个结点中设置三个域，即值域、左指针域和右指针域，其结点结构如下：

图1 二叉树结点结构

        其中，data表示值域，用于存储放入结点的数据元素，left和right分别表示左指针域和右指针域，用于分别存储左孩子和右孩子结点（即左右子树的根结点）的存储位置（即指针）。
        链接存储的指针类型和结点定义如下：
        typedef struct bnode
        {
            ElemType data;
            struct bnode *left, *right;
        }btree;
        其中，ElemType可以是任意数据类型如int、float或者char等，在算法中，规定其默认为int类型。

二、重建二叉树
        假设已经有了二叉树前序遍历和中序遍历的结果，是否可以据此重建这棵二叉树，答案是肯定的。
        重建原理：
            前序遍历：先访问当前结点，然后以前序访问左子树、右子树。
            中序遍历：先以中序遍历左子树，接着访问当前结点，然后以中序遍历右子树。
            根据前序遍历和中序遍历的特点，可以发现如下规律：前序遍历的每个结点，都是当前子树的根结点，同时，以对应的结点为边界，就会把中序遍历的结果分为左子树和右子树。
            如下图所示的二叉树：

图1 二叉树

            前序遍历结果：a b d c e f
                                “a”是根结点
            中序遍历结果：d b a e c f
                                “a”是根结点，把字符串分成左右两个子树。
            “a”是前序遍历结点中的第一个元素，可以看出，它把中序遍历的结果分成了“db”和“ecf”两个部分，从上图1可以看出，这就是“a”的左子树和右子树的遍历结果。如果能够找到前序遍历中对应的左子树和右子树，就可以把“a”作为当前的根节点，然后依次递归下去，这样就能够把左子树和右子树的遍历结果依次恢复出来，其递归算法如下：
        #define TREELEN    6                        // 为了简单起见，定义树的长度即结点总数
        void ReBuild(char *pPreOrder,             // 前序遍历结果
                        char *pInOrder,                 // 中序遍历结果
                        int nTreeLen,                    // 树长度
                        btree *pRoot)                   // 根结点
        {
            // 检查边界条件
            if ((NULL == pPreOrder) || (NULL == pInOrder))
            {
                return;
            }
            // 获得前序遍历的第一个结点
            btree *pTemp = new btree;
            pTemp->data = *pPreOrder;
            pTemp->left = NULL;
            pTemp->right = NULL;
            // 如果结点为空，把当前结点复制到根结点
            if (NULL == *pRoot)
            {
                *pRoot = pTemp;
            }
            // 如果当前树长度为1，那么已经是最后一个结点
            if (1 == nTreeLen)
            {
                return;
            }
            // 寻找子树长度
            char *pOrgInOrder = pInOrder;
            char *pLeftEnd = pInOrder;
            int nTempLen = 0;
            // 找到左子树的结尾
            while (*pPreOrder != *pLeftEnd)
            {
                if ((NULL == pPreOrder) ||(NULL == pLeftEnd))
                {
                    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)->left));
            }
            // 重建右子树
            if (nRightLen > 0)
            {
                ReBuild(pPreOrder+nLeftLen+1, pInOrder+nLeftLen+1, nRightLen, &((*pRoot)->right));
            }
        }
        // 示例的调用代码
        int main(int argc, char **argv)
        {
            char szPreOrder[TREELEN] = {'a', 'b', d', 'c', 'e', 'f'};
            char szInOrder[TREELEN] = {'d', 'b', 'a', 'e', 'c', 'f'};
            btree *pRoot = NULL;
            ReBuild(szPreOrder, szInOrder, TREELEN, &pRoot);
            return 0;
        }