view plaincopy to clipboardprint #include "stdafx.h"
#include
#include
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<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<
Node *pre = NULL;
if (IsBinSearchTree(root, pre))
cout<<"是二叉排序树！"< }

作者“wangyangkobe的专栏”