# Tree structure

## Definition

A tree structure is a graph which comprises a set of points, called nodes, connected by branches (represented by solid lines). Any given pair of nodes contained in the same tree will be related by one of two different types of relation, namely either by dominance or by precedence. A tree structure has only one top node.

```(i)	        A
/ \
B	  C
|   /\
|  D  E
|  |  |
b	 d  e
```

## Example

In (i) the node labelled A dominates all other nodes. Node C dominates D, but D does not dominate C. Node B precedes nodes D and E, as well as the nodes d and e. The nodes at the bottom of each complete tree structure (here in lower case) are called terminal nodes; other nodes are called non-terminal. Each node carries a label. Non-terminal nodes carry category labels; A, B, C, D, E in figure (i). Terminal nodes, unless they are empty, are labelled with an appropriate lexical item (a word), viz. b, d, e in (i). Nodes can be branching or non-branching. For example, node C in (i) branches into nodes D and E; node B is a non-branching node. Tree structures are used as a representation of the constituent structure of natural language expressions. Thus, the tree in (ii) represents the structure of the sentence John may eat apples.

```(ii)	       IP
/|
NP	I'
|	|\
|	I VP
John	|  |
|  V'
may |\
V \
|  NP
eat |
|
apples
```

The nodes with the category labels NP, IP, VP, I', V', V, I in (ii) are non-terminal nodes. The words John, may, eat, apples are the terminal nodes in this tree. Originally, tree structures were generated by phrase structure rules, or by the transformational rules that map the distinct levels of representation ( d-structure, s-structure, LF, PF) onto each other. All binary relations (such as c-command, sisterhood) are defined over trees. Another term for tree structure is Phrase marker or P-marker (although a Phrase marker is formally different from a tree).