**Problem:** Given a binary search tree and a value *k*, please find a node in the binary search tree whose value is closest to *k*.

参考：http://codercareer.blogspot.com/2013/03/no-45-closest-node-in-binary-search-tree_2.html

/* Copyleft: Ming Lin <minggr@gmail.com> */ #include <stdio.h> #include "tree.h" int distance(int i, int j) { int d = i - j; if (d < 0) d = -d; return d; } struct node *closest_node(struct node *root, int key) { struct node *n, *closest_n = NULL; int cur_d, min_d; cur_d = min_d = distance(root->data, key); n = root; while (n) { if (key == n->data) return n; cur_d = distance(n->data, key); if (n == root || cur_d < min_d) { min_d = cur_d; closest_n = n; } if (key > n->data) n = n->right; else n = n->left; } return closest_n; } int main() { struct node *root, *closest; int postorder[] = {14, 21, 25, 31, 28, 24, 39, 36, 47, 41, 32}; int n = 11; int key = 29; root = construct_bst(postorder, 0, n-1); closest = closest_node(root, key); printf("key %d, closest %d\n", key, closest->data); return 0; }