編寫判斷給定二叉樹是否為二叉排序樹的函數

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的專欄”