🚀 go-pugleaf

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

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
>