C/C++:二叉排序树.rar(含完整注释)

设二叉排序树的二叉链表存储结构的类型定义如下： 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