华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 1850|回复: 2
打印 上一主题 下一主题

NOIP2001普及组 求先序遍历

[复制链接]

61

主题

147

帖子

563

积分

超级版主

Rank: 8Rank: 8

积分
563
跳转到指定楼层
楼主
发表于 2016-2-18 15:30:59 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
题目描述:

描述 Description         

给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示,长度≤8)。

输入格式 Input Format      

      第一行为二叉树的中序序列

    第二行为二叉树的后序序列

输出格式 Output Format     

      一行,为二叉树的先序序列

样例输入 Sample Input      

      BADC BDCA

样例输出 Sample Output     

      ABCD
回复

使用道具 举报

61

主题

147

帖子

563

积分

超级版主

Rank: 8Rank: 8

积分
563
沙发
 楼主| 发表于 2016-2-18 15:31:30 | 只看该作者
题目分析:

已知中序和前序排列,或者已知中序和后序序列,都能够构造一棵二叉树,此题考查后者。

前序遍历的规律是:输出根结点,输出左子树,输出右子树;  

中序遍历的规律是:输出左子树,输出根结点,输出右子树;

后序遍历的规律是:输出左子树,输出右子树,输出根结点;

根据中序和后序序列的规律,我们可以知道构造二叉树的过程是一个递归的过程,根据给定的 中序和后序序列,建立二叉树的根结点,并将中序序列划分为左子树序列和右子树序列,然后分别把左子树序列和右子树序列递归的构造左子树和右子树。

具体的算法是分别用数组mid[lm..rm]和post[tp..rp]存储给定的中序和后序序列。易知post[rp]为根结点,创建二叉树的根结点t,设t->data = post[rp];遍历mid,寻找根结点post[rp]的下标pos,则mid[lm..pos-1]为左子树序列,mid[pos+1..rm]为右子树序列;左子树序列的长度lenL= pos - lm,右子树序列的长度lenR= rm - pos。

很明显,若pos == lm,则lenL = 0,说明根结点无左子树;若pos == rm,则lenR = 0,说明根结点无右子树;  

根据后序序列的规律,可以知道根结点t的左子树的后序排列为post[lp..lp+lenL-1];

根结点t的右子树的后序排列为post[lp+lenL..rp-1]。

采用同样的方法递归构造根结点t的左右子树。

以样例输入为例:

中序序列:BADC

后序序列:BDCA   

1.得到根结点t->data = 'A';

2.遍历中序序列mid,得到mid[pos] = 'A',lenL = 1;

3.得到根结点t的左子树的中序序列为mid[lm..pos-1] = "B",右子树的中序序列为mid[pos+1..rm] = "DC";根结点t的左子树的后序序列为post[lp..lp+lenL-1] = "B",右子树的后序序列为post[lp+lenL..rp-1] = "DC";

4.递归构造根结点t的左子树t->lc,设t= t->lc:

           1.得到根结点t->data = 'B';

           2.遍历中序序列mid,得到mid[pos] = 'B',lenL = 0;

           3.得到根结点t的左右子树均为空,返回调用函数。

5. 递归构造根结点t的右子树t->rc,设t= t->rc:

           1.得到根结点t->data = 'C';

           2.遍历中序序列mid,得到mid[pos] = 'C',lenL = 1;

           3.得到根结点t的左子树的中序序列为"D",后序序列为"D";右子树为空,

           4.递归构造根结点t的左子树t->lc;

6.最后得到整棵二叉树,前序遍历二叉树,得到前序序列:ABCD。



说明:

算法思想:递归和分治。

数据结构:数组,二叉树。

时间复杂度:O(N);

空间复杂度:O(N);

程序语言:分别用c++和pascal实现。



附注:

若题目改为已知中序和前序序列,输出后序序列,因为先序序列pre[lp..rp]中根结点是第一个元素,所以只需将函数中的根结点数据由t->data = post[rp] 改为t->data = pre[lp]; 然后在递归构造左右子树时注意左子树中序序列为mid[lm+1..pos-1],右子树中序序列为mid[pos+1..rm],左子树先序序列为pre[lp+1..lp+lenL],右子树先序序列为pre[lp+lenL+1..rp],

最后后序遍历二叉树就行了。  
回复 支持 反对

使用道具 举报

61

主题

147

帖子

563

积分

超级版主

Rank: 8Rank: 8

积分
563
板凳
 楼主| 发表于 2016-2-18 15:32:42 | 只看该作者
  1. #include<iostream>

  2. #include<string>



  3. using namespace std;



  4. typedef struct BTNode{

  5.       char data;

  6.       struct BTNode *lc, *rc;//左,右孩子指针

  7. } *BTree;



  8. void PostBtree(BTree & t, string mid, string post, int lm, int rm, int lp, int rp);

  9. void Preorder(BTree p);



  10. int main(int argc, char* argv[])

  11. {

  12.     string mid, post;

  13.     BTree root;

  14.    

  15.     cin >> mid;

  16.     cin >> post;

  17.     PostBtree(root, mid, post, 0, mid.size()-1, 0, post.size()-1);

  18.     Preorder(root);

  19.    

  20.     system("pause");

  21.     return 0;

  22. }



  23. /*

  24. 函数名称:PostBtree

  25. 函数功能:给出一棵二叉树的中序与后序序列,构造这棵二叉树。

  26. 输入参数: BTree & t:二叉树的结点t

  27.           string mid:存储了二叉树的中序序列的字符串

  28.           string post:存储了二叉树的后序序列的字符串

  29.           int lm, int rm:二叉树的中序序列在数组mid中的左右边界

  30.           int lp, int rp:二叉树的后序序列在数组post中的左右边界

  31. */

  32. void PostBtree(BTree & t, string mid, string post, int lm, int rm, int lp, int rp)

  33. {

  34.     t = new BTNode; //构造二叉树根结点

  35.     t->data = post[rp];

  36.     t->lc = t->rc = NULL;

  37.    

  38.     int pos = lm;

  39.     while (mid[pos] != post[rp])

  40.         pos++;

  41.     int lenL = pos - lm;

  42.     if (pos > lm)//有左孩子,递归构造左子树

  43.         PostBtree(t->lc, mid, post, lm, pos-1, lp, lp+lenL-1);

  44.     if (pos < rm)//有右孩子,递归构造右子树

  45.         PostBtree(t->rc, mid, post, pos+1, rm, lp+lenL, rp-1);

  46. }

  47. //先序遍历

  48. void Preorder(BTree p)

  49. {

  50.        if(p != NULL)

  51.        {

  52.               cout << p->data; //输出该结点

  53.               Preorder(p->lc); //遍历左子树

  54.               Preorder(p->rc); //遍历右子树

  55.        }

  56. }
复制代码
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-12-26 14:01 , Processed in 0.104178 second(s), 24 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表