**DiscreteMath****`****Tree****`**

This package introduces functions for creating, searching and displaying trees represented as nested lists. Since trees are an efficient, basic tool for storing and manipulating data, the functions defined here are used in several other packages.

A tree is a standard data structure used in computer science and elsewhere for organizing information. Information in a tree is stored in nodes, starting with a root node and ending with terminal nodes called leaves. Nodes are linked to other nodes through branches. Leaves are nodes without any branches. The most common type of tree is the binary tree, in which each node has no more than two branches.

In this package, each node has the form

expr,n

,

,

, where expr is the information stored at the node, n is a sequential number assigned to the node, and and are the branches associated with the node. A leaf is represented as

expr,n

,

,

in which the branches are empty lists.

Generating and searching trees.

This loads the package.
In[1]:= **<<DiscreteMath`Tree`**

Here is a simple tree with three nodes. Node number 2 is the root node and contains the item e2. The first branch is the node {{e1,1},{},{}} and the second branch is the node {{e3,3},{},{}}. Both of these nodes are leaves.
In[2]:= **MakeTree[{e1, e2, e3}]**

Out[2]=

Here is a tree with real values at the nodes. The root node contains the value 5.46, which is the median of the list. Other nodes are numbered in increasing order.
In[3]:= **tree = MakeTree[{9.05, 6.48, 8.40, 5.46,**

2.43, 4.46, 2.03}]

Out[3]=

This result indicates that node number 5 contains the largest value less than 6.5. Equivalently, 5 elements in the original list are smaller than 6.5.
In[4]:= **TreeFind[tree, 6.5]**

Out[4]=

A node number of 0 is returned if all of the nodes are larger than the specified value.
In[5]:= **TreeFind[tree, 1.0]**

Out[5]=

Graphical representations of trees.

Graphical representations are very useful for understanding the structure of trees. The function TreePlot produces a graphical representation of trees generated by MakeTree. More generally, most Mathematica expressions can be thought of as trees, with the head of an expression at each node and the arguments of expressions as branches. The function ExprPlot generates a graphical representation of an expression viewed as a tree.

Here is a graphical representation of a tree with 10 nodes.
In[6]:= **TreePlot[MakeTree[Range[10]]]**

Here is a similar plot of an expression containing nested functions.
In[7]:= **ExprPlot[f[g[x, y, z], g[x, y, h[x, y]],**

g[x, y]]]