HI,
What are Successors and predecessors of a node in binary trees?
thnx
HI,
What are Successors and predecessors of a node in binary trees?
thnx
A
|\
BC
I'm not quite sure about these English terms. But if I am correct than A is the predecessor of B and C. And B and C are the successors of A.
mmmmmmm but isn't this the same name as to 'parents' and 'children'? A is parent of B and C and B and C are children or child nodes of A ?
B and C are the children of A, so A is parent of B and C. I guess successor and predecessor are just other words for child and parent.
I am not sure about that, after looking at the code in my book. Maybe u can have a look at the this:
The function finds the successor of *x.Code:/* A binary tree node with parent pointer. */ struct pbin_node { int data; struct pbin_node *left; struct pbin_node *right; struct pbin_node *parent; }; /* A binary tree. */ struct pbin_tree { struct pbin_node *root; int count; }; /* Returns the next node in in-order in the tree after X, or NULL if X is the greatest node in the tree. */ static struct pbin_node *successor(struct pbin_node *x) { struct pbin_node *y; assert(x != NULL); if (x->right != NULL) { y = x->right; while (y->left != NULL) y = y->left; } else { y = x->parent; while (y != NULL && x == y->right) { x = y; y = y->parent; } } return y; }
thnx
Found these definitions:
If a node N has a right subtree: The successor of N will be the smallest node in the right subtree of N.
If a node N has no right subtree: If N is a left child, then the next node visited by the in-order traversal will be the parent of N. But what if N is a right child? Then the in-order traversal will keep going up the tree until it gets to a node for which the previous node is a left child.