免费智能真题库 > 历年试卷 > 程序员 > 2009年上半年 程序员 上午试卷 综合知识
  第38题      
  知识点:   树的存储结构及遍历操作   FC   二叉树
  关键词:   二叉树   中序遍历   遍历        章/节:   常用数据结构       

 
二叉树的先序遍历序列为ABFCDE、中序遍历序列为BFADCE,则该二叉树根的左孩子和右孩子结点分别是(38)。
 
 
  A.  B 和 F
 
  B.  F 和 B
 
  C.  B 和 C
 
  D.  C 和 B
 
 
 

 
  第40题    2012年上半年  
   56%
对于任意一个结点数为n (n>0)的二叉树,其高度h (40)。
  第41题    2019年下半年  
   48%
若某二叉树的先序遍历序列是ABDCE,中序遍历序列是BDACE,则该二叉树为(41)。
  第30题    2019年上半年  
   24%
表达式( )的结构可用下面的二叉树表示(其中*、—、+表示算术运算的乘、减、加)。
   知识点讲解    
   · 树的存储结构及遍历操作    · FC    · 二叉树
 
       树的存储结构及遍历操作
        1)树的存储结构
        树是非线性的结构,存储树时,须把树中节点之间存在的关系反映在树的存储结构中。树有很多存储结构,这里仅介绍最常用的两种。
        (1)树的标准存储结构。
        树的标准存储结构由节点的数据和指向子节点的指针数组组成;对于度为M的树,其指针数组中的元素个数为M
        (2)树的带逆存储结构。
        由于树的带逆存储结构需要一个从子节点指向父节点的指针,因而该结构在标准存储结构的基础上,需要在树的节点中增加一个指向其双亲节点位置的指针。
        2)树的遍历
        树的遍历是树的基本操作之一,也是最重要的操作之一。树的遍历含义是指:按照某种要求依次访问树中的每个节点,每个节点均被访问一次且仅被访问一次。常用的树的遍历方法可分为前序遍历、后序遍历和中序遍历。
        (1)树的前序遍历。
        首先访问根节点,然后从左到右前序遍历根节点的各棵子树。树的前序遍历递归算法如下:
        
        若利用栈来记录当前未访问完的子树的根节点指针,则前序遍历的非递归算法如下:
        
        (2)树的后序遍历。
        树的后序遍历的基本思想是:先依次遍历每棵子树,然后访问根节点,与后序遍历二叉树相同。树的后序遍历递归算法如下:
        
        (3)树的中序遍历。
        树的中序遍历的基本思想是:先左子树,遍历根节点,然后依次遍历其他各棵子树,类似二叉树的中序遍历。树的中序遍历递归算法如下:
        
 
       FC
        Fiber Channel(FC)是由美国标准化委员会(ANSI)的X3T11小组于1988年提出的高速串行传输总线,解决了并行总线SCSI遇到的技术瓶颈。FC总线技术由于具备高速率的数据传输特性、较高可靠性、可扩展性强等特点被认为是未来航空总线发展的主要数据总线之一。目前支持1x、2x、4x和8x的带宽连接速率,随着技术的不断发展该带宽还在不断进行扩展,以满足更高带宽数据传输的技术性能要求。
        光纤通道具有如下特点:
        (1)高带宽、多媒介、长距离传输:串行传输速率已由最初的1Gb/s提高到4Gb/s,并且正在向更高速率、更大数据吞吐量发展,适用于不同模块间大规模应用数据(如音频、视频数据流)交换;以光纤、铜缆或屏蔽双绞线为传输介质,低成本的铜缆传输距离为25m,多模光纤传输距离为0.5km,单模光纤传输距离为10km。
        (2)可靠性与实时性:多种错误处理策略,32位CRC校验,利用优先级不同适应不同报文要求,并解决媒介访问控制时的冲突,传输误码率低于10~12,端到端的传输延迟小于10μs,支持非应答方式与传感器数据传输。
        (3)统一性与可扩展性:可以方便的增加和减少结点以满足不同应用需求,拓扑结构灵活,支持多层次系统互连,利用高层协议映射提高兼容和适应能力。可以把SCSI、IP、ATM等协议映射到光纤通道上,以有效地减少物理器件与附加设备的种类并降低经济成本。
        (4)开放式互连,遵循统一的国际标准。光纤通道(FC)是高吞吐量、低延时、包交换及面向连接的网络技术。整个标准系列还在不断的发展,其中用于航空领域-航空电子系统环境工程(FC-AE)的协议规范已经定制了5种,分别是:无签名的匿名消息传输(FC-AE-ASM)、MIL-STD-1553高层协议(FC-AE-1553)、虚拟接口(FC-AE-VI)、FC轻量协议(FC-AE-FCLP)、远程直接存储器访问协议(FC-AE-RDMA)。
 
       二叉树
               二叉树的定义
               二叉树(Binary Tree)是n(n≥0)个节点的有限集合,它或者是空树(n=0),或者是由一个根节点及两棵互不相交的、分别称为左子树和右子树的二叉树所组成。
               二叉树与树的区别如下。
               .二叉树的节点的子树要区分左子树和右子树,即使在节点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。
               .二叉树的节点的最大度为2,而树中不限制节点的度数。
               二叉树的运算
               二叉树的基本运算是遍历,其他运算可建立在遍历运算的基础上。
               二叉树的性质
               二叉树具有以下性质。
               (1)二叉树第i层上的节点数目最多为2i-1(i≥1)个。
               (2)深度为k的二叉树至多有2k-1(k≥1)个节点。
               (3)在任意一棵二叉树中,若终端节点数为n0,度为2的节点数为n2,则n0=n2+1。
               (4)具有n个节点的完全二叉树的深度为[log2n]+1。
               (5)对一棵有n个节点的完全二叉树的节点按层次自左至右进行编号,则对任意节点i有以下性质。
               .若i=1,则节点i是二叉树的根,无双亲;若i>1,则其双亲为
               .若2i>n,则节点i无左孩子;否则其左孩子为2i
               .若2i+1>n,则节点i无右孩子;否则其右孩子为2i+1。
               若深度为k的二叉树有2k-1个节点,则称其为满二叉树。
               深度为k、有n个节点的二叉树,当且仅当其每一个节点都与深度为k的满二叉树编号从1至n的节点一一对应时,称之为完全二叉树。
               二叉树的存储结构
               1)顺序存储结构
               用一组地址连续的存储单元存储二叉树中的数据元素,必须把节点排成一个适当的线性序列,并且节点在这个序列中的相互位置能反映出节点之间的逻辑关系。
               顺序存储结构用于完全二叉树时既简单又节省空间,而对于一般二叉树则不适用。因为在顺序存储结构中,以节点在存储单元中的位置来表示节点之间的关系,那么对于一般的二叉树来说,也必须按照完全二叉树的形式存储,也就是要添上一些实际并不存在的"虚节点",这将造成空间的浪费。
               2)链式存储结构
               由于二叉树中的节点包含有数据元素、左子树根、右子树根及双亲等信息,因此可以用三叉链表或二叉链表来存储二叉树,链表的头指针指向二叉树的根节点。
               二叉树的遍历
               遍历是指按某种策略访问树中的每个节点,且仅访问一次。由于二叉树所具有的递归性质,一棵非空的二叉树可以看作由根节点、左子树和右子树三部分构成,因此若能依次遍历这三部分中的每个节点信息,也就遍历了整棵二叉树。按照遍历左子树要在遍历右子树之前进行的约定,根据访问根节点位置的不同,可得到二叉树的前序、中序和后序3种遍历方法。
               遍历二叉树的基本操作就是访问节点,不论按照哪种次序遍历,对含有n个节点的二叉树,遍历算法的时间复杂度都为O(n)。在最坏情况下,二叉树是有n个节点且深度为n的单枝树,遍历算法的空间复杂度也为O(n)。
               遍历二叉树的过程实质上是按一定规则,将树中的节点排成一个线性序列的过程,因此遍历操作得到的是树中节点的一个线性序列。在每一种序列中,有且仅有一个起始点和一个终节点,其余节点有且仅有唯一的直接前驱和直接后继。
               对二叉树还可以进行层序遍历。层序遍历就是从树的根节点出发,首先访问第1层的树根节点,然后从左到右依次访问第2层上的节点,以此类推,自上而下、自左到右逐层访问树中各层上节点的过程。
               线索二叉树
               若n个节点的二叉树采用链表作存储结构,则链表中含有n+1个空指针域,利用这些空指针域来存放指向节点的前驱和后继信息。线索链表的节点结构如下图所示。
               
               线索链表的节点结构
               若二叉树的二叉链表采用上图所示的节点结构,则相应的链表称为线索链表,其中指向节点前驱、后继的指针称为线索,加上线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。
               二叉树的应用:最优二叉树
               霍夫曼树又称最优二叉树,是一类带权路径长度最短的树。
               路径:是指从树中一个节点到另一个节点之间的通路,路径上的分支数目称为路径长度。
               树的路径长度:是从树根到每一个叶子的路径长度之和。节点的带权路径长度为从该节点到树根之间的路径长度与该节点权的乘积。
               树的带权路径长度:指树中所有叶子节点的带权路径长度之和,记为
               
               式中,n为带权叶子节点的数目;wi为叶子节点的权值;li为叶子节点到根的路径长度。
               霍夫曼树是指权值为w1w2,…,wnn个叶子节点的二叉树中带权路径长度最小的二叉树。
               构造最优二叉树的霍夫曼算法如下。
               (1)根据给定的n个权值w1w2,…,Wn构成n棵二叉树的集合F={T1,T2,…,Tn},其中每棵二叉树Ti中只有一个带权为wi的根节点,其左右子树均空。
               (2)在F中选取两棵根节点的权值最小的树作为左右子树,构造一棵新的二叉树,置新构造二叉树的根节点的权值为其左、右子树根节点的权值之和。
               (3)从F中删除这两棵树,同时将新得到的二叉树加入到F中。
               重复(2)、(3),直到F中只含一棵树时为止。这棵树便是霍夫曼树。
               树和森林
               1)树的存储结构
               .树的双亲表示法:用一组地址连续的单元存储树的节点,并在每个节点中附设一个指示器,指示其双亲节点在该存储结构中的位置。显然这种表示对于求指定节点的双亲或祖先都十分方便,但对于求指定节点的孩子及后代则需要遍历整个数组。
               .树的孩子表示法:在存储结构中用指针指示出节点的每个孩子,由于树中每个节点的子树数目不尽相同,因此在采用链式存储结构时可以考虑多重链表。
               .树的孩子兄弟表示法:又称二叉链表表示法。在链表的节点中设置两个指针域分别指向该节点的第一个孩子和下一个兄弟。利用这种存储结构便于实现树的各种操作。
               2)树和森林的遍历
               (1)树的遍历。树的遍历分为先根遍历和后根遍历两种。
               .先根遍历:先访问树的根节点,然后依次先根遍历根的各棵子树。对树的先根遍历等同于对转换所得的二叉树进行先序遍历。
               .后根遍历:先依次后根遍历树根的各棵子树,然后访问树根节点。树的后根遍历等同于对转换所得的二叉树进行中序遍历。
               (2)森林的遍历。森林的遍历分为前序遍历和后序遍历两种。
               .前序遍历森林:若森林非空,访问森林中第一棵树的根节点,前序遍历第一棵子树根节点的子树森林,再前序遍历除第一棵树之外剩余的树所构成的森林。
               .后序遍历森林:若森林非空,后序遍历森林中第一棵树的子树森林,访问第一棵树的根节点,后序遍历除第一棵树之外剩余的树所构成的森林。
               3)树、森林与二叉树的转换
               (1)树、森林转换为二叉树。利用树的孩子兄弟表示法可导出树与二叉树的对应关系,在树的孩子兄弟表示法中,从物理结构上看与二叉树的二叉链表表示法相同,因此就可以用这种同一存储结构的不同解释将一棵树转换为一棵二叉树。
               将一个森林转换为一棵二叉树的方法是:先将森林中的每一棵树转换为二叉树,再将第一棵树的根作为转换后的二叉树的根,第一棵树的左子树作为转换后二叉树根的左子树,第二棵树作为转换后二叉树根的右子树,第三棵树作为转换后二叉树根的右子树的右子树,以此类推,森林就可以转换为一棵二叉树。
               (2)二叉树转换为树和森林。若二叉树非空,则二叉树根及其左子树为第一棵树的二叉树形式,二叉树根的右子树又可以看作一个由森林转换后的二叉树,应用同样的方法,直到最后产生一棵没有右子树的二叉树为止,这样就得到了一个森林。为了进一步得到树,可用树的二叉链表表示的逆方法,即节点的右子树的根、右子树的右子树的根……找出原本是同一个双亲的兄弟。二叉树转换为树或森林是唯一的。
   题号导航      2009年上半年 程序员 上午试卷 综合知识   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
7 /
8 /
9 /
10 /
11 /
12 /
13 /
14 /
15 /
 
16 /
17 /
18 /
19 /
20 /
21 /
22 /
23 /
24 /
25 /
26 /
27 /
28 /
29 /
30 /
 
31 /
32 /
33 /
34 /
35 /
36 /
37 /
38 /
39 /
40 /
41 /
42 /
43 /
44 /
45 /
 
46 /
47 /
48 /
49 /
50 /
51 /
52 /
53 /
54 /
55 /
56 /
57 /
58 /
59 /
60 /
 
61 /
62 /
63 /
64 /
65 /
66 /
67 /
68 /
69 /
70 /
71 /
72 /
73 /
74 /
75 /
 
第38题    在手机中做本题