A tree data structure has a root, branches, and leaves. The difference between a tree in nature and a tree in computer science is that a tree data structure has its root at the top and its leaves on the bottom.
So lets just look at a few common examples below we can see a tree as a classification tree from biology.
So we have biological classification of some animals so a pretty simple example where we can learn about the properties of trees so this example demonstrates that trees have a hierarchy and their structure and layers where more general things are near the top and more specific things are near the bottom.
A second property of trees is that all of the children of one node are independent of the child of the another node. Third property is that each leaf node is unique.
Another example of a tree structure that you probably use every day is a file system. In a file system, directories, or folders, are structured as a tree
The above image is an example of this where you basically have just a small part of the UNIX file system as a hierarchy and just like that biological classification tree you can follow a path from the root to any directory and that path will uniquely identify that sub directory.
Another important property of tree also derived from that hierarchy is that you can move entire sections of a tree called subtrees to a different position in the tree without affecting the lower levels of the hierarchy. for example you can take the bin node from the above tree and move to the any node in the tree and its important to note that its not going to effect any of the children that are at the same level.
Another example is a webpage, for those familiar with HTML. it is also has a similar structure
We have mentioned some terms such as nodes, children, parents now we will go over some common vocabulary terms they should know when discussing trees.
Node:
A node is a fundamental part of a tree. It can have a name, which we call the “Key”. A node may also have additional information we call this additional information the “payload”. while the payload information is not central to many tree algorithms, it is often critical in applications that make use of trees.
Edge:
An edge is another fundamental part of a tree. An edge connects two nodes to show that there is a relationship between them. Every node(except the root) is connected by exactly one incoming edge from another node. Each node may have several outgoing edges
Root:
The root of the tree is the only node in the tree that has no incoming edges.
Path:
A path is an ordered list of nodes that are connected by edges.
Form example in biological classification tree
Mammal → Carnivora → Felidae → Felis is a path.
Children:
The set of nodes that have incoming edges from the same node to are said to be the children of that node.
Parent:
A node is the parent of all the nodes it connects to with outgoing edges.
Sibling:
Nodes in the tree that are children of the same parent are said to be siblings.
Sub Tree:
A subtree is a set of nodes and edges comprised of a parent and all the descendants of that parent.
Leaf Node:
A leaf node is a node that has no children.
Level:
The level of any node is the number of edges on the path from the root node to n.
Height:
The height of a tree is equal to the maximum level of any node in the tree.
Full Definition of a Tree
A tree consists of a set of nodes and a set of edges that connect pairs of nodes. A tree has the following properties:
- One node of the tree is designated as the root node.
- Every node n, except the root node, is connected by an edge from exactly one other node P, where P is the parent of n.
- A unique path traverses from the root to each node.
- If each node in the tree has a maximum of two children, we say that the tree is a binary tree.
Recursive Definition of a Tree
A tree is either empty or consists of a root and zero or more subtrees, each of which is also a tree.
The root of each subtree is connected to the root of the parent tree by an edge.
In the next blog we will implement tree data structure in python using lists and classes.
