What is a tree? • Tree is a discrete structure that represents hierarchical relationships between individual elements or nodes. • A tree in which a parent has no more than two children is called a binary tree. • A tree is a connected graph containing no cycles. • A forest is a graph containing no cycles. Note that this means that a connected forest is a tree. Tree and its Properties • A Tree is a connected acyclic undirected graph. • There is a unique path between every pair of vertices in G. • A tree with N number of vertices contains (N−1) number of edges. • The vertex which is of 0 degree is called root of the tree. • The vertex which is of 1 degree is called leaf node of the tree and the degree of an internal node is at least 2. Tree and its Properties • A graph T is a tree if and only if between every pair of distinct vertices of T there is a unique path. • A graph F is a forest if and only if between any pair of vertices in F there is at most one path. Example − tree • The following is an example of a tree − Forest Graphs containing no simple circuits that are not connected, but each connected component is a tree. Theorem
An undirected graph is a tree if and only if
there is a unique simple path between any two of its vertices. Rooted Trees
Once a vertex of a tree has been designated
as the root of the tree, it is possible to assign direction to each of the edges. Rooted Trees
g a e f e c b b d a d
c g f root node a internal vertex parent of g b c
d e f g
leaf siblings h i a
b c
d e f g
h i ancestors of h and i a
b c
d e f g
subtree with b as its
h i root subtree with c as its root m-ary trees A rooted tree is called an m-ary tree if every internal vertex has no more than m children. The tree is called a full m-ary tree if every internal vertex has exactly m children. An m-ary tree with m=2 is called a binary tree. Ordered Rooted Tree
An ordered rooted tree is a rooted tree
where the children of each internal vertex are ordered. Ordered trees are drawn so that the children of each internal vertex are shown in order from left to right. Properties of Trees
A tree with n vertices has n-1 edges.
Properties of Trees A full m-ary tree with i internal vertices contains n = mi+1 vertices. Properties of Trees
A full m-ary tree with
(i) n vertices has i = (n-1)/m internal vertices and l = [(m-1)n+1]/m leaves. (ii) i internal vertices has n = mi + 1 vertices and l = (m-1)i + 1 leaves. (iii) l leaves has n = (ml - 1)/(m-1) vertices and i = (l-1)/(m-1) internal vertices. Properties of Trees
The level of a vertex v in a rooted tree is
the length of the unique path from the root to this vertex.
level 2
level 4 Properties of Trees
The height of a rooted tree is the maximum
of the levels of vertices. Properties of Trees
A rooted m-ary tree of height h is called
balanced if all leaves are at levels h or h-1. Properties of Trees
There are at most mh leaves in an m-ary
tree of height h. Level of a vertex and tree height Let T be a rooted tree: The level l(v) of a vertex v is the length of the simple path from v to the root of the tree The height h of a rooted tree T is the maximum of all level numbers of its vertices: h = max { l(v) } v V(T)
Example: the tree on the right has height 3 Rooted Tree • A rooted tree G is a connected acyclic graph with a special node that is called the root of the tree and every edge directly or indirectly originates from the root. • An ordered rooted tree is a rooted tree where the children of each internal vertex are ordered. Rooted Tree • If every internal vertex of a rooted tree has not more than m children, it is called an m-ary tree. • If every internal vertex of a rooted tree has exactly m children, it is called a full m-ary tree. • If m=2, the rooted tree is called a binary tree. Rooted Tree Terminology Parent Ancestor Child Descendant Siblings Terminal vertices Internal vertices Subtrees Internal and external vertices
An internal vertex is a vertex that has at least one child A terminal vertex is a vertex that has no children The tree in the example has 4 internal vertices and 4 terminal vertices Subtrees A subtree of a tree T is a tree T' such that V(T') V(T) and E(T') E(T) Characterization of trees Theorem If T is a graph with n vertices, the following are equivalent: a) T is a tree b) T is connected and acyclic (“acyclic” = having no cycles) c) T is connected and has n-1 edges d) T is acyclic and has n-1 edges 7.3 Spanning trees
Given a graph G, a tree T is a
spanning tree of G if: T is a subgraph of G and T contains all the vertices of G 7.5 Binary trees A binary tree is a tree where each vertex has zero, one or two children Full binary tree
A full binary tree is a
binary tree in which each vertex has two or no children. Full binary tree If T is a full binary tree with k internal vertices, then T has k + 1 terminal vertices and the total number of vertices is 2k + 1. Example: there are k = 4 internal vertices (a, b, c and f) and 5 terminal vertices (d, e, g, h and i) for a total of 9 vertices. Height and terminal vertices If a binary tree of height h has t terminal vertices, then lg t < h, where lg is logarithm base 2. Equivalently, t < 2h. Example, h = 4 and t = 7. Then: t = 7 < 16 = 24 = 2h A case of equality
If all t terminal vertices of a full
binary tree T have the same level h = height of T, then t = 2h . Example: The height is h = 3, and the number of terminal vertices is t = 8 t = 8 = 2 3 = 2h Binary search trees Data are associated to Example: each vertex "Computers are an important Order data alphabetically, technological tool" so that for each vertex v, data to the left of v are less than data in v and data to the right of v are greater than data in v Binary Search Tree Binary Search tree is a binary tree which satisfies the following property −
•X in left sub-tree of vertex V,
Value(X)≤Value(V)
•Y in right sub-tree of vertex V,
Value(Y)≥Value(V)V,Value(Y)≥Value(V) Binary Search Tree So, the value of all the vertices of the left sub-tree of an internal node V are less than or equal to V and the value of all the vertices of the right sub-tree of the internal node V are greater than or equal to V. The number of links from the root node to the deepest node is the height of the Binary Search Tree. Example-Binary Search Tree Algorithm to search for a key in BST BST_Search(x, k) if ( x = NIL or k = Value[x] ) return x; if ( k < Value[x]) return BST_Search (left[x], k); else return BST_Search (right[x], k) Binary Tree Traversal • Traversal is the process of visiting every node once • Visiting a node entails doing some processing at that node, but when describing a traversal strategy, we need not concern ourselves with what that processing is Binary Tree Traversal Techniques
• Three recursive techniques for binary tree traversal
• In each technique, the left subtree is traversed recursively, the right subtree is traversed recursively, and the root is visited • What distinguishes the techniques from one another is the order of those 3 tasks Preoder, Inorder, Postorder • In Preorder, the root Preorder Traversal: 1. Visit the root is visited before (pre) 2. Traverse left subtree the subtrees traversals 3. Traverse right subtree • In Inorder, the root is Inorder Traversal: visited in-between left 1. Traverse left subtree 2. Visit the root and right subtree traversal 3. Traverse right subtree • In Preorder, the root Postorder Traversal: is visited after (pre) 1. Traverse left subtree 2. Traverse right subtree the subtrees traversals 3. Visit the root Illustrations for Traversals • Assume: visiting a node 1 is printing its label 3 7 • Preorder: 5 8 9 1 3 5 4 6 7 8 9 10 11 12 10 4 6 • Inorder: 4 5 6 3 1 8 7 9 11 10 12 11 12 • Postorder: 4 6 5 3 8 11 12 10 9 7 1 Illustrations for Traversals (Contd.) • Assume: visiting a node 15 8 20 is printing its data • Preorder: 15 8 2 6 3 7 2 11 27 11 10 12 14 20 27 22 30 6 10 12 22 30 • Inorder: 2 3 6 7 8 10 11 3 7 14 12 14 15 20 22 27 30 • Postorder: 3 7 6 2 10 14 12 11 8 22 30 27 20 15 Code for the Traversal Techniques void preOrder(Tree *tree){ • The code for visit if (tree->isEmpty( )) return; visit(tree->getRoot( )); is up to you to preOrder(tree->getLeftSubtree()); preOrder(tree->getRightSubtree()); provide, depending } void inOrder(Tree *tree){ on the application if (tree->isEmpty( )) return; • A typical example inOrder(tree->getLeftSubtree( )); visit(tree->getRoot( )); for visit(…) is to inOrder(tree->getRightSubtree( )); } print out the data void postOrder(Tree *tree){ if (tree->isEmpty( )) return; part of its input postOrder(tree->getLeftSubtree( )); postOrder(tree->getRightSubtree( )); node visit(tree->getRoot( )); } Introduction • A free tree is a connected undirected graph without a cycle. – Note: This definition of tree is different from the one of a rooted tree • In a free tree |E| = |V| - 1 • Example of a free tree:
• A forest is an acyclic directed or undirected graph consisting of two or more trees
• The trees in a directed forest are rooted trees
• The trees in an undirected forest are free trees
48 Introduction (Cont’d) • To traverse a graph is to systematically visit and process each node in the graph exactly once.
• There are two common graph traversal algorithms that are applicable to both directed and undirected graphs : • BreadthFirst Traversal (BFS) • DepthFirst Traversal (DFS) • PreOrder DepthFirst Traversal • PostOrder DepthFirst Traversal
• Since some graph algorithms do not require all vertices of a graph to be
visited we will define both BFS and DFS such that it is possible the algorithms: • starting from any vertex, will not visit all vertices if the traversed graph is disconnected • starting from a particular vertex, may not visit all vertices if the traversed graph is weakly connected
• We shall define General traversal algorithms [dfsAllVertices and bfsAllVertices] that will visit each vertex of a graph G in those algorithms that require each vertex to be visited. These algorithms will be of the form: for(i = 0; i < numberOfVertices; i++){ if(vertexi is not visited) dfsPreOrder(G, vertexi); // or dfsPostOrder(G, vertexi) or bsf(G, vertexi) } 49 Introduction (Cont’d) The BFS and DFS traversal of a graph G is not unique. A traversal depends both on the starting vertex, and on the order of traversing the adjacent vertices of each node.
50 Breadth-First Traversal Algorithm • In this method, After visiting a vertex v, we must visit all its adjacent vertices w1, w2, w3, ..., before going down to the next level to visit vertices adjacent to w1 etc.
• The method can be implemented using a queue.
• A boolean array is used to ensure that a vertex is enqueued only once. enqueue the starting vertex while(queue is not empty){ dequeue a vertex v from the queue; visit v. enqueue vertices adjacent to v that were never enqueued; } • Note: Adjacent vertices can be enqueued in any order; but to obtain a unique traversal, we will enqueue them in alphabetical order.
• A BFS traversal of a graph results in a breadth-first tree or in a forest of such
trees 51 Example • Breadth-first traversal using a queue. Queue front
BFS-tree:
B D E
Order of C G
Traversal A B D E C G F H I Queue rear
F H
Note: The BFS-tree for undirected graph is a free tree
52 Depth-First Traversal Algorithm • A DFS starting at a vertex v first visits v, then some neighbour w of v, then some neighbour x of w that has not been visited before, etc. When it gets stuck, the DFS backtracks until it finds the first vertex that still has a neighbour that has not been visited before. It continues with this neighbour until it has to backtrack again. Eventually, it will visit all vertices reachable from v
• Must keep track of vertices already visited to avoid cycles.
• The method can be implemented using recursion or iteration. • The iterative preorder depth-first algorithm is:
push the starting vertex onto the stack
while(stack is not empty){ pop a vertex off the stack, call it v if v is not already visited, visit it push vertices adjacent to v, not visited, onto the stack }
• Note: Adjacent vertices can be pushed in any order; but to obtain a unique traversal, we will push them in reverse alphabetical order.
• A DFS traversal of a graph results in a depth-first tree or in a forest of such
trees
53 Example • Depth-first traversal using an explicit stack.
The Preorder Depth First Tree:
Order of A B C F E G D H I Stack Traversal
Note: The DFS-tree for undirected graph is a free tree
