设二叉排序树的二叉链表存储结构的类型定义如下:
typedef struct node{
int data; //用整数表示一个结点的名
struct node *LChild,*RChild; //左右指针域
}BSTNode,*BSTree;
设计算法并编写程序求解以下几个问题。
8
12
14 10
7 3 15
6 2 4 1 5 11 9 13
16
13
(1)键盘输入一个元素序列创建一棵二叉排序树,输出该二叉排序树的中序遍历序列;
例如,若输入 45,24,55,12,37,53,60,23,40,70 则创建的二叉排序树为:
输出结果为:12 23 24 37 40 45 53 55 60 70
(2)在(1)中所得的二叉排序树中插入一个值为 58 的结点,再输出它的中序遍历序列,输出
结果为:12 23 24 37 40 45 53 55 58 60 70
(3)在(1)中所得的二叉排序树中删除值为 45 的结点,再输出它的中序遍历序列,输出结果
为:12 23 24 37 40 53 55 58 60 70
(4)利用(1)中所得的二叉排序树的所有叶子结点构造一个带头结点的单链表 L。要求不能
破坏这棵二叉排序树。所得的单链表 L 如下。
输出该链表各结点的值,输出结果为:23 40 53 70
(5)设计算法将(1)中所得的二叉排序树的左右子树进行交换,由于二叉树是一种递归定义,
所以子树的左右两棵子树也要相交换,依此类推。最后输出所得到的二叉树的中序遍历序列。
例如,经过上述操作后,(1)中所得的二叉排序树变为如下形式。
输出该二叉树的中序序列,结果为:70 60 55 53 45 40 37 24 23 12
(6)设计算法统计并输出(1)中所得的二叉排序树中只有一个孩子结点的结点个数。输出结
果为:3(7)在(1)中所得的二叉排序树中,设计算法并编写程序输出结点 40 的所有祖先结点。输
出结果为:45 24 37