编写判断给定二叉树是否为二叉排序树的函数

view plaincopy to clipboardprint?#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;
}

作者“wangyangkobe的专栏”

补充：软件开发 , C语言 ,