判断binary tree是不是binary search tree
如何定义递归式?
int is_bst(struct node *n, int min, int max);
子树n的所有节点必需满足min < n->data < max,不断更新min/max值,以深度优先搜索形式从上往下传递
/* Copyleft: Ming Lin <minggr@gmail.com> */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <limits.h> #include “tree.h” int check_bst(struct node *n, int min, int max) { if (!n) return 1; if (n->data < min || n->data > max) return 0; return check_bst(n->left, min, n->data) && check_bst(n->right, n->data, max); } int main() { struct node *root; int postorder[] = {5,7,6,9,11,10,8}; root = construct_bst(postorder, 0, 6); printf(“check_bst: %d\n”, check_bst(root, INT_MIN, INT_MAX)); root->data = 100; printf(“check_bst: %d\n”, check_bst(root, INT_MIN, INT_MAX)); return 0; }