1 struct node { 2 int val; 3 node *left; 4 node *right; 5 node *parent; 6 node() : val(0), left(NULL), right(NULL) { } 7 node(int v) : val(v), left(NULL), right(NULL) { } 8 }; 9 10 node* insert(int n, node *root) { 11 if (root == NULL) { 12 root = new node(n); 13 return root; 14 } 15 if (n < root->val) { 16 if (root->left == NULL) { 17 root->left = new node(n); 18 return root->left; 19 } 20 else return insert(n, root->left); 21 } 22 if (n > root->val) { 23 if (root->right == NULL) { 24 root->right = new node(n); 25 return root->right; 26 } 27 else return insert(n, root->right); 28 } 29 } 30 31 Variation: How would you find the sucessor of a node? 32 33 node* findSuccessor(node* n) { 34 if (n == NULL) return NULL; 35 if (n->right) { 36 n = n->right; 37 while (n->left) n = n->left; 38 return n; 39 } 40 else { 41 while (n->parent && n->parent->right == n) n = n->parent; 42 if (n->parent == NULL) return NULL; 43 return n->parent; 44 } 45 }
find successor in a BST,布布扣,bubuko.com
原文:http://www.cnblogs.com/yingzhongwen/p/3595500.html