频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
数据结构例程——二叉树的构造
2015-10-20 15:34:29         来源:迂者-贺利坚的专栏  
收藏   我要投稿

本文是数据结构基础系列(6):树和二叉树中第13课时二叉树的构造的例程。

1.由先序序列和中序序列构造二叉树

定理:任何n(n≥0)个不同节点的二叉树,都可由它的中序序列和先序序列唯一地确定。 证明(数学归纳法)
基础:当n=0时,二叉树为空,结论正确。
假设:设节点数小于n的任何二叉树,都可以由其先序序列和中序序列唯一地确定。
归纳:已知某棵二叉树具有n(n>0)个不同节点,其先序序列是a0a1…an−1;中序序列是b0b1…bk−1bkbk+1…bn−1
先序遍历“根-左-右”,a0必定是二叉树的根节点 a0必然在中序序列中出现,设在中序序列中必有某个bk(0≤k≤n−1)就是根节点a0
这里写图片描述 由于bk是根节点,中序遍历“左-根-右”,故中序序列中b0b1…bk−1必是根节点bk(a0)左子树的中序序列,即bk的左子树有k个节点,bk+1…bn−1必是根节点bk(a0)右子树的中序序列,即bk的右子树有n−k−1个节点。 对应先序序列,紧跟在根节点a0之后的k个节点a1…ak是左子树的先序序列,ak+1…an−1n−k−1就是右子树的先序序列。
这里写图片描述 根据归纳假设,子先序序列a1…ak和子中序序列b0b1…bk−1可以唯一地确定根节点a0的左子树,而先序序列ak+1…an−1和子中序序列bk+1…bn−1可以唯一地确定根节点a0的右子树。 综上所述,这棵二叉树的根节点己经确定,而且其左、右子树都唯一地确定了,所以整个二叉树也就唯一地确定了。


这里写图片描述

根据定理的证明,写出下面的算法。<喎"https://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxibG9ja3F1b3RlPg0KCTxwPsa3zrajutLUyc+5udTs0NTWpMP3ysfNu7P2zOXP1rzGy+O7+r/G0ae1xLC4wP2ho7zGy+O7+tGnv8a1xL6ry+i+zdTa09rWxtTso6y8tMq51NombGRxdW87wO3C29DUJnJkcXVvO862tcC1xLaowO3W0KOsxuTWpMP3uf2zzKOsuPiz9rXEvs3KxyZsZHF1bzu05tTatcTV4sO00ru49rarzvcmcmRxdW87tcS5udTst723qKGjPC9wPg0KPC9ibG9ja3F1b3RlPg0KPHA+o9uyzr+8veK08KPdo6hidHJlZWUuaLz7y+O3qL/io6k8L3A+DQo8cHJlIGNsYXNzPQ=="brush:java;"> #include #include #include btree.h BTNode *CreateBT1(char *pre,char *in,int n) /*pre存放先序序列,in存放中序序列,n为二叉树结点个数, 本算法执行后返回构造的二叉链的根结点指针*/ { BTNode *s; char *p; int k; if (n<=0) return NULL; s=(BTNode *)malloc(sizeof(BTNode)); //创建二叉树结点*s s->data=*pre; for (p=in; plchild=CreateBT1(pre+1,in,k); //递归构造左子树 s->rchild=CreateBT1(pre+k+1,p+1,n-k-1); //递归构造右子树 return s; } int main() { ElemType pre[]=ABDGCEF,in[]=DGBAECF; BTNode *b1; b1=CreateBT1(pre,in,7); printf(b1:); DispBTNode(b1); printf( ); return 0; }

2.由后序序列和中序序列构造二叉树

定理:任何n(n>0)个不同节点的二叉树,都可由它的中序序列和后序序列唯一地确定。 证明:(略)
这里写图片描述

[参考解答](btreee.h见算法库)

#include 
#include 
#include btree.h

BTNode *CreateBT2(char *post,char *in,int n)
/*post存放后序序列,in存放中序序列,n为二叉树结点个数,
本算法执行后返回构造的二叉链的根结点指针*/
{
    BTNode *s;
    char r,*p;
    int k;
    if (n<=0) return NULL;
    r=*(post+n-1);                          //根结点值
    s=(BTNode *)malloc(sizeof(BTNode));     //创建二叉树结点*s
    s->data=r;
    for (p=in; plchild=CreateBT2(post,in,k);         //递归构造左子树
    s->rchild=CreateBT2(post+k,p+1,n-k-1);  //递归构造右子树
    return s;
}

int main()
{
    ElemType in[]=DGBAECF,post[]=GDBEFCA;
    BTNode *b2;
    b2=CreateBT2(post,in,7);
    printf(b2:);
    DispBTNode(b2);
    printf(
);
    return 0;
}

3.由顺序存储结构转为二叉链存储结构
这里写图片描述

[参考解答](btreee.h见算法库)

#include 
#include 
#include btree.h
#define N 30
typedef ElemType SqBTree[N];
BTNode *trans(SqBTree a,int i)
{
    BTNode *b;
    if (i>N)
        return(NULL);
    if (a[i]=='#')
        return(NULL);           //当节点不存在时返回NULL
    b=(BTNode *)malloc(sizeof(BTNode)); //创建根节点
    b->data=a[i];
    b->lchild=trans(a,2*i);                 //递归创建左子树
    b->rchild=trans(a,2*i+1);               //递归创建右子树
    return(b);                              //返回根节点
}
int main()
{
    BTNode *b;
    ElemType s[]=0ABCD#EF#G####################;
    b=trans(s,1);
    printf(b:);
    DispBTNode(b);
    printf(
);
    return 0;
}

 

点击复制链接 与好友分享!回本站首页
相关TAG标签 数据结构
上一篇:一元二次方程求解
下一篇:数据结构例程——线索化二叉树(中序)
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站