本文共 3157 字，大约阅读时间需要 10 分钟。

题面：

L2-004 这是二叉搜索树吗？ （25 分）

一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点，

• 其左子树中所有结点的键值小于该结点的键值；
• 其右子树中所有结点的键值大于等于该结点的键值；
• 其左右子树都是二叉搜索树。

所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。

给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。

输入格式：

输入的第一行给出正整数 N（≤1000）。随后一行给出 N 个整数键值，其间以空格分隔。

输出格式：

如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果，则首先在一行中输出 YES ，然后在下一行输出该树后序遍历的结果。数字间有 1 个空格，一行的首尾不得有多余空格。若答案是否，则输出 NO。

输入样例 1：

78 6 5 7 10 8 11

输出样例 1：

YES5 7 6 8 11 10 8

输入样例 2：

78 10 11 8 6 7 5

输出样例 2：

YES11 8 10 7 5 6 8

输入样例 3：

78 6 8 5 10 9 11

输出样例 3：

NO

这个最主要的就是建树，在我的上一篇文章中 在这里我详细的介绍了二叉搜索树的一些操作，对于这道题你应该首先判断这棵树是二叉搜索树，还是其的镜像。相对于二叉搜索树来说，镜像就是其性质的相反，也就是说右结点小于其根节点，每个左节点大于其根节点。这就构成了两种建树的方法。我的解题思路是首先建立两棵树，然后把他们的先序遍历分别存储到一个数组中，然后与输入的数组对比，看是其中之一还是都不符合，然后输出对应的后序遍历。

代码如下：

int n;int a[maxn], b[maxn],d[maxn];typedef struct node{	int date;	struct node*left;	struct node*right;}Node; typedef struct{	Node *root;}Tree;void insert(Tree* tree, int value){	Node* node = (Node *)malloc(sizeof(Node));	node->date = value;	node->left = NULL;	node->right = NULL;	if(tree->root == NULL){		tree->root = node;	}else{		Node* temp = tree->root;		while(temp != NULL){			if(value < temp->date){				if(temp->left == NULL){					temp -> left = node;					return ;				}else{					temp = temp->left;				}			}else{				if(temp->right == NULL){					temp -> right = node;					return ;				}else{					temp = temp->right;				}			}		} 	}}void insert2(Tree *tree, int value){	Node *node = (Node*)malloc(sizeof(Node));	node->date = value;	node->left = NULL;	node->right = NULL;	if(tree->root == NULL){		tree->root = node;	}else{		Node *temp = tree->root;		while(temp!=NULL){			if(value < temp->date){				if(temp->right == NULL){					temp->right = node;					return ;				}else{					temp = temp->right;				}			}else{				if(temp->left == NULL){					temp->left = node;					return ;				}else{					temp = temp->left;				}			}		}	}}int ans = 0;void preorder(Node *node){	if(node != NULL){		a[ans]  = node->date;		ans++;		//printf("%d ",node->date);		preorder(node->left);		preorder(node->right);	}} int res = 0;void preorder2(Node *node){	if(node != NULL){		b[res]  = node->date;		res++;		//printf("%d ",node->date);		preorder2(node->left);		preorder2(node->right);	}} int res2 = 0;void postorder(Node *node){	if(node != NULL){		postorder(node->left); 		postorder(node->right);		d[res2] = node->date;		res2++;	}}int main(){	scanf("%d",&n);	int q[maxn];	Tree tree;	tree.root = NULL;	Tree tree2;	tree2.root = NULL;	for(int i = 0; i < n; i++){		scanf("%d",&q[i]);		insert(&tree,ot);	preorder2(tree2.root);	   int flag q[i]);		insert2(&tree2,q[i]);	}	preorder(tree.ro= 0;	for(int i = 0; i < n; i++){		if(a[i] != q[i]){			flag = 1;			break;		}	}	int flag2 = 0;	for(int i = 0; i < n; i++){		if(b[i] != q[i]){			flag2 = 1;			break;		}	}	if(!flag2){		printf("YES\n");		postorder(tree2.root);		for(int i = 0; i < n; i++){			if(i == n-1){				printf("%d\n",d[i]);			}else{				printf("%d ", d[i]);			}		}	}else{		if(!flag){			printf("YES\n");			postorder(tree.root);			for(int i = 0; i < n; i++){				if(i == n-1){					printf("%d\n",d[i]);				}else{					printf("%d ", d[i]);				}			}		}else{			printf("NO\n");		}	}		return 0;}

这应该是比较笨的办法，不过自己主动做出来了一道，数据结构的题还好是很开心。坚持吧，骚年；

转载地址：http://oqpfb.baihongyu.com/