/* Copyleft: Ming Lin <minggr@gmail.com> */ struct node { struct node *left, *right; int data; int distance; }; struct traversal { int *preorder; int *inorder; int pre_s, pre_e; int in_s, in_e; }; #define NUM 8 int search(int *order, int d) { int i; for (i = 0; i < NUM; i++) if (order[i] == d) break; return i; } struct node *create(int d) { struct node *n; n = malloc(sizeof(*n)); n->data = d; return n; } struct node *construct(int preorder[], int inorder[], int pre_s, int pre_e, int in_s, int in_e) { struct node *l_root, *r_root; struct node *n; int l_len, r_len; int i; n = create(preorder[pre_s]); i = search(inorder, preorder[pre_s]); l_len = i - in_s; r_len = in_e - i; if (l_len == 0) l_root = NULL; else l_root = construct(preorder, inorder, pre_s+1, pre_s+l_len, in_s, i-1); if (r_len == 0) r_root = NULL; else r_root = construct(preorder, inorder, pre_s+l_len+1, pre_e, i+1, in_e); n->left = l_root; n->right = r_root; return n; } #define QUEUE_LEN 10 struct node *queue[QUEUE_LEN]; int head = 0, tail = 0; void enqueue(struct node *n) { queue[tail] = n; tail = (tail+1)%QUEUE_LEN; } struct node *dequeue() { struct node *n; n = queue[head]; head = (head+1)%QUEUE_LEN; return n; } void print_tree(struct node *n) { int num1 = 0; int num2 = 0; enqueue(n); num1++; while (n = dequeue()) { printf("%d ", n->data); if (n->left) { enqueue(n->left); num2++; } if (n->right) { enqueue(n->right); num2++; } num1--; if (!num1) { printf("\n"); num1 = num2; num2 = 0; } } } int is_bst(struct node *n, int parent_data, int is_left) { if (!n) return 1; if (is_left==1 && n->data > parent_data) return 0; if (is_left==0 && n->data < parent_data) return 0; return is_bst(n->left, n->data, 1) && is_bst(n->right, n->data, 0); } int first(int postorder[], int s, int e) { int i; for (i = s; i < e; i++) if (postorder[i] > postorder[e]) break; return i; } struct node *construct_bst(int postorder[], int s, int e) { struct node *n; struct node *left, *right; int i; n = create(postorder[e]); i = first(postorder, s, e); if (i == s) left = NULL; else left = construct_bst(postorder, s, i-1); if (i == e) right = NULL; else right = construct_bst(postorder, i, e-1); n->left = left; n->right = right; return n; } int is_max(int postorder[], int s, int e) { int i; for (i = s; i < e; i++) if (postorder[i] > postorder[e]) return 0; return 1; } int is_min(int postorder[], int s, int e) { int i; for (i = s; i < e; i++) if (postorder[i] < postorder[e]) return 0; return 1; } int is_bst_preorder(int postorder[], int s, int e) { int i; int r; i = first(postorder, s, e); if (i == s) r = is_min(postorder, s, e); else r = is_bst_preorder(postorder, s, i-1); if (!r) return 0; if (i == e) r = is_max(postorder, s, e); else r = is_bst_preorder(postorder, i, e-1); if (!r) return 0; return 1; } #if 0 int main() { struct node *root; int preorder[] = {5,20,1,3,4,7,6,8}; int inorder[] = {1,20,3,4,5,6,7,8}; int pre_s, in_s; int pre_e, in_e; int postorder[] = {5,7,6,9,11,10,8}; pre_s = in_s = 0; pre_e = in_e = 7; root = construct(preorder, inorder, pre_s, pre_e, in_s, in_e); //print_tree(root); root = construct_bst(postorder, 0, 6); print_tree(root); printf("is_bst(): %d\n", is_bst(root, -1, -1)); printf("is_bst_preorder(): %d\n", is_bst_preorder(postorder, 0, 6)); return 0; } #endif