methodological_instructions (21)

Methodological Instructions

Theme: Algorithms on graphs 

Aim: Implementation of search algorithms on graphs to solve the practical tasks

Lesson objective: Implementation of binary search tree (BST) graph to solve the practical task

Assessment criteria

Knowledge

·     Know what is a binary search tree (BST) graph

Comprehension

·     Understand the structure of BST graph

Application

·        Implement BST graph algorithm

Language objectives

Learners able to …

• State what is BST

• Describe the purpose of BST graph and its application in Computer Science

Vocabulary and terminology specific to the subject:

binary search tree graph,  nodes, path, root, vertices, edge

Useful expressions for dialogs and letters:

Well, in binary search tree graph there are … .

For example, every vertex has its own position and could be connected by edges.

Obviously, the path in BST graph has   … .

Theory

  Binary Search Tree

A Binary Search Tree is a binary tree with a search property where elements in the left sub-tree are less than the root and elements in the right sub-tree are greater than the root.




                                                                                          
Walking (Traversing) a Binary Search Tree

There can be 3 types of tree traversals in a binary tree as below.

• Pre-Order
• In-Order
• Post-Order

Pre-Order traversal

In this traversal the traversal happens in the following order.

• Root node
• Left Child
• Right Child

For the binary search tree, displayed above the Pre-Order traversal would be as follows.



The C# implementation for the same is as follows.

public void PreOrder_Rec (TNode root)

{

    if (root != null)

    {

        Console.Write(root.Data +" ");

        PreOrder_Rec(root.Left);

        PreOrder_Rec(root.Right);

    }

}
 
In-Order traversal

In this traversal the traversal happens in following order:

• Left Child
• Root node
• Right Child

For the binary search tree, displayed above the In-Order traversal would be as follows.



The C# implementation for that is as follows.

public void InOrder_Rec(TNode root)

{

    if (root != null)

     {

          InOrder_Rec(root.Left);

          Console.Write(root.Data +" ");

          InOrder_Rec(root.Right);

    }

}
 
Post-Order traversal

In this traversal the traversal happens in the following order:

• Left Child
• Right Child
• Root node

For the binary search tree, displayed above the Post-Order traversal would be as follows.



The C# implementation for that is as follows:

public void PostOrder_Rec(TNode root)

{

    if (root != null)

   {

         PostOrder_Rec(root.Left);

         PostOrder_Rec(root.Right);

         Console.Write(root.Data +" ");

   }

}

 Important Notes

• One of the practical uses of pre-order traversal can be a table of contents in a book where we first visit the root or main chapter then its sub-chapters.
• One of the practical uses of post-order traversal can be calculating the size of directories in a computer where the first size of its sub-folders are calculated and then it gets assigned to the root folder.
• Pre-Order and Post-Order traversal can be used in any general tree however In-Order is specific to binary trees.
• We can form a binary tree if Pre-Order and In-Order traversal or Post-Order and In-Order traversals are given.
• We can also form a binary tree if Pre-Order and Post-Order traversals are given provided each internal node of the binary tree has two children. 

П. Questions for self-assessment.

What is the BST graph in Computer Science?

How to perform traversal in BST graph?

Visual Aids and Materials links.

1. Slides

2.      https://www.c-sharpcorner.com/UploadFile/19b1bd/binarysearchtreewalkstraversal-implementation-using-C-Sharp/

3.      https://en.wikibooks.org/wiki/A-level_Computing_2009/AQA/Problem_Solving,_Programming,_Operating_Systems,_Databases_and_Networking/Programming_Concepts/Tree_traversal_algorithms_for_a_binary_tree

Students' Practical Activities:

Students must be able:

·        perform traversal  for BST graph in 3 different ways

Скачано с www.znanio.ru