Data Structure Binary Search Tree: Inorder Successor in Binary Search Tree

 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 node* leftmost(node *n) {
33     if (n == NULL) return NULL;
34     while (n->left) n = n->left;
35     return n;
36 }
37 
38 node* findSuccessor(node* n) {
39     if (n == NULL) return NULL;
40     if (!n->parent || n->right) return leftmost(n->right);
41     else {
42         while (n->parent && n->parent->right == n) n = n->parent; 
43         return n->parent;
44     }
45 }

下面是没有parent的代码

 1 node *minvalue(node *root) {
 2     while (root->left) root = root->left;
 3     return root;
 4 }
 5 
 6 node* successor(node *root, node *n) {
 7     if (n->right) return minvalue(n->right);
 8     node *succ = NULL;
 9     while (root) {
10         if (n->data < root->data) {
11             succ = root;
12             root = root->left;
13         }
14         else if (n->data > root->data) root = root->right;
15         else break;
16     }
17     return succ;
18 }