如何判断一颗二叉树是二叉搜索树（BSTree）

对于如下一颗树，如何判断它是否符合搜索二叉树

image.png

首先，要明白搜索二叉树的特点：
1，根节点的所有左节点的值小于根节点，根节点的所有右节点的值大于根节点；
2，所有左子树、右子树分别是一颗搜索二叉树。
根据以上特点，我们可以得出这样一个结论：对搜索二叉树
进行中序遍历，遍历后得到的序列一定是有序的。利用对二叉树的中序遍历，可以有如下三种方法判断一颗二叉树是否是搜索二叉树。
这里先定义一下二叉树的节点的结构：

typedef struct Node {
    int value;
    struct Node *pLeftChild;
    struct Node *pRightChild;

public:
    Node(const int &value) {
        this->value = value;
        pLeftChild = NULL;
        pRightChild = NULL;
    }
} *PNode;

方法一：通过对二叉树中序遍历，并将遍历后的序列保存到一个数组中，通过判断数组是否有序，从而得出该二叉树是否是搜索二叉树，代码如下：

void inOrder(PNode node, vector<int>& vec) {

    if (node == NULL) {
        return;
    }

    if (node->pLeftChild != NULL) {
        inOrder(node->pLeftChild, vec);
    }

    cout << "push back into vector: value = " <<node->value<< endl;
    vec.push_back(node->value);

    if (node->pRightChild != NULL) {
        inOrder(node->pRightChild, vec);
    }
}

方法二：这个方法是在方法一的基础之上，方法一是将遍历的序列保存到一个数组中，那么是否可以不保存这样一个数组呢，我们知道，判断是一个数组是否有序，是通过对比数组中前后两个相邻的元素的大小，所以方法的思路是通过一个变量记录上一个访问的节点的值，通过将该值与当前要访问的节点的值进行对比，从而判断是否是二叉树。代码如下：

bool inOrder2(PNode node, int& lastValue) {
    if (node == NULL) {
        return true;
    }

    if (node->pLeftChild != NULL) {
        if (!inOrder2(node->pLeftChild, lastValue)) {
            return false;
        }
    }
    
    cout << "lastValue: " << lastValue << "   curValue: " << node->value << endl;

    if (lastValue > node->value) {
        return false;
    }

    lastValue = node->value;

    if (node->pRightChild != NULL) {
        if (!inOrder2(node->pRightChild, lastValue)) {

            return false;
        }
    }
}

方法三：该方法也是是基于中序遍历实现，由于每个节点的值必定满足一定的范围，通过对每个节点设置合理的范围值来判断是否是二叉搜索书，代码如下：

bool inOrder3(PNode node, int& minValue, int& maxValue) {
    if (node == NULL) {
        return true;
    }


    if (node->pLeftChild != NULL) {
        if (!inOrder3(node->pLeftChild, minValue, node->value)) {
            return false;
        }
    }

    cout << "minValue: " << minValue << " nowValue: " << node->value << " maxValue: " << maxValue << endl;

    if (node->value < minValue || node->value > maxValue)
    {
        return false;
    }

    if (!inOrder3(node->pRightChild, node->value, maxValue)) {
        return false;
    }
}

main函数中的测试代码如下：

void main() {
    PNode node1 = new Node(5);

    PNode node2 = new Node(3);
    node1->pLeftChild = node2;

    PNode node3 = new Node(8);
    node1->pRightChild = node3;

    PNode node4 = new Node(2);
    
    PNode node5 = new Node(4);

    node2->pLeftChild = node4;

    node2->pRightChild = node5;

    PNode node6 = new Node(1);

    PNode node7 = new Node(6);
    node3->pLeftChild = node7;

    PNode node8 = new Node(7);
    node7->pRightChild = node8;

    PNode node9 = new Node(9);
    node3->pRightChild = node9;

    node4->pLeftChild = node6;

    vector<int> vec;
    cout << "//*****************************方法一************************************//" << endl;
    inOrder1(node1, vec);

    bool isBSTree = true;
    for (int i = 0; i < vec.size() - 1; i++) {
        if (vec[i] < vec[i+1]) {
            isBSTree = false;
            break;
        }
    }

    if (isBSTree)
    {
        cout << "This is a BSTree" << endl;
    }
    else
    {
        cout << "This is not a BSTree" << endl;
    }

    cout << endl;
    cout << "//*****************************方法二************************************//" << endl;
    int lastValue = MIN_INT;
    if (inOrder2(node1, lastValue))
    {
        cout << "This is a BSTree" << endl;
    }
    else
    {
        cout << "This is not a BSTree" << endl;
    }
    cout << endl;
    cout << "//*****************************方法三************************************//" << endl;

    int minValue = MIN_INT;
    int maxValue = MAX_INT;

    if (inOrder3(node1, minValue, maxValue))
    {
        cout << "This is a BSTree" << endl;
    }
    else
    {
        cout << "This is not a BSTree" << endl;
    }

    getchar();
}

测试结果如下：

image.png