7.11 binary tree data structure (3.2.03)

7.11.1 Bruno Guerrieri

I am trying to use Maple to set up binary trees and work with them. Is there a person in the community who has already written the standard procedures for insertion, deletion of nodes etc.. and would not mind sharing?

In addition, although I do not want to go the route of C, C++, etc, the concept of pointer is especially useful when dealing with trees. Since speed is not paramount to what I am doing, is there a "construct", (be it artificial and to be refined in future versions), a definition-like "thing" that someone could set up at the beginning of the worksheet that would allow one to almost translate word for word certain C procedures such as node deletion in a tree, exploiting the recursive nature of the situation.

The construct would, of course, be the equivalent of the pointer concept p->left or p->right as one can see in the following example:

Here is an example of a C procedure

void printtree(node *p) 
{ if (p !=3D NULL) 
    { printtree(p->left); 
      printf(........,p->count, p->pword); 
      printtree(p->right); 
    } 
}
 

I tried the network package to plot some binary trees and that was like to trying to ride a wild bronco.

7.11.2 Carl Devore (15.2.03)

See ?examples,binarytree

| Since speed is not paramount to what I am doing, ...

Yes, they are called modules (see ?module), and as far as I can tell, there is no performance penalty for using them. The Maple syntax would be p:-left rather than C's p->left.

A skeleton would be

BinaryTree:= proc(...) 
   module() 
      export left, right, ...; 
      left:= ...; 
      right:= ...; 
      ... 
   end module 
end proc; 
 
p:= BinaryTree(...); 
p:-left;
 

Note that a procedure that returns a module (as above) is far more powerful than just a module.

7.11.3 Dr Francis J. Wright (16.2.03)

You might like to take a look at C:\Program Files\Maple8\ examples\binarytree.mws (although the full pathname of this file may be different on your installation), which illustrates insertion, deletion, etc. There is also a similar implementation of linked lists described in the Maple 8 Advanced Programming Guide. These both use inert functions to represent nodes.

Alternatively, if you represented a node as a module (or record) then you could use the object-oriented syntax node:-left etc, which is as close as I think you will get to C pointer syntax.