September 25th, 2015

Trees

• A tree is a nonlinear structure in which elements are organized
  into a hierarchy.
• A tree is composed of a set of nodes in which elements are stored and edges that connect one node to another.
• Each node is at a particular level in the tree hierarchy.
• The root of the tree is the only node at the top level of the tree.
• There is only one root node in a tree.
• The nodes at lower levels of the tree are the children of nodes at the previous level.
• A node can have only one parent, but a node may have multiple children.
• Nodes that have the same parent are called siblings.
• The root node is the only node in a tree that does not have a parent.
• A node that does not have any children is called a leaf.
• The root is the entry point into a tree structure. We can follow a path through the tree from parent to child.
• We can follow a path through the tree from parent to child.
• A node is the ancestor of another node if it is above it on the path from the root.
• The level of a node is also the length of the path from the root to the node.
• This path length is determined by counting the number of edges that must be followed to get from the root to the node.
• The height of a tree is the length of the longest path from the root to a leaf.

Tree Types

• A tree that has no limit to the number of children a node may have is called a general tree.
• A tree that limits each node to no more than n children is referred to as an n-ary tree.
• A tree in which nodes may have at most two children is called a binary tree.
• A tree is considered to be balanced if all of the leaves of the tree are on the same level or at least within one level of each other.
• A balanced n-ary tree with m elements will have a height of log base n of m.
• A balanced binary tree with n nodes will have a height of log base 2 of n.

• A complete tree is related to the balance of a tree.
• A tree is complete if it is balanced and all of the leaves at the bottom level are on the left side of the tree.
• Another way to define this concept is that a complete binary tree has 2^k nodes at every level k except the last, where the nodes must be leftmost.
• An n-ary tree is considered full if all the leaves of the tree are at the same level and every node is either a leaf or has exactly n children.

(a) and (c)–are complete
Only (c) in Figure full

Homework:
Visit edmodo.com to answer the following questions
1. What is a tree?
2. What is a node?
3. What is the root of the tree?
4. What is a leaf?
5. What is an internal node?
6. Define the height of a tree.
7. Define the level of a node.

Read Tree implementation with arrays.