🚀 go-pugleaf

Jos A. Horsmeier <jos@and.nl> wrote in article
<352B713D.A246A05E@and.nl>...
> Ben Smith wrote:
> 
> > I'm trying to make a Binary Tree program in Visual Basic5
> > I'm a bit stuck on writting the code to find the predecessor and
> > successor of a node. And also on the Preorder and Postorder traversal.
> > I can do the inorder code, if they are similar.
> > Is there anyone who could help me?
> 
> Have you considered adding a 'parent' pointer to each node, i.e.
> instead of the regular 'left' and 'right' pointers, add a third
> pointer 'parent' pointing the parent, to each node. All your 
> problems will vanish instantly ... Note that the parent pointer
> of the root of the tree points nowhere (NULL).
> 
> Here's some pseudo code; I assume the elementary functions
> 'parent(node)', 'left(node)' and 'right(node)' already present.
> 
> first(node ) {				/* find smallest element in the tree */
> 
> 	if (node != NULL) 		/* is tree not empty?)
> 		while (left(node))	/* move down leftwards */
> 			root= left(node);
> 	
> 	return (node ;
> } 
> 
> last(node ) {				/* find largest element in the tree */
> 
> 	if (node  != NULL)		/* is tree not emty? */  
> 		while (right(node ))	/* move down rightwards */
> 			root= right(node);
> 
> 	return root;
> }
> 
> next(node) {				/* find next element in the tree */
> 
> 	pointer r= right(node);
> 
> 	if (r != NULL)			/* right child present? */
> 		r= first(r);		/* take smallest kid from this subtree */
> 	else {
> 		r= parent(node);	/* we're the 'right' kid, move up */
> 		while (r != NULL && node == right(r)) {
> 			node= r;
> 			r   = parent(r);
> 		}
> 	}	
> 	return r;
> }
> 
> prev(node) {				/* find previous element in th tree */
> 
> 	pointer l= left(node);
> 
> 	if (l != NULL)			/* left child present? */
> 		l= last(l);		/* take largest kid from this subtree */
> 	else {
> 		l= parent(node);	/* we're the 'left' kid, move up */
> 		while (l != NULL && node == left(l)) {
> 			node= l;
> 			l   = parent(l);
> 		}
> 	}
> 	return l;
> }
> 
> Inorder traversal is a walk over the tree with all elements in order,
> so:
> 
> inorder(tree) {
> 
> 	pointer node;
> 
> 	node= first(tree);			/* leftmost element */
> 
> 	while (node != NULL) {			/* travese the tree */	
> 		process(node);			/* do something with 'node' */
> 		node= next(node);
> 	}
> }
> 
> Preorder and postorder walks can be easily implemented using recursion:
> 
> preorder(tree) {
> 
> 	if (tree) {
> 		process(tree);			/* do something with 'node' */
> 		preorder(left(tree));		/* similar with left tree */	
> 		preorder(right(tree));		/* and the right tree */
> 	}
> }
> 
> postorder(tree) {
> 
> 	if (tree) {
> 		postorder(left(tree));		/* similar with left tree */	
> 		postorder(right(tree));		/* and the right tree */
> 		process(tree);			/* do something with 'node' */
> 	}
> }
> 
> kind regards,
> 
> Jos aka jos@and.nl
>