首页 > 其他 > 详细

find successor in a BST

时间:2014-03-12 10:09:16      阅读:387      评论:0      收藏:0      [点我收藏+]
bubuko.com,布布扣
 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 }
bubuko.com,布布扣

find successor in a BST,布布扣,bubuko.com

find successor in a BST

原文:http://www.cnblogs.com/yingzhongwen/p/3595500.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!