问答题

某二叉树的后序遍历序列为：，φ，φ，A，φ，φ，E，φ，φ，C D，B，其中φ表示空格符，代表空二叉树。能否以此序列作为输入创建二叉树如不能，请说明理由；如能够，试画出对应二叉树。【华中科技大学2007三、23(8分)】

答案：正确答案：二叉树后序遍历序列是“左一右一根”，序列的最后一个结点是根，根结点的左面是右子树的根，若无右子树，则该位置应为...

你可能感兴趣的试题

分别给出满足下列条件的二叉树。(1)前序和中序遍历结果相同；(2)前序和中序遍历结果不相同而是相反；(3)中序和后序遍历结果相同；(4)前序和后序遍历结果相同。【四川大学2004】【烟台大学2007四、2(8分)】

答案：正确答案：空二叉树满足题目要求，若二叉树非空，则 (1)前序和中序遍历结果相同的二叉树是任一结点无左子女； (2)前序和...

设某二叉树的前序遍历序列为：ABCDEFGHI，中序遍历序列为：BCAEDGHFI。(1)试画出该二叉树。(2)写出由给定的二叉树的前序遍历序列和中序遍历序列构造出该二叉树的算法。(3)设具有4个结点的二叉树的前序遍历序列为abcd；S为长度等于4的由a，b，c，d排列构成的字符序列，若任取S作为上述算法的中序遍历序列，试问是否一定能构造出相应的二叉树，为什么试列出具有4个结点二叉树的全部形态及相应的中序遍历序列。【浙江大学1997六(15分)】

答案：正确答案：(1)
(2)设二叉树的前序遍历序列为P1，P2，…，Pm，中序遍历序列为S1，S2，…，Sm。因为...

(1)试找出满足下列条件的二叉树：1)先序序列与后序序列相同2)中序序列与后序序列相同3)先序序列与中序序列相同4)中序序列与层次遍历序列相同(2)已知一棵二叉树的中序序列和后序序列分别为DBEAFIHCG和DEBHIFGCA，画出这棵二叉树。【东北大学1999六(4分)】【东南大学2000一、4(6分)】

答案：正确答案：(1)先序遍历二叉树的顺序是“根一左子树一右子树”，中序遍历“左子树一根一右子树”，后序遍历顺序是“左子树一右...

已知一棵二叉树的对称序和后序序列如下：对称序：GLDHBEIACJFK 后序：LGHDIEBJKFCA(1)(2分)给出这棵二叉树；(2)(2分)转换为对应的森林；(3)(4分)画出该森林的带右链的先根次序表示法；
(4)(4分)画出该森林带度数的后根次序表示法；(5)(4分)在带度数的后根次序表示法中，不包含指针，但仍能完全反映树的结构。写出以结点x为根的子树在后根次序序列中的前驱的求法。(用语言叙述，不用写算法。)【山东大学1998八(16分)】

答案：正确答案：(1)
(2)
(3)森林的带右链的前序表示法。在前序序列中，任何结点的子树的所有结点都直...

假设一棵二叉树的前序序列为ABCD，它的中序序列可能是DABC吗【石油大学1998一、1(5分)】

答案：正确答案：不能。因DABC并不是ABCD的合法出栈序列

设一棵二叉树的先序、中序遍历序列分别为先序遍历序列：AB D，C E G H 中序遍历序列：B FDAG E H C(1)画出这棵二叉树。(2)画出这棵二叉树的后序线索树。(3)将这棵二叉树转换成对应的树(或森林)。【南京航空航天大学1997二(10分)】

答案：正确答案：(1)

(2)

(3)

将下列由三棵树组成的森林转换为二叉树(只要求给出转换结果)。
【南京航空航天大学1998一(10分)】

