数据结构编程题.pdfVIP

数据结构编程题--第1页

第4周二叉树基础

4-2:文本二叉树

总时间限制:1000ms内存限制:65536kB

描述

如上图，一棵每个节点都是一个字母，且字母互不相同的二叉树，可以用以下若干行文

本表示:

A

-B

--*

--C

-D

--E

*

F

在这若干行文本中：

1)每个字母代表一个节点。该字母在文本中是第几行，就称该节点的行号是几。根在第1

行

2)每个字母左边的-字符的个数代表该结点在树中的层次（树根位于第0层）

3)若某第i层的非根节点在文本中位于第n行，则其父节点必然是第i-1层的节点中，

数据结构编程题--第1页

数据结构编程题--第2页

行号小于n,且行号与n的差最小的那个

4)若某文本中位于第n行的节点(层次是i)有两个子节点，则第n+1行就是其左子节点，

右子节点是n+1行以下第一个层次为i+1的节点

5)若某第i层的节点在文本中位于第n行，且其没有左子节点而有右子节点，那么它的下

一行就是i+1个-字符再加上一个*

给出一棵树的文本表示法，要求输出该数的前序、后序、中序遍历结果

输入

第一行是树的数目n

接下来是n棵树，每棵树以0结尾。0不是树的一部分

每棵树不超过100个节点

输出

对每棵树，分三行先后输出其前序、后序、中序遍历结果

两棵树之间以空行分隔

样例输入

2

A

-B

--*

--C

-D

--E

*

F

0

A

-B

-C

0

数据结构编程题--第2页

数据结构编程题--第3页

样例输出

ABCDEF

CBFEDA

BCAEFD

ABC

BCA

BAC

4-3:由中根序列和后根序列重建二叉树

总时间限制:500ms内存限制:65535kB

描述

我们知道如何按照三种深度优先次序来周游一棵二叉树，来得到中根序列、前根序列和后根

序列。反过来，如果给定二叉树的中根序列和后根序列，或者给定中根序列和前根序列，可

以重建一二叉树。本题输入一棵二叉树的中根序列和后根序列，要求在内存中重建二叉树，

最后输出这棵二叉树的前根序列。

用不同的整数来唯一标识二叉树的每一个结点，下面的二叉树

中根序列是953267

后根序列932675

前根序列596732

输入

两行。第一行是二叉树的中根序列，第二行是后根序列。每个数字表示的结点之间用空

数据结构编程题--第3页

数据结构编程题--第4页

格隔开。结点数字范围0～65535。暂不必考虑不合理的输入数据。

输出

一行。由输入中的中根序列和后根序列重建的二叉树的前根序列。每个数字表示的结点

之间用空格隔开。

样例输入

953267

932675

样例输出

596732

4-4:表达式·表达式树·表达式求值

总时间限制:1000ms内存限制:65535kB

描述