Chinaunix首页 | 论坛 | 博客
  • 博客访问: 4388568
  • 博文数量: 291
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 7924
  • 用 户 组: 普通用户
  • 注册时间: 2016-07-06 14:28
  • 认证徽章:
个人简介

阿里巴巴是个快乐的青年

文章分类

全部博文(291)

文章存档

2018年(21)

2017年(4)

2016年(5)

2015年(17)

2014年(68)

2013年(174)

2012年(2)

分类: 架构设计与优化

2013-05-12 16:36:59

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

图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;
        }
       




阅读(2427) | 评论(1) | 转发(3) |
给主人留下些什么吧!~~

scq2099yt2013-05-12 16:37:18

文明上网,理性发言...

评论热议
请登录后评论。

登录 注册