Page 1 1 Trees : Part 1 Section 4.1 (1) Theory and Terminology (2) Preorder, Postorder and Levelorder Traversals Theory and Terminology ?Definition: A tree is a connected graph with no cycles ?Consequences: ?Between any two vertices, there is exactly one unique path A Tree? 1 2 3 4 5 6 8 7 9 10 12 11 A Tree? 1 2 3 4 5 6 8 7 9 10 12 11 Theory and Terminology ?Definition: A rooted tree is a graph G such that: ?G is connected ?G has no cycles ?G has exactly one vertex called the root of the tree Theory and Terminology ?Consequences ?The depth of a vertex v is the length of the unique path from root to v ?G can be arranged so that the root is at the top, its neighboring vertices are vertices of depth 1, and so on… ?The set of all vertices of depth k is called level k of the tree Page 2 1 Trees : Part 1 Section 4.1 (1) Theory and Terminology (2) Preorder, Postorder and Levelorder Traversals Theory and Terminology ?Definition: A tree is a connected graph with no cycles ?Consequences: ?Between any two vertices, there is exactly one unique path A Tree? 1 2 3 4 5 6 8 7 9 10 12 11 A Tree? 1 2 3 4 5 6 8 7 9 10 12 11 Theory and Terminology ?Definition: A rooted tree is a graph G such that: ?G is connected ?G has no cycles ?G has exactly one vertex called the root of the tree Theory and Terminology ?Consequences ?The depth of a vertex v is the length of the unique path from root to v ?G can be arranged so that the root is at the top, its neighboring vertices are vertices of depth 1, and so on… ?The set of all vertices of depth k is called level k of the tree 2 A Rooted Tree 1 2 3 4 5 6 8 7 9 10 12 11 root depth = 1 depth = 0 depth = 3 depth = 2 height = 2 height = 3 height = 0 height = 1 Rooted Tree: Recursive definition ? A graph with N nodes and N - 1 edges ? Graph has ?one root r ?Zero or more non-empty sub-trees, each of whose root is connected to r by an edge. ?Every node except the root has one parent Theory and Terminology ? Definition: A descending path in a rooted tree is a path, whose edges go from a vertex to a deeper vertex 1 2 3 4 5 6 8 7 9 10 12 11 root depth = 1 depth = 0 depth = 3 depth = 2 3 8 12 Theory and Terminology ? Consequences: ?A unique path from the root to any vertex is a descending path ?The length of this path is the depth of the vertex 1 2 3 4 5 6 8 7 9 10 12 11 root depth = 1 depth = 0 depth = 3 depth = 2 1 3 8 11 Theory and Terminology ?Definition: If there is a descending path from v 1 to v 2 , v 1 is an ancestor of v 2 , and v 2 is a descendant of v 1 . Theory and Terminology ?Suppose v is a vertex of depth k: ?Any vertex that is adjacent to v must have depth k - 1 or k + 1. 1 2 3 4 5 6 8 7 9 10 12 11 root depth = 1 depth = 0 depth = 3 depth = 2 3 1 7 8 Page 3 1 Trees : Part 1 Section 4.1 (1) Theory and Terminology (2) Preorder, Postorder and Levelorder Traversals Theory and Terminology ?Definition: A tree is a connected graph with no cycles ?Consequences: ?Between any two vertices, there is exactly one unique path A Tree? 1 2 3 4 5 6 8 7 9 10 12 11 A Tree? 1 2 3 4 5 6 8 7 9 10 12 11 Theory and Terminology ?Definition: A rooted tree is a graph G such that: ?G is connected ?G has no cycles ?G has exactly one vertex called the root of the tree Theory and Terminology ?Consequences ?The depth of a vertex v is the length of the unique path from root to v ?G can be arranged so that the root is at the top, its neighboring vertices are vertices of depth 1, and so on… ?The set of all vertices of depth k is called level k of the tree 2 A Rooted Tree 1 2 3 4 5 6 8 7 9 10 12 11 root depth = 1 depth = 0 depth = 3 depth = 2 height = 2 height = 3 height = 0 height = 1 Rooted Tree: Recursive definition ? A graph with N nodes and N - 1 edges ? Graph has ?one root r ?Zero or more non-empty sub-trees, each of whose root is connected to r by an edge. ?Every node except the root has one parent Theory and Terminology ? Definition: A descending path in a rooted tree is a path, whose edges go from a vertex to a deeper vertex 1 2 3 4 5 6 8 7 9 10 12 11 root depth = 1 depth = 0 depth = 3 depth = 2 3 8 12 Theory and Terminology ? Consequences: ?A unique path from the root to any vertex is a descending path ?The length of this path is the depth of the vertex 1 2 3 4 5 6 8 7 9 10 12 11 root depth = 1 depth = 0 depth = 3 depth = 2 1 3 8 11 Theory and Terminology ?Definition: If there is a descending path from v 1 to v 2 , v 1 is an ancestor of v 2 , and v 2 is a descendant of v 1 . Theory and Terminology ?Suppose v is a vertex of depth k: ?Any vertex that is adjacent to v must have depth k - 1 or k + 1. 1 2 3 4 5 6 8 7 9 10 12 11 root depth = 1 depth = 0 depth = 3 depth = 2 3 1 7 8 3 Theory and Terminology ?Suppose v is a vertex of depth k: ?Vertices adjacent to v of depth k + 1 are called children of v. 1 2 3 4 5 6 8 7 9 10 12 11 root depth = 1 depth = 0 depth = 3 depth = 2 3 7 8 Theory and Terminology ? Suppose v is a vertex of depth k: ?If k > 0, there is exactly one vertex of depth k – 1 that is adjacent to v in the graph. ?This vertex is called the parent of v. 1 2 3 4 5 6 8 7 9 10 12 11 root depth = 1 depth = 0 depth = 3 depth = 2 3 1 Theory and Terminology ?Definitions ?A vertex with no children is called a leaf 1 2 3 4 5 6 8 7 9 10 12 11 root depth = 1 depth = 0 depth = 3 depth = 2 Theory and Terminology ? Definitions ?Depth of a vertex v is its distance from the root. ?Height of a vertex v is the distance of the longest path from v to one of its descendant leaves. ?The height of a tree is the maximum depth of its vertices 1 2 3 4 5 6 8 7 9 10 12 11 root depth = 1 depth = 0 depth = 3 depth = 2 height Theory and Terminology ? Definitions ?The root is the only vertex of depth 0. The root has no parent. 1 2 3 4 5 6 8 7 9 10 12 11 root depth = 1 depth = 0 depth = 3 depth = 2 1 Example of rooted tree ? Which are the parent nodes? ? Which are the child nodes? ? Which are the leaves? ? What is the height and depth of the tree? ? What is the height and depth of node E? Node F? Page 4 1 Trees : Part 1 Section 4.1 (1) Theory and Terminology (2) Preorder, Postorder and Levelorder Traversals Theory and Terminology ?Definition: A tree is a connected graph with no cycles ?Consequences: ?Between any two vertices, there is exactly one unique path A Tree? 1 2 3 4 5 6 8 7 9 10 12 11 A Tree? 1 2 3 4 5 6 8 7 9 10 12 11 Theory and Terminology ?Definition: A rooted tree is a graph G such that: ?G is connected ?G has no cycles ?G has exactly one vertex called the root of the tree Theory and Terminology ?Consequences ?The depth of a vertex v is the length of the unique path from root to v ?G can be arranged so that the root is at the top, its neighboring vertices are vertices of depth 1, and so on… ?The set of all vertices of depth k is called level k of the tree 2 A Rooted Tree 1 2 3 4 5 6 8 7 9 10 12 11 root depth = 1 depth = 0 depth = 3 depth = 2 height = 2 height = 3 height = 0 height = 1 Rooted Tree: Recursive definition ? A graph with N nodes and N - 1 edges ? Graph has ?one root r ?Zero or more non-empty sub-trees, each of whose root is connected to r by an edge. ?Every node except the root has one parent Theory and Terminology ? Definition: A descending path in a rooted tree is a path, whose edges go from a vertex to a deeper vertex 1 2 3 4 5 6 8 7 9 10 12 11 root depth = 1 depth = 0 depth = 3 depth = 2 3 8 12 Theory and Terminology ? Consequences: ?A unique path from the root to any vertex is a descending path ?The length of this path is the depth of the vertex 1 2 3 4 5 6 8 7 9 10 12 11 root depth = 1 depth = 0 depth = 3 depth = 2 1 3 8 11 Theory and Terminology ?Definition: If there is a descending path from v 1 to v 2 , v 1 is an ancestor of v 2 , and v 2 is a descendant of v 1 . Theory and Terminology ?Suppose v is a vertex of depth k: ?Any vertex that is adjacent to v must have depth k - 1 or k + 1. 1 2 3 4 5 6 8 7 9 10 12 11 root depth = 1 depth = 0 depth = 3 depth = 2 3 1 7 8 3 Theory and Terminology ?Suppose v is a vertex of depth k: ?Vertices adjacent to v of depth k + 1 are called children of v. 1 2 3 4 5 6 8 7 9 10 12 11 root depth = 1 depth = 0 depth = 3 depth = 2 3 7 8 Theory and Terminology ? Suppose v is a vertex of depth k: ?If k > 0, there is exactly one vertex of depth k – 1 that is adjacent to v in the graph. ?This vertex is called the parent of v. 1 2 3 4 5 6 8 7 9 10 12 11 root depth = 1 depth = 0 depth = 3 depth = 2 3 1 Theory and Terminology ?Definitions ?A vertex with no children is called a leaf 1 2 3 4 5 6 8 7 9 10 12 11 root depth = 1 depth = 0 depth = 3 depth = 2 Theory and Terminology ? Definitions ?Depth of a vertex v is its distance from the root. ?Height of a vertex v is the distance of the longest path from v to one of its descendant leaves. ?The height of a tree is the maximum depth of its vertices 1 2 3 4 5 6 8 7 9 10 12 11 root depth = 1 depth = 0 depth = 3 depth = 2 height Theory and Terminology ? Definitions ?The root is the only vertex of depth 0. The root has no parent. 1 2 3 4 5 6 8 7 9 10 12 11 root depth = 1 depth = 0 depth = 3 depth = 2 1 Example of rooted tree ? Which are the parent nodes? ? Which are the child nodes? ? Which are the leaves? ? What is the height and depth of the tree? ? What is the height and depth of node E? Node F? 4 Overview of Tree Implementation ? Each node points to ?Its first child ?Its next sibling ?Back to its parent (optional) ? What could be an alternate representation? Tree Traversals ?Definition: A traversal is the process for “visiting” all of the vertices in a tree ?Often defined recursively ?Each kind corresponds to an iterator type ?Iterators are implemented non-recursively Preorder Traversal ?Visit vertex, then visit child vertices (recursive definition) ?Depth-first search ?Begin at root ?Visit vertex on arrival arrival ?Implementation may be recursive, stack- based, or nested loop Preorder Traversal 1 2 3 4 5 6 8 7 root 2 5 6 3 7 8 4 Preorder Traversal of UNIX Directory Tree Postorder Traversal ?Visit child vertices, then visit vertex (recursive definition) ?Depth-first search ?Begin at root ?Visit vertex on departure departure ?Implementation may be recursive, stack- based, or nested loop Page 5 1 Trees : Part 1 Section 4.1 (1) Theory and Terminology (2) Preorder, Postorder and Levelorder Traversals Theory and Terminology ?Definition: A tree is a connected graph with no cycles ?Consequences: ?Between any two vertices, there is exactly one unique path A Tree? 1 2 3 4 5 6 8 7 9 10 12 11 A Tree? 1 2 3 4 5 6 8 7 9 10 12 11 Theory and Terminology ?Definition: A rooted tree is a graph G such that: ?G is connected ?G has no cycles ?G has exactly one vertex called the root of the tree Theory and Terminology ?Consequences ?The depth of a vertex v is the length of the unique path from root to v ?G can be arranged so that the root is at the top, its neighboring vertices are vertices of depth 1, and so on… ?The set of all vertices of depth k is called level k of the tree 2 A Rooted Tree 1 2 3 4 5 6 8 7 9 10 12 11 root depth = 1 depth = 0 depth = 3 depth = 2 height = 2 height = 3 height = 0 height = 1 Rooted Tree: Recursive definition ? A graph with N nodes and N - 1 edges ? Graph has ?one root r ?Zero or more non-empty sub-trees, each of whose root is connected to r by an edge. ?Every node except the root has one parent Theory and Terminology ? Definition: A descending path in a rooted tree is a path, whose edges go from a vertex to a deeper vertex 1 2 3 4 5 6 8 7 9 10 12 11 root depth = 1 depth = 0 depth = 3 depth = 2 3 8 12 Theory and Terminology ? Consequences: ?A unique path from the root to any vertex is a descending path ?The length of this path is the depth of the vertex 1 2 3 4 5 6 8 7 9 10 12 11 root depth = 1 depth = 0 depth = 3 depth = 2 1 3 8 11 Theory and Terminology ?Definition: If there is a descending path from v 1 to v 2 , v 1 is an ancestor of v 2 , and v 2 is a descendant of v 1 . Theory and Terminology ?Suppose v is a vertex of depth k: ?Any vertex that is adjacent to v must have depth k - 1 or k + 1. 1 2 3 4 5 6 8 7 9 10 12 11 root depth = 1 depth = 0 depth = 3 depth = 2 3 1 7 8 3 Theory and Terminology ?Suppose v is a vertex of depth k: ?Vertices adjacent to v of depth k + 1 are called children of v. 1 2 3 4 5 6 8 7 9 10 12 11 root depth = 1 depth = 0 depth = 3 depth = 2 3 7 8 Theory and Terminology ? Suppose v is a vertex of depth k: ?If k > 0, there is exactly one vertex of depth k – 1 that is adjacent to v in the graph. ?This vertex is called the parent of v. 1 2 3 4 5 6 8 7 9 10 12 11 root depth = 1 depth = 0 depth = 3 depth = 2 3 1 Theory and Terminology ?Definitions ?A vertex with no children is called a leaf 1 2 3 4 5 6 8 7 9 10 12 11 root depth = 1 depth = 0 depth = 3 depth = 2 Theory and Terminology ? Definitions ?Depth of a vertex v is its distance from the root. ?Height of a vertex v is the distance of the longest path from v to one of its descendant leaves. ?The height of a tree is the maximum depth of its vertices 1 2 3 4 5 6 8 7 9 10 12 11 root depth = 1 depth = 0 depth = 3 depth = 2 height Theory and Terminology ? Definitions ?The root is the only vertex of depth 0. The root has no parent. 1 2 3 4 5 6 8 7 9 10 12 11 root depth = 1 depth = 0 depth = 3 depth = 2 1 Example of rooted tree ? Which are the parent nodes? ? Which are the child nodes? ? Which are the leaves? ? What is the height and depth of the tree? ? What is the height and depth of node E? Node F? 4 Overview of Tree Implementation ? Each node points to ?Its first child ?Its next sibling ?Back to its parent (optional) ? What could be an alternate representation? Tree Traversals ?Definition: A traversal is the process for “visiting” all of the vertices in a tree ?Often defined recursively ?Each kind corresponds to an iterator type ?Iterators are implemented non-recursively Preorder Traversal ?Visit vertex, then visit child vertices (recursive definition) ?Depth-first search ?Begin at root ?Visit vertex on arrival arrival ?Implementation may be recursive, stack- based, or nested loop Preorder Traversal 1 2 3 4 5 6 8 7 root 2 5 6 3 7 8 4 Preorder Traversal of UNIX Directory Tree Postorder Traversal ?Visit child vertices, then visit vertex (recursive definition) ?Depth-first search ?Begin at root ?Visit vertex on departure departure ?Implementation may be recursive, stack- based, or nested loop 5 Postorder Traversal 1 root 2 3 4 5 6 7 8 2 5 5 6 6 2 3 7 7 8 8 3 4 4 1 Postorder Traversal Calculating Size of Directory Levelorder Traversal ?Visit all vertices in level, starting with level 0 and increasing ?Breadth-first search ?Begin at root ?Visit vertex on departure ?Only practical implementation is queue- based Levelorder Traversal 1 root 2 3 4 5 6 7 8 2 5 5 6 6 2 3 7 7 8 8 3 4 4 1 Tree Traversals ?Preorder: depth-first search (possibly stack-based), visit on arrival ?Postorder: depth-first search (possibly stack-based), visit on departure ?Levelorder: breadth-first search (queue- based), visit on departureRead More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!