Arrays, linked lists, stacks and queues are used to represent linear and tabular data. These structures are not suitable for representing hierarchical data.
In hierarchical data we have
- ancestors, descendants
- superiors, subordinates, etc
Business Corporate Structure
Federal Government Structure
Introduction to Trees
- Fundamental data storage structures used in programming
- Combine advantages of ordered arrays and linked lists
- Searching can be made as fast as in ordered arrays
- Insertion and deletion as fast as in linked lists
- Consists of nodes connected by edges
- Nodes often represent entities (complex objects) such as people, car parts etc.
- Edges between the nodes represent the way the nodes are related.
- It's easy for a program to get from one node to another if there is a line connecting them.
- The only way to get from node to node is to follow a path along the edges.
- Root: node without parent (A)
- Internal node: node with at least one child (A, B, C, F)
- External node: (a.k.a. leaf) node without children (E, I, J, K, G, H, D)
- Ancestors of a node: parent, grandparent, grand-grandparent, etc
- Depth of a node: number of ancestors
- Height of a tree: maximum depth of any node (3)
- Descendant of a node: child, grandchild, grand-grandchild, etc
- Degree of an element: no. of children it has
- Subtree: tree consisting of a node and its descendants
- Path: traversal from node to node along the edges that results in a sequence
- Root: node at the top of the tree
- Parent: any node, except root has exactly one edge running upward to another node. The node above it is called parent.
- Child: any node may have one or more lines running downward to other nodes. Nodes below are children.
- Leaf: a node that has no children
- Subtree: any node can be considered to be the root of a subtree, which consists of its children and its children's children and so on.
- Visiting: a node is visited when program control arrives at the node, usually for processing.
- Traversing: to traverse a tree means to visit all the nodes in some specified order.
- Levels: the level of a particular node refers to how many generations the node is from the root. Root is assumed to be level 0.
- Keys: key value is used to search for the item or perform other operations on it.
- Every node in a binary tree can have at most two children.
- The two children of each node are called the left child and right child corresponding to their positions.
- A node can have only a left child or only a right child or it can have no children at all.
A binary tree is a tree with the following properties:
- Each internal node has at most two children (exactly two for proper binary trees)
- The children of a node are an ordered pair
- We call the children of an internal node left child and right cild
Alternative recursive definition: a binary tree is either
- a tree consisting of a single node, or
- a tree whose root has an ordered pair of children, each of which is a binary tree
- arithmetic expressions
- decision processes
Arithmetic Expression Tree
Binary tree associated with an arithmetic expression
- internal nodes: operators
- external nodes: operands
- Example: arithmetic expression tree for the expression (2 * (a – 1) + (3 * b))
Compiling arithmetic expressions
We can represent an arithmetic expression such as
(A + B) * (C + D) * 2 – X / Y as a binary tree, in which the leaves are constants or variables and the nodes are operations:
Properties of Proper Binary Trees
- n number of nodes
- e number of external nodes
- i number of internal nodes
- h height
- e = i +1
- n =2e -1
- h <= i
- h <= (n -1)/2
- e <= 2h