對(duì)于如下一顆樹，如何判斷它是否符合搜索二叉樹

image.png

首先，要明白搜索二叉樹的特點(diǎn)：
1，根節(jié)點(diǎn)的所有左節(jié)點(diǎn)的值小于根節(jié)點(diǎn)，根節(jié)點(diǎn)的所有右節(jié)點(diǎn)的值大于根節(jié)點(diǎn)；
2，所有左子樹、右子樹分別是一顆搜索二叉樹。
根據(jù)以上特點(diǎn)，我們可以得出這樣一個(gè)結(jié)論：對(duì)搜索二叉樹
進(jìn)行中序遍歷，遍歷后得到的序列一定是有序的。利用對(duì)二叉樹的中序遍歷，可以有如下三種方法判斷一顆二叉樹是否是搜索二叉樹。
這里先定義一下二叉樹的節(jié)點(diǎn)的結(jié)構(gòu)：

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

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

方法一：通過(guò)對(duì)二叉樹中序遍歷，并將遍歷后的序列保存到一個(gè)數(shù)組中，通過(guò)判斷數(shù)組是否有序，從而得出該二叉樹是否是搜索二叉樹，代碼如下：

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);
    }
}

方法二：這個(gè)方法是在方法一的基礎(chǔ)之上，方法一是將遍歷的序列保存到一個(gè)數(shù)組中，那么是否可以不保存這樣一個(gè)數(shù)組呢，我們知道，判斷是一個(gè)數(shù)組是否有序，是通過(guò)對(duì)比數(shù)組中前后兩個(gè)相鄰的元素的大小，所以方法的思路是通過(guò)一個(gè)變量記錄上一個(gè)訪問(wèn)的節(jié)點(diǎn)的值，通過(guò)將該值與當(dāng)前要訪問(wèn)的節(jié)點(diǎn)的值進(jìn)行對(duì)比，從而判斷是否是二叉樹。代碼如下：

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;
        }
    }
}

方法三：該方法也是是基于中序遍歷實(shí)現(xiàn)，由于每個(gè)節(jié)點(diǎn)的值必定滿足一定的范圍，通過(guò)對(duì)每個(gè)節(jié)點(diǎn)設(shè)置合理的范圍值來(lái)判斷是否是二叉搜索書，代碼如下：

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函數(shù)中的測(cè)試代碼如下：

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 << "http://*****************************方法一************************************//" << 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 << "http://*****************************方法二************************************//" << 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 << "http://*****************************方法三************************************//" << 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();
}

測(cè)試結(jié)果如下：

image.png