注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zhouhaigang.love的博客

喜欢冬日黄昏那冻住的山

 
 
 

日志

 
 

二叉树  

2011-01-06 12:52:04|  分类: C语言 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

二叉树的遍历你掌握了吗?

研究性学习 2008-12-05 19:54:56 阅读423 评论0   字号: 订阅

      本文发表在中小学电脑报《noi专刊》2008年11月                     湖南郴州市第二中学    宁海燕

一、二叉树遍历概述

遍历是对树结构的一种最基本的运算,所谓遍历二叉树,就是按一定的规则和顺序走遍二叉树的所有结点,使每一个结点都被访问一次,而且只被访问一次。由于二叉树是非线性结构,因此,二叉树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。从二叉树结构定义理解,二叉树是由根结点、左子树、和右子树三个基本单元构成,如果能够依次遍历这三个部分,则能遍历整个二叉树。若限定先左子树后右子树,按照访问根结点的顺序,我们可以得到三种遍历方式:

   (一)、先序遍历:

若二叉树为空,则空操作,否则访问根接点,先序遍历左子树,先序遍历右子树。

由此可见,二叉树的遍历是一种递归操作。根据二叉树的结构定义,我们可以得到先序遍历二叉树的算法如下:

   Procedure xianxu(p:tree)  {先序遍历根结点指针为p的二叉树}

   Begin

     If p<>nil then

      Begin

       Vist(p);

       Xianxu(p.lchild);

       Xianxu(p.rchild);

      End;

   End.

(二)、中序遍历:

若二叉树为空,则空操作,否则中序遍历左子树,访问根结点,中序遍历右子树。

中序遍历二叉树的算法如下:

   Procedure  zhongxu(p:tree)  {中序遍历根结点指针为p的二叉树}

   Begin

     If p<>nil then

      Begin

       zhongxu(p.lchild);

       Vist(p);

       zhongxu(p.rchild);

      End;

   End.

(三)、后序遍历:

若二叉树为空,则空操作,否则后序遍历左子树,后序遍历右子树,访问根结点。

后序遍历二叉树的算法如下:

   Procedure  hou xu(p:tree)  {后序遍历根结点指针为p的二叉树}

   Begin

     If p<>nil then

      Begin

       houxu(p.lchild);

       houxu(p.rchild);

 Vist(p);

      End;

   End.

下面我们看一个例子,如下图(一)所示的一棵二叉树,我们用先序、中序、后序分别遍历该二叉树,看能得到什么表达式:

 

n

m

*

b

x

c

d

                   (图一)

 

按照先序遍历该二叉树,可得到表达式:

* n x b m / c d   

该表达式称为该二叉树的前缀表达式(或称为波兰式)。

按照中序遍历该二叉树,可得到表达式:

   n (xb)*mc/d

该表达式称为该二叉树的中缀表达式(该表达式就是我们数学习惯常用的表达式)。

按照后序遍历该二叉树,可得到表达式:

  n x b m * cd /

该表达式称为该二叉树的后缀表达式(或称为逆波兰式)。

二、典型考题

下面我们来看几道NOIP试题:

1[NOIP2001]已知一棵二叉树的结点名为大写英文字母,其中序与后序遍历的顺序分别为:

CBGEAFHDIJ,CGEBHFJIDA 则该二叉树的先序遍历序列为(     )。

[解析]如果由中序遍历序列和后序遍历序列可以画出这棵二叉树的示意图,那么我们就可以很容易的得到该二叉树的先序遍历。怎样画出来呢?我们总结了下面四条规则:

1)、树的前序序列的第一个结点,即为该树的根结点;

2)、树的后序序列的最后一个结点,即为该树的根结点;

3)、树的中序序列中,在根结点左边的为左子树的中序序列,在根结点右边的为右子树的中序序列;

4)、树的前序序列中,根结点之后是左子树的前序序列,再是右子树的前序序列。

反复应用这4条规则这类题目都可以解决。例如本题,我们已知中序与后序遍历的顺序分别为:CBGEAFHDIJ,CGEBHFJIDA根据第2条,可知A是该二叉树的根结点,再根据第3条可知CBGE 为左子树上的结点,FHDIJ为右子树上的结点,再根据第2条,可知B为左子树的根结点,再根据第3条,C为以B为根结点的左子树,GE为以B为根的右子树上的结点,再根据第2条,E结点为右子树的根,再据第3条,知G为以E为根的左子树。那么以A 为根的左子树就确定了,按同样的方法,按着上面的四条规则,我们可以得到下图(图二)所示:

A

C

G

E

B

D

F

I

J

H

(图二)

从图二我们可以得到先序遍历序列为:ABCEGDFHIJ