答案：正确答案：森林转为二叉树的三步： (1)连线(将兄弟结点相连，各树的根看作兄弟)； (2)切线(保留最左边子女为独生子女...

已知一棵二叉树的后序遍历序列为EICBGAHDF，同时知道该二叉树的中序遍历序列为CEIFGBADH，试画出该二叉树。【重庆大学2000二、2】

答案：正确答案：

已知一棵二叉树T的诸结点在先根次序下的排列为:ABCEDFGHI，在中根次序下的排列为：ECBDFAHIG，画出此树形状并给出其后根序列。【吉林大学2007二、3(3分)】

答案：正确答案：二叉树略，其后根序列为：ECFDBIHGA。

在某二叉树上进行前序、中序遍历后发现该二叉树的前序序列的最后一个结点和中序序列的最后一个结点是同一个结点。请问该结点具有何种性质为什么【上海交通大学2003五(10分)】

答案：正确答案：该结点应是二叉树最右边的叶子结点。因为前序遍历是“根一左一右”，中序遍历是“左一根一右”，只有在最右边的叶子处...

在二叉树上进行前序遍历时，结点A在结点B之前，而在进行后序遍历时，结点A在结点B之后，那么结点A是结点B的祖先，对吗为什么【上海交通大学2003六(10分)】

答案：正确答案：正确。前序遍历是“根一左一右”，后序遍历是“左一右一根”。前序遍历结点A在结点B之前，说明结点A到B有路径，或...

某二叉树的后序遍历序列为：，φ，φ，A，φ，φ，E，φ，φ，C D，B，其中φ表示空格符，代表空二叉树。能否以此序列作为输入创建二叉树如不能，请说明理由；如能够，试画出对应二叉树。【华中科技大学2007三、23(8分)】

答案：正确答案：二叉树后序遍历序列是“左一右一根”，序列的最后一个结点是根，根结点的左面是右子树的根，若无右子树，则该位置应为...

输入带空二叉树信息(O)的前序遍历序列：A，G，φ，φ，B，φ，C，D，E，φ，E φ，φ，φ，E φ，φ建立一棵二又树，其中φ表示空格符，代表空二叉树，试画出该二叉树。【华中科技大学2006三、1(6分)】

答案：正确答案：二叉树前序遍历序列的第一个结点是根(如是空树，则用φ表示)，接着应是左子树的根，如无左子树，则用φ表示，φ的后...

已知某二叉树的每个结点，要么其左、右子树皆为空，要么其左、右子树皆不空。又知该二叉树的前序序列为(即先根次序)：J、F、D、B、A、C、E、H、X、I、K；后序序列为(即后根次序)：A、C、B、E、D、X、，、H、F、K、，。请给出该二叉树的中序序列(即中根次序)。【上海交通大学2001二(8分)】

答案：正确答案：二叉树中序序列ABCDEFXHIJK。

假设一棵二叉树的层次序列为ABCDEFGHIJ，中序序列DBGEHJACIF。请画出这棵二叉树。【武汉大学2000三、1】【东南大学2000一、1(6分)】【大连理工大学2005二、3(20／4分)】【中国海洋大学2007一、5(8分)】

答案：正确答案：按层次遍历，第一个结点(若树不空)为根，该结点在中序序列中把序列分成左右两部分——左子树和右子树。若左子树不空...

已知一个森林的先序序列和后序序列如下，请构造出该森林。先序序列：ABCDEFGHIJKLMNO后序序列：CDEBFHIJGAMLONK【合肥工业大学2000四、1(5分)】

答案：正确答案：森林的先序序列和后序序列对应其转换的二叉树的先序序列和中序序列，应先据此构造二叉树，再构造出森林。

画出同时满足下列两条件的两棵不同的二叉树。(1)按先根序遍历二叉树顺序为ABCDE。(2)高度为5其对应的树(森林)的高度最大为4。【东北大学1 997一、3(5分)】

答案：正确答案：

用一维数组存放的一棵完全二叉树；ABCDEFGHIJKL。请写出后序遍历该二叉树的访问结点序列。【西安电子科技大学1999计算机应用一、6(5分)】

答案：正确答案：HIDJKEBLFGCA。完全二叉树的结点按从上到下、从左到右的顺序，在数组中存储。结点t和其双亲、子女的编号...

一棵二叉树的先序、中序和后序序列如下，其中有部分未标出，试构造出该二叉树。先序序列为：一一CDE—GHI一K中序序列为：C B一一F A—J K I G后序序列为：一E F D B—J I H—A【电子科技大学2001三、1(5分)】【厦门大学2002七、l(6分)】

答案：正确答案：本题解答原理及方法如下：首先掌握先序遍历是“根一左一右”中序遍历是“左一根一右”，后序遍历是“左一右一根”。从...

M叉树的前序和后序遍历分别与由它转换成的二叉树的哪种遍历相对应【中国人民大学2000一、2(4分)】

答案：正确答案：M叉树的前序和后序遍历分别与它转换成的二叉树的先序和中序遍历对应。

设树形T在后根次序下的结点排列和各结点相应的次数如下：后根次序：BDEFCGJKILHA次数：000030002024请画出T的树形结构图。【吉林大学2001一、2(4分)】

答案：正确答案：树的遍历序列中，各子树的结点在一起，不会漏掉一个结点，也不会有其他子树的结点插到里面。后根遍历序列中最后一个是...

已知二叉树采用二叉链表方式存放，要求返回二叉树T的后序序列中的第一个结点的指针，是否可不用递归且不用栈来完成请简述原因。【西北大学2001三、6】

答案：正确答案：后序遍历的顺序是“左一右一根”。因此，二叉树最左(或右)下的叶子结点是后序遍历的第一个结点。下面的语句段说明了...

对于二叉树T的两个结点N1和N2，我们应该选择树T结点的前序、中序和后序中哪两个序列来判断结点n1必定是结点n2的祖先，并给出判断的方法。不需证明判断方法的正确性。【复旦大学1999五(10分)】

答案：正确答案：采用前序和后序两个序列来判断二叉树上结点n1必定是结点n2的祖先。在前序序列中某结点的祖先都排在其前。若结点n...

在二又树的前序遍历和中序遍历的递归算法中，最后一个递归调用语句在调用时所保留的参数有什么作用如何清除最后这个递归语句【北京邮电大学1994三(8分)】

答案：正确答案：最后一个递归调用语句所保留的参数没有意义。这类递归因其在算法最后，通常被称为“尾递归”，可不用栈且将其(递归)...

在二叉树的Llink-一Rlink存储表示中，引入“线索”的好处是什么【山东大学1999六、1(2分)】

答案：正确答案：在二叉链表表示的二叉树中，查找结点的左右子女非常方便，但查找后继就不太方便。引入线索的目的主要是便于查找结点的...

按下面要求解下图中二叉树的有关问题：(1)对此二叉树进行后序后继线索化；(2)将此二叉树变换为森林；(3)用后根序遍历该森林，写出遍历后的结点序列。
【北京邮电大学1996五(10分)】

答案：正确答案：给二叉树加上线索有如下要点：首先要明确是什么序的线索化，即前序、中序还是后序线索化；二是前驱、后继还是全线索化...

一棵h层、度为k(k＞1)的树，最多有多少个结点【北京科技大学2006】

答案：正确答案：1+k ¹ +k ² +k ³ +…+k ^h-1 =(k ^h 一1)／(k-1)

设二叉树BT的存储结构如下：
其中BT为树根结点的指针，其值为6，Lchild，Rchild分别为结点的左、右孩子指针域，data为结点的数据域。试完成下列各题：画出二叉树BT的逻辑结构；

答案：正确答案：

请说明是否存在这样的二叉树，即它可以实现后序线索树进行后序遍历时不使用栈；而对前序线索树进行前序遍历时，又有什么样的二叉树可不使用栈。【西安电子科技大学1996二、l(5分)】

答案：正确答案：后序线索树中结点的后继，要么是其右线索(当结点的rtag=1时)，要么是其双亲结点右子树中最左下的叶子结点。所...

设二叉树BT的存储结构如下：
其中BT为树根结点的指针，其值为6，Lchild，Rchild分别为结点的左、右孩子指针域，data为结点的数据域。试完成下列各题：写出按前序、中序、后序遍历该二叉树所得到的结点序列；

答案：正确答案：前序序列：A BC E D F H G I J 中序序列：E C B H F D J I G A 后序序列：E...

一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为多少【西安电子科技大学2000计算机应用一、2(5分)】

答案：正确答案：左右子树均不空的二叉树先序线索化后，空指针域为1个(最后访问结点的右链为空)。

在前序线索树上，要找出结点p的直接后继结点，请写出相关语句。结点结构为(1tag，lc，data， nag，rc)。【西北大学2000二、6(5分)】

答案：正确答案：if(p一>ltag==0)return(p一>lchild)；／／左子女不空，左子女为直接后继结点else...

对于后序线索二叉树，怎样查找任意结点的直接后继；对于中序线索二叉树，怎样查找任意结点的直接前驱【西北工业大学1998一、4(4分)】

答案：正确答案：后序线索树中结点的后继求法如下：根结点无后继；当结点的rtag=1时，其右线索指向后继；当结点的nag=0且是...

设二叉树BT的存储结构如下：
其中BT为树根结点的指针，其值为6，Lchild，Rchild分别为结点的左、右孩子指针域，data为结点的数据域。试完成下列各题：画出二叉树的后序线索树。【中国矿业大学2000二(15分)】

答案：正确答案：

将下列树的孩子兄弟链表改为后根遍历全线索链表。【清华大学1994二(10分)】

答案：正确答案：树的后根遍历(对应二叉树的中序遍历)全线索链表

若森林共有n个结点和b条边(b

答案：正确答案：森林的n个结点开始可看作是n个连通分量，加入一条边将减少一个连通分量。因为树可以定义为无环的图，故加入b条边将...

给定权W1，W2，…，Wm。说明怎样来构造一个具有最小的加权路径长度的k叉树。试对于权1，4，9，16，25，36，49，64，8l，100来构造最优的三叉树，并给出其最小加权路径长度。【北方交通大学1994四(12分)】

答案：正确答案：首先确定是否需加“虚权值”(即权值为0)，对m个权值，建尼叉树，若(m—1)％(k-1)=0，则不需要加“虚权...