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