数据结构综合练习题(3)

6、 (1) 求树三棵树的先根序列和后根序列； (2) 求森林先序序列和中序序列； （3）把森林转换为对应的二叉树。

E H

C

B A D G I K J

7、把下面的二叉树转换为相应的森林。

五、算法设计题

1．假设正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’ 和‘ababab’则不是回文。试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。

2.试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。且树中结点的关键字均不同。

3. 编写按层次顺序（同一层自左至右）遍历二叉树的算法。（6分） 4.编写递归算法，计算二叉树中叶子结点的数目。 5.设有一组初始记录关键字序列（K1，K2，?，Kn），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。