2[NOIP2003]表达式(1+34*5-567的后缀表达式为( 

 A1+34*5-567  B-*+1 345567   C1 34+5*56 7-   D1 345*+56 7-

 E1 34+5 567-*

[解析]

该题我们已知中缀表达式,按照题1规则中的第3条,我们可以尝试按中序遍历的顺序画出该棵二叉树的示意图(图三),其实利用树对表达式进行处理是树结构的一个重要应用。

---

+

1

5

*

/

566

7

34

(图三)

故按后序遍历可得到后缀表达式为:1 34 + 5 * 56 7 / -,故选C

3[NOIP2004] 二叉树T,已知其前序遍历序列为1 2 4 3 5 7 6,中序遍历序列为4 2 1 5 7 3 6,则其后序遍历序列为( )。

A. 4 2 5 7 6 3 1   B. 4 2 7 5 6 3 1   C. 4 2 7 5 3 6 1   D. 4 7 2 3 5 6 1  

E. 4 5 2 6 3 7 1

[解析]此题的解法同题1,我们根据4条规则分析可得:1为二叉树的根,2为左子树的根,4为以2为根的左子树,3为右子树的根,56分别为以3为根的左、右子树,7为以5为根的右子树。如(图四),那么我们很容易得到其后序遍历序列为:4 2 7 5 6 3 1,故选B

1

4

2

3

5

6

7

(图四)

4、下面我们来看最近三年的考题:

[NOIP2005] 已知 6 个结点的二叉树的先根遍历是 1 2 3 4 5 6(数字为结点的编号,以下同),后根遍历是3 2 5 6 4 1,则该二叉树的可能的中根遍历是(  

 A. 3 2 1 4 6 5             B. 3 2 1 5 4 6

C. 2 3 1 5 4 6             D. 2 3 1 4 6 5

[NOIP2007] 已知7个点的二叉树的先根遍历是1 2 4 5 6 3 7(数字为结点的编号,以下同) 后根遍历是4 6 5 2 7 3 1 则该二叉树的可能的中根遍历是(   

A. 4 2 6 5 1 7 3            B. 4 2 5 6 1 3 7

C. 4 2 3 1 5 4 7            D. 4 2 5 6 1 7 3

[NOIP2008]二叉树T,已知其先序遍历是1 2 4 3 5 7 6(数字为节点编号,以下同),后序遍历是4 2 7 5 6 3 1,则该二叉树的中根遍历是(  

A4 2 1 7 5 3 6   B2 4 1 7 5 3 6   C4 2 1 7 5 6 3    D2 4 1 5 7 3 6

[解析]

最近三年二叉树的遍历问题一改以前的单选为不定项选择,每年的题型一致,都是已知先序遍历和后序遍历的基础上,求可能的中序序列。这类考题较往年难度有所加大。但我们只要抓住在题1中介绍的四条规则,我们还是能很轻松的把这类问题解决。以[NOIP2005]为例,我们可用排除法得到答案,我们一一假设四个选项是正确的,A.3 2 1 4 6 5是该二叉树的中序遍历,结合四条规则中第3条知4 5 6是以1为根的右子树上的结点,从先根遍历1 2 3 4 5 6,知4应该是结点5 6 的根,但其后序序列为3 2 5 6 4 1,且结合中序序列,知5  6为以4为根的右子树上的结点,又根据先序序列知5 6的根,则与后序3 2 5 6 4 1中的5 6访问顺序矛盾(5要在6后访问 ),故A假设不成立。假设B选项正确,同A假设,5 4 6为以1为根的右子树上的结点,由先序序列知4为根,5为以4为根的左子树,6为以4为根的右子树。我们可以很明了的得到以下一棵二叉树(图五),明显先序、中序、后序都满足题设要求。同理分析C选项也是正确的。得到的二叉树如(图六),D选项的矛盾同选项A。故答案为B C[NOIP2007][NOIP2008]的分析方法与上类同,希望同学们自己开动脑筋得到答案, [NOIP2007]答案为ABD ,[NOIP2008]答案为ABD。其可能的二叉树示意图分别如(图七)(图八)(图九)(图十)(图十一)(图十二)所示。

 

 

 

1

3

2

4

5

6

1

3

2

4

5

6

(图五)

1

3

2

4

5

6

(图六)

 

1

4

2

3

5

6

7

1

4

2

3

5

6

7

A图七)                                                B图八)

 

1

4

2

3

5

6

7

1

4

2

3

5

6

7

 

 

 

 

 

 

 

 

 


A图十)

                                                 (D图九)

 

 

 

 

 

 

 

 

1

4

2

3

5

6

7

1

4

2

3

5

6

7

               

 

 

 

 

 

 

 

                                                                                                                       D图十二)

                                           B图十一)

 

三、小结

二叉树的遍历在每年的NOIP初赛中基本都会涉及考题,但不管考题怎么变化,我们解决此类题目应先把握好三种遍历的基本概念(三种遍历都是递归操作)。

再次我们利用以下四点规则:

1)、树的前序序列的第一个结点,即为该树的根结点;

2)、树的后序序列的最后一个结点,即为该树的根结点,

3)、树的中序序列中,在根结点左边的为左子树的中序序列,在根结点右边的为右子树的中序序列;

4)、树的前序序列中,根结点之后是左子树的前序序列,再是右子树的前序序列。

最后我们最好用笔画出二叉树的示意图。看其是否满足题设条件,以免万无一失。

四、思考题[NOIP2003复赛试题]

加分二叉树

[问题描述]

设一个n个节点的二叉树tree的中序遍历为(l,2,3,,n),其中数字1,2,3,,n为节点编号。每个节点都有一个分数(均为正整数),记第j个节点的分数为ditree及它的每个子树都有一个加分,任一棵子树subtree(也包含tree本身)的加分计算方法如下:

subtree的左子树的加分× subtree的右子树的加分+subtree的根的分数

若某个子树为主,规定其加分为1,叶子的加分就是叶节点本身的分数。不考虑它的空子树。

试求一棵符合中序遍历为(1,2,3,,n)且加分最高的二叉树tree。要求输出;

1tree的最高加分(2tree的前序遍历

[输入格式]

1行:一个整数nn30),为节点个数。

2行:n个用空格隔开的整数,为每个节点的分数(分数<100)。

[输出格式]

1行:一个整数,为最高加分(结果不会超过4,000,000,000)。

2行:n个用空格隔开的整数,为该树的前序遍历。

[输入样例]

5

5 7 1 2 10

[输出样例]

145

3 1 2 4 5

  评论这张
 
阅读(98)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017