find next node of a tree(C++)

写的啥啊看不懂。。重新写一个。。
------06/17/13 rewrite-----------
假设不是最大的节点 ，假设是BST
1, node has  a parent field.
node *nextNode(node *root,  int val){
    if(!root) return NULL;
   while(root && root->val != val){
       if(root->val > val) root = root->left;
       else root = root->right;
   }
   if(!root->right) return root->parent;
   root = root->right;
   while(root->left){
       root = root->left;
   }
   return root;
}

2, node doesn't have a parent field.

node *nextNode(node *root,  int val){
   if(!root) return NULL;
   node dummy(0);
   dummy.next = root;
   node *parent = &dummy;
   // find node with value = val
   while(root && root->val != val){
       parent = root;
       if(root->val > val) root = root->left;
       else root = root->right;
   } 
   // find next node
   if(!root->right) return parent;
   root = root->right;
   while(root->left){
       root = root->left;
   }
   return root;
}


------------------old post---------------------------
add a successor pointer for each node in a tree

findsuc(node *root){
  node *parent = NULL;
  node *first,last;
  inorder(root,  first, last);
}

void inorder(node *root,  node *first, node *last){
  if(!root->left) first = root;
  if(!root->right) last = root;
  if(root->left){
   inorder(root->left, first, last);
   last->successor = root;
  }
  if(root->right) {
   inorder(root->right,first,last);
   root->sucessor = first;
   last->successor = NULL;
  }
}
---------------
void solve(Node * r) {
    while (r && r->left) r=r->left;
    Helper(NULL, r);
}

// return the last node of inorder travsal
Node * Helper(Node * prev, Node * r) {
    if (!r) return NULL;
    Node * prev_in_left = Helper(prev, r->left);

    if (prev_in_left) prev = prev_in_left;
    if (prev) prev->successor = r;

    return r->right?Helper(r, r->right):r;
}