【题目】试写一个判别给定二叉树是否为二叉排序树的算法。
【来源】长沙铁道学院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 版》)。