Binary Search Trees Predesessor & Successor Problems
I am coding an implmentation of a standard BST. This is my first implementation I am having problems with the predesessor and successor parts. Maybe someone could lend me some insight.
I have all the find post, in, pre -order traversals i need the succ & pred & delete. I need the succ for the delete and i'm burned put on this program. I need help. :confused:
Here is what i am trying to accomplish.
pred, moves the pointer to the predecessor of the current node, prints the value that proceeds the string or the line "No Previous"
succ, moves the pointer to the successor of the current node, prints the value that follows the string or the line "No Next"
Code:
//MY GLOBAL STRUCTS FOR THE NODES
struct Wrd {
int wordcounter; // counter
string theword; // the actual word
};
struct TreeNode {
Wrd item; // the data struct
TreeNode *parent; // pointer to the parent
TreeNode *left; // pointer to left subtree
TreeNode *right; // pointer to right subtree
};
TreeNode *root = NULL; // root of the tree & init to NULL
TreeNode* succ(TreeNode *T){
TreeNode *x, *y;
if (T == NULL){
return T;
}
if (T->right != NULL){
return min(T->right);
}
y = T->parent;
while (y != NULL && x == y->right){
x = y;
y = y->parent;
}
return y;
}
//THE CALL
succ(root);