The document discusses trees and graphs in computer science. It defines trees as hierarchical data structures with nodes linked by edges in a parent-child relationship. It describes key tree concepts like root, internal/leaf nodes, subtrees, depth, height, and types of trees like binary trees. It also explains tree traversal methods like preorder, inorder and postorder. Finally, it defines graphs as data structures with sets of vertices and edges, describes directed/undirected graphs, and graph concepts like paths, cycles, and weighted graphs.
The document discusses trees and graphs in computer science. It defines trees as hierarchical data structures with nodes linked by edges in a parent-child relationship. It describes key tree concepts like root, internal/leaf nodes, subtrees, depth, height, and types of trees like binary trees. It also explains tree traversal methods like preorder, inorder and postorder. Finally, it defines graphs as data structures with sets of vertices and edges, describes directed/undirected graphs, and graph concepts like paths, cycles, and weighted graphs.
The document discusses trees and graphs in computer science. It defines trees as hierarchical data structures with nodes linked by edges in a parent-child relationship. It describes key tree concepts like root, internal/leaf nodes, subtrees, depth, height, and types of trees like binary trees. It also explains tree traversal methods like preorder, inorder and postorder. Finally, it defines graphs as data structures with sets of vertices and edges, describes directed/undirected graphs, and graph concepts like paths, cycles, and weighted graphs.
The document discusses trees and graphs in computer science. It defines trees as hierarchical data structures with nodes linked by edges in a parent-child relationship. It describes key tree concepts like root, internal/leaf nodes, subtrees, depth, height, and types of trees like binary trees. It also explains tree traversal methods like preorder, inorder and postorder. Finally, it defines graphs as data structures with sets of vertices and edges, describes directed/undirected graphs, and graph concepts like paths, cycles, and weighted graphs.
Lecture # 11 TREES & GRAPHS (Introduction to Tree, Binary Tree, Graphs)
1 (1 – حال201( حاسب آلـى: المقـرر
INTRODUCTION TO TREES 1. What is tree?
In computer science, a tree is an abstract model of a hierarchical structure. A tree
consists of nodes with a parent-child relation. Trees are a hierarchical data structure of nodes. Nodes are linked by edges. A parent node references one or more nodes (children nodes) that are “lower” in the tree hierarchy.
a. Root Node Node without parent is called root node. Except for the root (no parent), every node has exactly one parent (by definition). A tree has only one root node.
b. Sibling Node Nodes that are children of the same parent are called sibling.
c. Internal Node —A node is internal if it has one or more children.
2 (1 – حال201( حاسب آلـى: المقـرر
d. Leaf Node A node is a leaf if it has no children
2. What is subtree?
The subtree of T rooted at node v is the tree consisting of all the descendants of v in T (including v) tree consisting of a node and its descendants
3. What is depth of a tree
The depth of a node v in T is the number of ancestors of v, excluding v.
More formally: If v is the root, the depth of v is 0
3 (1 – حال201( حاسب آلـى: المقـرر
4. What is height of a tree
The height of a tree is the maximum depth of its lowest level leaves. Also called maximum levels of a tree.
Two nodes are adjacent if an edge connects them. A path is a sequence of nodes in which each node is adjacent to the next one. Every node in the tree can be reached by following a unique path starting from the root. The length of a path is the number of edges on the path.
5. Types of Trees
a) —General tree – a node can have any number of children
b) —Binary tree – a node can have at most two children
4 (1 – حال201( حاسب آلـى: المقـرر
6. Tree Traversal
There are 2 basic approaches to traverse a tree - breadth-first and depth-first. With breadth-first you start at the top node then visit all its children before visiting its children's children - i.e. you explore the tree layer by layer. With depth-first searching you keep going down, backtracking when you can go no further.
With either method there's a choice of ways to order operations on the node.
In a preorder traversal, the root node of the tree is processed first, then the left subtree is traversed, then the right subtree.
Preorder traversal= A,B,D,E,C,F,G
b) Postorder Traversal (LRN):
In a postorder traversal, the left subtree is traversed, then the right subtree, and then the root node is processed.
Postorder traversal= D,E,B,F,G,C,A.
c) Inorder Traversal:
In an inorder traversal, the left subtree is traversed first, then the root node is processed, then the right subtree is traversed.
Inorder traversal= D,B,E,A,F,C,G
5 (1 – حال201( حاسب آلـى: المقـرر
7. What is Graph
A data structure that consists of a set of nodes (vertices) and a set of edges that relate the nodes to each other. The set of edges describes relationships among the vertices. As a formal definition, a graph G is defined as follows:
G=(V,E)
V(G): a set of vertices
E(G): a set of edges (pairs of vertices)
There are two important sets of objects, which specify graph and its structure. First set is V, which is called vertex-set. Each vertex can be drawn as a circle with vertex's number inside.
Vertices Next important set is E, which is called edge-set. All graphs are divided into two big groups: directed and undirected graphs. The difference is that edges in directed graphs, called arcs, have a direction.
Edge can be drawn as a line. If a graph is directed, each line has an arrow.
undirected graph directed graph
6 (1 – حال201( حاسب آلـى: المقـرر
- Sequence of vertices, such that there is an edge from each vertex to the next in sequence, is called path. - First vertex in the path is called the start vertex; - The last vertex in the path is called the end vertex. - If start and end vertices are the same, path is called cycle. - Path is called simple, if it includes every vertex only once. - Cycle is called simple, if it includes every vertex, except start (end) one, only once. Let's see examples of path and cycle.
path (simple) cycle (simple)
- The last definition we give here is a weighted graph. Graph is called weighted, if every edge is associated with a real number, called edge weight. For instance, in the road network example, weight of each road may be its length or minimal time needed to drive along.
