Embedded Files
Lesson Learning Outcomes
Lesson Learning Outcomes
At the end of this lesson, students will be able to:
Describes trees.
Identify the properties of trees.
Describe the terminology and characteristics of trees.
Sketches the spanning trees.
Construct the minimal spanning trees using:
a. Prim’s algorithm
b. Kruskal’s algorithm
Build a binary search tree.
Concept of Trees
Concept of Trees
Exercise 1
Exercise 1
Spanning Tree
Spanning Tree
Spanning tree is a subgraph of a connected graph without a cycle
It is a tree that includes all the vertices of the connected graph
Every connected graph has a spanning tree
There may be more than one solution to construct a spanning tree from a graph. Click to watch the videos below for example solutions.
Sketch the spanning trees for the following graph1.mp4Sketch the spanning trees for the following graph2.mp4
Prim’s Algorithm.mp4Prim's Algorithm
Kruskal’s Algorithm.mp4Kruskal's Algorithm
Exercise 2
Exercise 2
Exercise - Prim's & Kruskal Algorithm.pdfPractice Prim & Kruskal
Practice Prim & Kruskal
Prim & Kruskal Practice.pdfBuild a Binary Search Tree
Build a Binary Search Tree
A binary search tree is a tree where each node contains a value from a well-ordered set.
Every node or vertex has either no child node or one child node or two child nodes.
Child node in a binary tree on the left is termed as ‘left child node’ and the node on the right is termed as the ‘right child node’.
For each node n in a binary search tree hold the following simple rule:
Example
Example
Exercise 3
Exercise 3
Draw binary search tree for the following:
20, 6, 7, 100, 25, 30, 17, 16, 18, 22
‘Draw a binary search tree for this sentence”
8, 3, 10, 1, 6, 4, 7, 14, 13
‘ I love Discrete Mathematics’
Page updated
Report abuse