Data Structure Tree Basics

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)

    Advertisements

    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
    This entry was posted in data structure, Tree and tagged , , , . Bookmark the permalink.

    Leave a Reply

    Fill in your details below or click an icon to log in:

    WordPress.com Logo

    You are commenting using your WordPress.com account. Log Out / Change )

    Twitter picture

    You are commenting using your Twitter account. Log Out / Change )

    Facebook photo

    You are commenting using your Facebook account. Log Out / Change )

    Google+ photo

    You are commenting using your Google+ account. Log Out / Change )

    Connecting to %s