一、假设二叉排序树以后继线索链表作存储结构，编写出该二叉排序树中所有大于a且小于b的关键字的算法。
答：
本实现要求输出二叉排序树中的所有大于a且小于b。由二叉排序树的相关知识我们很容易知道：用递归的方式进行遍历，遇到大于a且小于b的关键字时即输出。
该算法实现的伪代码如下：
|
/* 函数名称：输出二叉排序树中所有大于a且小于b的关键字 函数传入参数：树的根节点T，比较参数a和b 函数返回值：void */ void searchPrint(BinTree T,int m,int n) { if(T) { Search(T -> lchild, a, b); if(T -> data > a && T -> data < b) { printf("%d ",T -> data); } SearchPrint(T -> rchild, a, b); } } |
算法分析：由分析可以知道，该算法通过递归的方式对二叉排序树进行遍历并成功输出大于a且小于b的关键字。这是解决该类问题的较好方法。
二、试写一算法，将两棵二叉排序树合并为一棵二叉排序树。
答：
由分析容易知道，实现二叉排序的合并，我们需要构造两个函数一个是根据插入值与此时遍历到的值进行判断后从而采取相应操作的insert函数。另一个则是合并两个二叉排序树的递归操作函数。在相应的操作步骤进行判定，从而使得最终得到的仍然为二叉排序树。
该算法实现的伪代码如下：
|
/* 函数名称：二叉排序树的插入 传入参数：二叉排序树其中一个根节点，对应关键字 返回值：void */ void Insert(BinTree *T,int key) { if(!(*T)) { //如果为空树，直接操作 (*T) = (BinTree)malloc(sizeof(BinNode)); (*T) -> data = key; (*T) -> lchild = (*T) -> rchild = NULL; return; } //根据大小进行操作 if(key == (*T)->data) return; if(key > (*T) -> data) Insert(&((*T) -> rchild), key); else Insert(&((*T) -> lchild), key); } /* 函数名称：合并二叉排序树 传入参数：两棵二叉排序树 返回值：void */ void MergeBST(BinTree T1,BinTree T2) { if(T2 ！= NULL) { InsertBST(T1, T2 -> lchild); Insert(&T1, T2 -> data); //递归操作 InsertBST(T1, T2->rchild); } } |
算法分析：本算法由二叉排序树进行设计，根据大小判断进行相应的操作，采用递归方法使得代码简洁明了。综上，这是解决该类问题的较好的算法。