【题目】试写一个判别给定二叉树是否为二叉排序树的算法。
【来源】长沙铁道学院98年第五（1）题（12’）
【解答】
typedef struct node{
char data;
struct node *left,*right;
}*T;
issorttree(T)
{
initqueue(Q); // 初始化队列
inqueue(Q,T); // 树根结点进队列
while(!empty(Q)){
outqueue(Q,T);
if(T->data>T->left->data&&T->data<T->right->data){
if(T->left)inqueue(Q,T->left);
if(T->right)inqueue(Q,T->right);
}
else if(T->left||T->right)return 1; // 不符合二叉排序树的特征，则终止并返回‘ 1 ’
}
return 0; // 是二叉排序树，则返回 ‘0’
}
【分析】注意队列的运用，其他如图的广度搜索（教材《清华 C 版》）。