数据结构+二叉排序树+哈希表
一、问题一：实现二叉排序树的基本运算算法
编写一个程序，包含二叉排序树的创建、查找和删除算法，并在此基础上编写 程序完成以下功能。
（1）由关键字序列（4, 9, 0, 1, 8, 6, 3, 5, 2, 7）创建一棵二叉排序树 bt 并以括号表示法输出。 （2）判断 bt 是否为一棵二叉排序树。（对二叉排序树来说，其中序遍历序列 为一个递增有序序列，因此，对 给定的二叉树进行中序遍历，如果始终能保持前一个值比后一个值小，则说明 该二叉树是一棵二叉排序树）
（3）采用递归和非递归两种方法查找关键字为 6 的结点，并输出其查找路径。
（4）分别删除 bt 中关键字为 4 和 5 的结点，并输出删除后的二叉排序树。
#include <stdio.h>
#include <stdlib.h>
typedef int KeyType;
typedef int ElemType;
typedef struct node
{ KeyType key; struct node *lchild,*rchild;
}BSTNode; //插入单个数据
BSTNode * InsertBST( BSTNode * bt,KeyType k)
{ if(bt==NULL)//原树为空 { bt=(BSTNode *)malloc(sizeof(BSTNode));//新建根节点 bt bt->key=k;bt->lchild=bt->rchild=NULL; } else if(k<bt->key) bt->lchild=InsertBST(bt->lchild,k);//递归插到左子树 else if(k>bt->key) bt->rchild=InsertBST(bt->rchild,k);//递归插到右子树 return bt;//返回根节点 bt
}
//构建排序二叉树 BSTNode *CreateBST(KeyType a[],int n) { BSTNode *bt=NULL; int i=0; while(i<n)//循环将数值元素全部插入排序二叉树中 { bt=InsertBST(bt,a[i]); i++; }
return bt; } //判断是否为排序二叉树 KeyType predt=-32767; int judgeBST(BSTNode *bt) { int b1, b2; if (bt==NULL) //空树是一棵二叉排序树 return 1; else { b1=judgeBST(bt->lchild); //判断左子树 if(b1==0 || predt>=bt->key) return 0; predt=bt->key; //保存当前节点的关键字 b2=judgeBST (bt->rchild); //判断右子树 return b2; } } // 使用递归查找关键字为 6 的结点，并输出查找路径
void SearchBST(BSTNode *bt,KeyType k)
{ printf(" %d",bt->key); if(bt==NULL || bt->key==k){//递归出口 return ; } if(k<bt->key){ SearchBST(bt->lchild,k);}//左子树递归查找 else SearchBST(bt->rchild,k);//右子树递归查找
} //使用非递归查找关键字为 6 的结点，并输出查找路径 void NRSearchBST(BSTNode *bt,KeyType k)
{ B