Data Type-List

Data Strucutre-Linked List

**Tree:**

As a *data type*, a tree has a value and children, and the children are themselves trees; the value and children of the tree are interpreted as the value of the root node and the subtrees of the children of the root node.

As a *data structure,* a linked tree is a group of nodes, where each node has a value and a list of references to other nodes (its children). This data structure actually defines a directed graph,[a] because it may have loops or several references to the same node, just as a (corrupt) linked list may have a loop. Thus there is also the requirement that no two references point to the same node (that each node has at most a single parent, and in fact exactly one parent, except for the root), and a tree that violates this is “corrupt”.

*a tree is always non-empty, but a reference to a tree may be null.*

**Recursive**

As a Data Type

- t: v [t[1], …, t[k]] -(A tree t consists of a value v and a list of other trees.)
- f: [t[1], …, t[[k]]

t: v f -(a tree can be defined in terms of a forest (a list of trees), where a tree consists of a value and a forest (the subtrees of its children):

As a data structure

n: v [&n[1], …, &n[k]] -((A node n consists of a value v and a list of other references to other nodes.)
**Terminology**

node:

An **internal node **(also known as an inner node, inode for short, or branch node) is any node of a tree that has *child nodes*.

**External node** (also known as an outer node, leaf node, or terminal node) is any node that *does not have child nodes*.

**height** of a node is the length of the longest downward path to a leaf from that node. The height of the root is the height of the tree

The **depth** of a node is the length of the path to its root (i.e., its root path

Ref:

http://mathworld.wolfram.com/RootedTree.html

http://en.wikipedia.org/wiki/Tree_(data_structure)

### Like this:

Like Loading...

## About Lekshmana Perumal M

Proud be an Indian, passion to teaching & learn, love mathematics, enjoy with family & friends, job to code. Care about child education, Indian culture