Question

判别二叉树是否为二叉排序树的完整程序

c语言版

Answer 1

给你一个测试代码。
VC下通过。

#include <stdio.h>
#include <stdlib.h>

struct node
{
node(int i):data(i),left(NULL),right(NULL){}
int data;
node *left; //左孩子结点
node *right; //右孩子结点
void inorder(node *root) //中序遍历，符合升序输出
{
if(root!=NULL)
{
inorder(root->left);
printf("%d ",root->data);
inorder(root->right);
}
}
void insert(node *&ptr,int item) //在排序树中插入元素
{
if(ptr==NULL)
ptr=new node(item);
else if(item<ptr->data)
insert(ptr->left,item);
else insert(ptr->right,item);
}
};

int main()
{
int t=rand(),i=0;
node *x=new node(t);
printf("待排序数列为：%d ",t);
for(;i<9;i++)
{
t=rand();
printf("%d ",t);
x->insert(x,t);
}
printf("\n树升序输出:");
x->inorder(x);
printf("\n");
return 0;
}

很明显地看到，当一棵二叉排序树以中序遍历输出时，是输出一组递增序列。
这样就可以知道，只要当一棵树的中序遍历输出不是一组递增序列时，就可判断其不是一棵二叉排序树。