Data Strucutre-Linked List
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.
As a Data Type
- t: v [t, …, t[k]] -(A tree t consists of a value v and a list of other trees.)
- f: [t, …, 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
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