免费智能真题库 > 历年试卷 > 程序员 > 2009年上半年 程序员 上午试卷 综合知识
  第33题      
  知识点:   树和二叉树   语法分析阶段的主要任务   二叉树
  关键词:   表达式   二叉树        章/节:   软件基础知识   常用数据结构       

 
若算术表达式“a*(b-c)+d”采用二叉树描述,则合理的树结构为(33)。
 
 
  A. 
 
  B. 
 
  C. 
 
  D. 
 
 
 

 
  第29题    2019年上半年  
   48%
下面关于编译和解释的说法中,正确的是( )。
①编译是将高级语言源代码转换成目标代码的过程
②解释是将高级语言..
  第33题    2010年下半年  
   60%
某C语言程序中,m是一个整型变量,则(33)时遇到表达式m+"test"会报错。
  第30题    2009年下半年  
   43%
(30)的任务是将来源不同的编译单元装配成一个可执行程序。
  相关试题:树          更多>  
 
  第40题    2011年上半年  
   31%
当二叉树的结构形如(40)时,其后序遍历序列和中序遍历序列相同。
  第40题    2017年下半年  
   32%
对下图所示的二叉树进行中序遍历(左子树,根结点,右子树)的结果是( )。
  第34题    2017年上半年  
   34%
某二叉树的先序遍历(根、左、右)序列为 EFHIGJK 、中序遍历(左、根、右)序列为HFIEJGK, 则该二叉树根结点的左孩子结点和右孩子结..
   知识点讲解    
   · 树和二叉树    · 语法分析阶段的主要任务    · 二叉树
 
       树和二叉树
               树的递归定义理解
               树是零个或多个节点的有限集合。在一棵非空树中:
               .有一个特定的称为该树之根的节点。
               .除根外的其他节点被分成nn≥0)个不相交的集合T1,T2, …,Tn,其中每个集合本身是一棵树,树T1,T2, …,Tn称为根的子树。
               这是一个递归定义,即在树的定义中又用到树的概念,它指出了树的固有特性,具有一个节点的树必然由根组成,而具有n>1个节点的树则借助于小于n个节点的树来定义。特别要注意的是递归定义中各子树T1,T2, …,Tn的相对次序是重要的,即是有序的。
                      树的性质和基本概念
                      树包括以下一些基本性质。
                      .树中的节点数等于所有节点的度数加1。
                      .度为m的树中第i层上至多有mi-1个节点(i≥1)。
                      .高度为hm叉树至多有(mh-1)/(m-1)个节点。
                      .具有n个节点的m叉树的最小高度为|logmnm-1)+1)|。
                      树还包含树的度、节点数及叶子节点数等。关于如何对给定的树求出满足某种条件的树的节点数和叶子节点数等问题,下面列举两个例子来加以说明。
                      例1:已知一棵度为m的树中有N1个度为1的节点,N2个度为2的节点,……,Nm个度为m的节点。试问该树中有多少个叶子节点?
                      解决该问题的关键是将树的节点数和树中各节点的度联系起来。若设该树中叶子节点个数为N0,则该树节点个数为,因该树节点个数又为,故
                      ,即
                      例2:已知某度为k的树中,其度为0, 1, 2, …,k-1的节点数分别为n0,n1,n2, …,nk-1,求该树的节点总数。
                      设树的度为k的节点数为nk,则树的总节点数为:
                      n=n0+n1+…+nk-1+nk
                      而树的分支数(或连线数),即n-1为:n-1=n1+2n2+(k-1)nk-1+knk,故
                      
               树的存储结构及遍历操作
               1)树的存储结构
               树是非线性的结构,存储树时,须把树中节点之间存在的关系反映在树的存储结构中。树有很多存储结构,这里仅介绍最常用的两种。
               (1)树的标准存储结构。
               树的标准存储结构由节点的数据和指向子节点的指针数组组成;对于度为M的树,其指针数组中的元素个数为M
               (2)树的带逆存储结构。
               由于树的带逆存储结构需要一个从子节点指向父节点的指针,因而该结构在标准存储结构的基础上,需要在树的节点中增加一个指向其双亲节点位置的指针。
               2)树的遍历
               树的遍历是树的基本操作之一,也是最重要的操作之一。树的遍历含义是指:按照某种要求依次访问树中的每个节点,每个节点均被访问一次且仅被访问一次。常用的树的遍历方法可分为前序遍历、后序遍历和中序遍历。
               (1)树的前序遍历。
               首先访问根节点,然后从左到右前序遍历根节点的各棵子树。树的前序遍历递归算法如下:
               
               若利用栈来记录当前未访问完的子树的根节点指针,则前序遍历的非递归算法如下:
               
               (2)树的后序遍历。
               树的后序遍历的基本思想是:先依次遍历每棵子树,然后访问根节点,与后序遍历二叉树相同。树的后序遍历递归算法如下:
               
               (3)树的中序遍历。
               树的中序遍历的基本思想是:先左子树,遍历根节点,然后依次遍历其他各棵子树,类似二叉树的中序遍历。树的中序遍历递归算法如下:
               
               二叉树的递归定义
               二叉树是节点的集合,这个集合或者为空,或者是由一个根和两棵互不相交的被称为左子树和右子树的二叉树组成。二叉树中的每个节点至多有两棵子树,且有左右之分,次序不能颠倒。
               二叉树是一种重要的树型结构,但不是树的特例,其有5种形态,分别为:空(二叉树);只有根节点;根节点和左子树;根节点和右子树;根节点和左右子树。
               二叉树与树的区别:二叉树可以为空,每个节点子树不超过两个,而树至少有一个节点且节点子树无限制。
               二叉树的性质及其推广
               二叉树的性质如下。
               性质1在二叉树的第i层上至多有2i-1个节点(i≥1)。
               性质2深度为k的二叉树至多有2k-1个节点(k≥1)。
               性质3对任何一棵二叉树T,如果其终端节点数为n0,度为2的节点数为n2,则n0=n2+1。
               性质4具有n个节点的完全二叉树的深度为[log2n]+1。
               性质5如果有n个节点的完全二叉树,对任一节点i(1<in)满足:
               .如果i=1,则i为根,无双亲;若i>1,则i的双亲为[i/2]。
               .如果2i>n,则无左孩子,否则左孩子为2i
               .如果2i+1>n,则无右孩子,否则右孩子为2i+1。
               二叉树的有关性质可推广到k叉树,如:一棵含有n个节点的二叉树共含有n+1个空指针;而一棵含有n个节点的三叉树共含有2n+1个空指针。推而广之,一棵含有n个节点的k叉树共含有(k-1)n+1个空指针。
               不难看出,在k叉树的第i层上至多有ki-1个节点(i≥1);深度为Hk叉树至多有(kH-1)/(k-1)个节点(H≥1)。
               同理,可得到含N个节点和N个叶子节点的完全三叉树的高度分别为:
               
               其推导过程如下。
               (1)设含N个节点的完全三叉树的高度为H,则1+3+…+3H-2+1≤N≤1+3+…+3H-1, 3H-1≤2N-1≤3H-2,即H=[log32N-1]+1。
               (2)设含N个叶子节点的完全三叉树的高度为H,则3H-2N≤3H-1,即
               
               可进一步推广,含N个节点的完全k叉树的高度为
               H=[logkk-1)N-(k-2)]+1
               二叉树遍历的非递归
               二叉树的遍历是操作的重点,通常采用的递归算法不难实现和理解。但要实现二叉树遍历的非递归则有一定的难度,因而是理解二叉树遍历的难点。
               由于很多程序员考题中都隐含地利用二叉树遍历的非递归算法,如求二叉树中某个节点的祖先等,因而必须牢固地掌握二叉树的三种遍历的非递归算法。本质上,程序员考题中不是要考生遍历二叉树中的所有节点,而是遍历满足某种条件的节点并输出,在成功找到答案之前需要保留访问过的部分节点信息,因而须借助栈和队列等重要的数据结构。
               二叉链表的C语言描述如下:
               
               二叉树的前序、中序和后序遍历的非递归算法如下。
               1)前序遍历的非递归调用算法
               
               2)中序遍历的非递归调用算法
               
               3)后序遍历的非递归调用算法
               
               下面通过例子说明二叉树遍历的非递归应用。
               例如,在以二叉链表为存储结构的二叉树中,打印数据域值为x的节点(假定节点值不相同),并打印x的所有祖先的数据域值。
               解决此问题的算法思想是:若在查找某节点的过程中,记下其祖先节点,则可实现本问题要求。能实现这种要求的数据结构是栈,故设置一个栈用于装入x节点的所有祖先,而这种查找只有用非递归的后序遍历。
               栈的元素结构说明如下:
               
               用线索二叉树实现二叉树的非递归
               以二叉链表作为存储结构时,只能找到左、右子树信息,不能直接得到节点在任一序列中的前驱和后继信息,最简单的方法是每个节点上增加两个指针域,但有点浪费。其实,n个节点的二叉链表中必定存在n+1个空链域,因此可用这些链域来存放节点的前驱和后继信息。改进后的节点结构如下:
               
               其中,
               ltag=0:lchild域指示节点的左子树。
               ltag=1:lchild域指示节点的前驱。
               rtag=0:rchild域指示节点的左子树。
               rtag=1:rchild域指示节点的前驱。
               其C语言描述如下:
               
               以这种结构构成的二叉链表叫线索链表,其中指向节点前驱和后继的指针叫线索。加上线索的二叉树叫线索二叉树。对二叉树以某种次序遍历使其成为线索二叉树的过程叫线索化。
               对给定的线索二叉树中的某个节点p,查找节点p的后继(中序),其特点为所有叶子节点的右链直接指示了后继,所有非终端节点的后继应是其右子树中第一个中序遍历的节点。
               对给定的线索二叉树中的某个节点p,查找节点p的前驱(中序),其特点为若其左标志为"1",则左链为线索,指示其前驱,否则其前驱为左子树上最后遍历的一个节点。
               可见,对线索二叉树进行遍历可通过线索找到相应的前驱和后继,而无须递归进行。
               例如,对给定的中序线索化二叉树,查找节点*p的中序后继。在中序线索二叉树中,查找p指针的节点,其后继分为两种情况:若p→rtag=1,则p→rchild,即指向其后继节点;若p→rtag=0,则*p节点的中序后继必为其右子树中第一个中序遍历到的节点,即从*p的右子树开始,沿着左指针链向下找,直到找到一个没有左子树的节点,该节点就是*p的右子树中"最左下"的节点。其算法如下:
               
               二叉树与树或森林转换的目的
               由于树或森林可借用孩子兄弟表示法实现与二叉树的转换,因而我们只要研究二叉树的特性就行了,而无须对树或森林单独进行深入的讨论。
               这里仅给出森林和二叉树的转换算法,树和二叉树的转换算法类似。
               1)森林的二叉树表示
               森林转换成二叉树的步骤如下。
               设T={T1,T2,…,Tn}是森林,对应的二叉树B={root, LB, RB},则:
               (1)若T为空,即n=0,则B为空。
               (2)若T非空,即n>0,则二叉树的根为T1的根,其左子树是从T1中根节点的子树森林T={T11,T12,…,T1n}转换而成的二叉树;其右子树是从森林T={T2,T3,…,Tn}转换而成的二叉树。
               2)二叉树转化为森林
               若B是一棵二叉树,根为TL为左子树的根,R为右子树的根,则其相应的森林T{B}由下列步骤形成:
               (1)若B为空,则T为空。
               (2)若B非空,则B的根节点T为{T1, T2, …,Tn}的根节点,B[L]构成了T1的不相交的子树集合{T11T12,…,T1n};B[R]构成了森林中其他的树T2,…,Tn
               建立二叉树的若干方法
               建立二叉树的方法有很多,如按完全二叉树的形式输入字符序列,其中空格表示相应的子树为空。
               近年来,在程序员考试中经常出现的二叉树建立为:已知二叉树的后序序列和中序序列或已知二叉树的先序序列和中序序列,要求考生确定一棵二叉树。
               例如,一个二叉树的对称序列和后序序列分别是DCBAEFG和DCBGFEA,请给出该二叉树的前序序列。该题可通过后序遍历确定二叉树的根节点,然后找到该数据值在前序序列中的位置,并用该位置的左部序列和后序序列中的相应序列构造左子树,该位置的右部序列和后序序列中的相应序列构造右子树,如此不断地递归构造即可得到二叉树。建立的二叉树如下图所示。
               
               二叉树
               而且,该题还可引申到要考生证明已知二叉树的先序序列和中序序列,可唯一确定一棵二叉树;或要求考生针对已知二叉树的先序序列和中序序列,写出建立一棵二叉树的算法等。同时,要求考生证明已知二叉树的先序序列和后序序列,不能唯一确定一棵二叉树。
               当然,还可以通过给定的广义表建立二叉树等。可见,建立二叉树的方法很多,只要考生掌握了二叉树的递归定义的本质和输入形式就可以方便地建立二叉树。
               哈夫曼树的建立和哈夫曼编码的构造
               1)哈夫曼树的基本概念
               .路径:由从树中一个节点到另一个节点之间的分支构成两节点之间的路径。
               .路径长度:路径上的分支数目。
               .树的路径长度:从树根到每一个节点的路径长度之和。
               .节点的带权路径长度:从节点到根之间的路径长度与节点上权的乘积WkLk
               .树的带权路径长度:树中所有带权叶子节点的路径长度之和。
               .哈夫曼树:假设有n个数值{W1W2,…,Wn},试构造一棵有n个叶子节点的二叉树,节点带权为W1,带权路径长度WPL最小的二叉树称哈夫曼树。
               下图给定的两棵二叉树,它们的带权路径长度分别为:
               
               二叉树
               (1)WPL=7*2+5*2+2*2+4*2=36。
               (2)WPL=7*1+5*2+2*3+4*3=35。
               2)哈夫曼树的构造
               哈夫曼树的构造算法如下。
               (1)根据给定的n个数值{W1,W2, …,Wn}构成n棵二叉树的集合F={T1,T2, …,Tn},其中每棵二叉树Ti中只有一个带权为Wi的根节点,左右子树均空。
               (2)在F中选取两棵根节点的数值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根节点的数值为其左右子树上根节点的数值之和。
               (3)在F中删除这两棵树,同时将新得到的二叉树加入F中。
               (4)重复步骤(2)、(3),直到F只含一棵树为止。
               3)哈夫曼编码
               哈夫曼编码的设计思想是:若要设计长短不等的编码,则必须是任一个字符的编码都不是另一个字符的编码的前缀,这种编码称作前缀编码。利用二叉树来设计二进制的前缀编码,设计长度最短的二进制前缀编码,以n种字符出现的频率作为权,由此得到的二进制前缀编码为哈夫曼编码。
               如何利用树型结构求解集合的幂
               求集合{1, 2, …,n}的幂集是一个经典的问题。解决这个问题的最典型做法就是递归调用,传统的做法这里不再讨论。
               如何利用树型结构这个参照系来设计求集合{1, 2, …,n}的幂集算法是我们讨论的重点。对于给定的集合{1,2,3,4},按幂集集合中的元素个数和字典次序建立的树如下图所示。
               
               集合{1, 2, 3, 4}的幂集树型示意图
               为保持集合中元素的字典次序,可采用两种方法来求集合{1, 2, 3, 4}的幂集集合,其一是采用前序遍历树;其二是按层次遍历树。特别要注意的是在设计求集合的幂集时并不建立真正的树,而是在考生的心中建立这样一个虚拟的树,并以这棵树为参照系。下面给出这两种方法的算法。
               方法1:前序遍历虚拟树。
               
               方法2:按层次遍历虚拟树。
               
               可见,灵活地应用树型结构及其遍历操作的思路,能有效地解决实际应用问题。
               二叉树的应用
               二叉树运算是数据结构的重要内容,为加深对二叉树内容的理解,这里给出一些应用实例。为方便描述,二叉树的顺序存储结构用一维数组R表示,而二叉链表的节点存储结构定义如下:
               
               (1)以二叉链表为存储结构,写一个算法用括号形式(key, LT, RT)打印二叉树,其中key是根节点数据,LT和RT分别是括号形式的左右子树。并且要求:空树不打印任何信息,一个节点x的树打印形式是x,而不应是(X,)的形式。相应的算法如下:
               
               (2)建立哈夫曼树和哈夫曼编码。
               建立哈夫曼树和哈夫曼编码的代码如下:
               
               (3)将已知二叉树改建为中序线序树。
               将已知二叉树改建为中序线序树算法的主要思路是:对二叉树进行中序遍历,若当前被访问节点的左子节点指针为空,则让它指向当前节点的前驱节点;若其前驱节点的右子节点指针为空,则让它指向当前节点。相应的算法如下:
               
 
       语法分析阶段的主要任务
        语法分析的任务是:在词法分析的基础上,根据语言的语法规则(文法规则),把单词符号串分解成各类语法单位,如"短语""子句""句子"("语句")、"程序段"和"程序"。通过语法分解,确定整个输入串是否构成一个语法上正确的"程序"。在语法分析这一阶段的工作中,所依循的是语言的语法规则。
 
       二叉树
               二叉树的定义
               二叉树(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 /
 
第33题    在手机中做本题