判断搜索二叉树

概念

一棵树所有结点的左节点小于父节点，右节点大于父节点，则为搜索二叉树。

迭代方法

• 中序遍历二叉树，如果总是升序则是搜索二叉树。
• 如果存在降序，那肯定不是搜索二叉树。

Coding

checkTreeOrder()方法

bool checkTreeOrder(Node* head) {stack<Node*> st;int n = INT_MIN;while (!st.empty() || head != NULL) {if (head != NULL) {st.push(head);head = head->left;} else {Node* node = st.top();if (node->value > n) {n = node->value;} else {return false;}st.pop();head = node->right;}}return true;}

最终代码

//迭代方法#include <iostream>#include <stack>#include <vector>using namespace std;// 判断搜索二叉树struct Node {int value;Node* left;Node* right;Node(int v): value(v), left(NULL), right(NULL) {};};bool checkTreeOrder(Node* head) {stack<Node*> st;int n = INT_MIN;while (!st.empty() || head != NULL) {if (head != NULL) {st.push(head);head = head->left;} else {Node* node = st.top();if (node->value > n) {n = node->value;} else {return false;}st.pop();head = node->right;}}return true;}int main() {Node* head = new Node(5);Node* v3 = new Node(3);Node* v7 = new Node(7);Node* v2 = new Node(2);Node* v4 = new Node(4);Node* v6 = new Node(6);Node* v8 = new Node(8);Node* v1 = new Node(1);head->left = v3;head->right = v7;head->left->left = v2;head->left->right = v4;head->left->left->left = v1;head->right->left = v6;head->right->right = v8;if (checkTreeOrder(head)) {cout << "true!" << endl;} else {cout << "false!" << endl;}}

递归方法

1.第一种实现方式(动态调整)

//递归方法int preValue = INT_MIN;inline bool isBST(Node* head) {if (head == NULL) {return true;}//如果左树不是，直接剪枝bool isLeftBST = isBST(head->left);if (isLeftBST == false) {return false;}//**********************//设置布尔属性if (head->value <= preValue) {return false;} else {preValue = head->value;}return isBST(head->right);}

2.第二种实现方式-存入数组依次遍历(更加简单，不过效率略低)

vector<int> BSTelements;inline void isBST_easy(Node* head) {if (head == NULL) return;isBST_easy(head->left);BSTelements.push_back(head->value);isBST_easy(head->right);}inline bool checkArrayOrder(Node* head) {isBST_easy(head);for (int i = 1; i < BSTelements.size(); i++) {if (BSTelements[i] < BSTelements[i-1]) {return false;}}return true;}