学步园

#include "stdafx.h"
#include <iostream>
#include <algorithm>
using namespace std;


struct Node
{
	int element;
	Node *left;
	Node *right;

	Node(int ele = 0, Node *l = NULL, Node *r = NULL)
		:element(ele), left(l), right(r){}
};


//插入结点
void InsertNode(Node *&root, int element)
{
	if (NULL == root)
		root = new Node(element);
	else if (element < root->element)
		InsertNode(root->left, element);
	else
		InsertNode(root->right, element);
}

//创建二叉搜索树
void CreateBinSearchTree(Node *&root, int arr[], int n)
{
	for (int i = 0; i < n; ++i)
		InsertNode(root, arr[i]);
}

//中序输出
void MiddlePrint(Node *root)
{
	if (NULL != root)
	{
		MiddlePrint(root->left);
		cout<<root->element<<" ";
		MiddlePrint(root->right);
	}
}

//函数功能：二叉排序树的判定算法
/*
	算法思想：根据二叉树的特点“其中序遍历序列为有序序列”，对二叉树进行中序遍历，
	同时检查当前结点与其中前驱关键字值的大小。
*/
//中序遍历过程中判定给定的二叉树是否为二叉排序树，入是返会true，否则返回false
//pre指向中序前驱结点，初值为NULL
bool IsBinSearchTree(Node *root, Node *pre)
{
	if(NULL == root) //空二叉树也是二叉排序树
		return true;

	//左子树为二叉排序树且关键字值大于前驱结点关键字值，
	//此时，是否为二叉树却决于右子树
	if (IsBinSearchTree(root->left, pre))   
	{
		if ( (NULL == pre) || (pre->element < root->element))
		{
			pre = root;
			return IsBinSearchTree(root->right, pre);
		}
	}
	else
		return false;
}

int main()
{
	const int N = 10;
	int arr[N];
	for (int i = 0; i < N; i++)
		arr[i] = i + 1;
	
	random_shuffle(arr, arr + N);

	Node *root = NULL;
	CreateBinSearchTree(root, arr, N);                                                                                                                                                                                                                                                                                                             

	MiddlePrint(root);
	cout<<endl;
	
	Node *pre = NULL;
	if (IsBinSearchTree(root, pre))
		cout<<"是二叉排序树！"<<endl;
}