meljun cortes tree rm104tr-8

7/29/2019 MELJUN CORTES TREE Rm104tr-8

1/20

Lesson 8 - 1

Year 1

CS113/0401/v1

LESSON 8TREE

Introduction

Mainly linear types of data

structure: strings,arrays, lists,

stacks and queues. Nonlinear

data structure called a tree. Thisstructure is mainly used to

represent data containing a

hierarchical relationship between

elements. E.g. records, family

trees and tables of contents.

A special kind of tree, called a

binary tree, which can be easily

maintained in the computer.


2/20

Lesson 8 - 2

Year 1

CS113/0401/v1

TREE

Natural Tree

WHAT HAS A natural tree got to

with a computer? Try a pseudo-

code to get the apples and return

to the ground


3/20

Lesson 8 - 3

Year 1

CS113/0401/v1

POSITIONAL VALUES (2)

Computer Tree

A simplified model of a real tree.

Where each node has two others

below it. This is a binary tree.


4/20

Lesson 8 - 4

Year 1

CS113/0401/v1

Example

The countries Malaysia, Namibia,

Mauritius, Bahrain, Hong Kong,

Pakistan, Sri Lanka, Botswana,Singapore and India are to be

placed in an alphabetical order

using pointers.

The diagram below is a complete,

linkages of all the countries.


5/20

Lesson 8 - 5

Year 1

CS113/0401/v1

CDCS Nov. 1992 part b)

A sentence A big brown fox

jump over the lazy dog must be

stored in the computer inalphabetical order.

i. Construct a BINARY TREE for

this sentence. [3]

ii. From the BINARY TREE,

construct a TABLE with the

appropriate columns with the

respective fields: Leftdescendent, Right descending

and Parent pointer respectively.

[5]

(refer to next section for hints!)


6/20

Lesson 8 - 6

Year 1

CS113/0401/v1

Further Example of TreeDiagram

The text TREE DIAGRAMS ARE

QUITE EASY WHEN YOU

KNOW HOW. is to be

represented in the form of a tree.


7/20

Lesson 8 - 7

Year 1

CS113/0401/v1

TABLES

In tables, there are basically 4

types of pointers

Left pointer

Right pointer

Back pointer

Trace pointer

The Pointers, points to the left,

right of the tree trace where itcomes from or to the next node of

the tree

This to preserve the structure of

the tree


8/20

Lesson 8 - 8

Year 1

CS113/0401/v1

TABLES


9/20

Lesson 8 - 9

Year 1

CS113/0401/v1

TABLES

Using the full set of pointers, the

final tree can be represented

below,


10/20

Lesson 8 - 10

Year 1

CS113/0401/v1

BINARY TREES

A binary tree T is defined as finite set ofelements, called nodes such as that

T is empty ( called the null tree or empty

tree ), or

T contains a distinguished node R,called the root of T, and the remaining

nodes of T form an ordered pair of

disjoint binary trees T1 and T2

If T does contain a root R, then the two

trees T1 and T2 are called, respectively,the left and right subtrees of R. If T1 is

nonempty, then its root is called the left

successor of R; similarly, if T2 is

nonempty, then its root is called the right

successor of R.


11/20

Lesson 8 - 11

Year 1

CS113/0401/v1

BINARY TREES

B is a left successor and C is a

right successor of the node A.

The left subtree of the root A

consists of the node B, D, E, and

F, and the right subtree of A

consists of the nodes C, G, H, J,

K, and L.


12/20

Lesson 8 - 12

Year 1

CS113/0401/v1

TRANSVERSING OF BINARYTREES

There are three standard ways of

traversing a binary tree T with root R.

These three algorithms, called preorder,

inorder and postorder, are as follows;

Preorder:

1. Process the root.

2. Transverse the left subtree of R in

preorder.

3. Transverse the right subtrees of R in

preorder.

Inorder:

1. Transverse the left subtree of R in order.

2. Process the root R.

3. Transverse the right subtree of R in

inorder.


13/20

Lesson 8 - 13

Year 1

CS113/0401/v1

ALT

D

B C

F

RT

E


Postorder :1. Traverse the left subtree of R in

postorder.

2. Traverse the right subtree of R in

postorder.3. Process the root R.

A Simple Example Of Binary Tree


14/20

Lesson 8 - 14

Year 1

CS113/0401/v1


Preorder Traversal

The preorder traversal of T processes A,traverses LT and traverses RT.

However, the preorder traversal of LT

processes the root B and then D and E,

and the preorder traversal of RT

processes the root C and then F.

Hence4 ABDECF is the preordertraversal of T.

Inorder Traversal

The inorder traversal of T traverses LT,processes A and traverses RT.

However, the inorder traversal of LT

processes D, B and then E, and the

inorder traversal of RT processes C and

then F. Hence DBEACF is the inorder

traversal of T.


15/20

Lesson 8 - 15

Year 1

CS113/0401/v1


Postorder Traversal

The postorder traversal of T

traverses LT, traverses RT, and

processes A.However, thepostorder traversal of LT

processes D, E, and then B, and

the postorder traversal of RT

processes F and then C.

Accordingly, DEBFCA is the

postorder traversal of T.


16/20

Lesson 8 - 16

Year 1

CS113/0401/v1

38

14 56

8 23 45 38

18 70

BINARY SEARCH TREES

Most important data structures incomputer science, a binary

search tree. This structure

enables one to search for an

element. It also enables one to

easily insert and delete elements.

Binary Search Tree


17/20

Lesson 8 - 17

Year 1

CS113/0401/v1

SEARCHING AND

INSERTING IN BINARYSEARCH TREES

Suppose an ITEM of informationis given. The following algorithm

finds the location if ITEM in the

binary search tree T, or insert

ITEM as a new node in its

appropriate place in the tree

Compare ITEM with the root node

N of the tree.

If ITEM < N, proceed to the left

subtree of N

If ITEN > N, proceed to the right

subtree of N

.


18/20

Lesson 8 - 18

Year 1

CS113/0401/v1

SEARCHING AND

INSERTING IN BINARYSEARCH TREE

Repeat step (a) until one of thefollowing occurs:

We meet a node n such that

ITEM = N. In this case the searchis successful.

We meet an empty subtree,

which indicates that the search is

unsuccessful, and we insertITEM in place of the empty

subtree.


19/20

Lesson 8 - 19

Year 1

CS113/0401/v1

SEARCHING AND


Example:Consider the binary search tree T

above. Suppose ITEM = 20 is given.

Simulating the above algorithm, we

obtain the following steps:

1. Compare ITEM = 20 with the root, 38, ofthe tree T. Since 20 < 38, proceed to the

left child of 38, which is 14.

2. Compare ITEM = 20 with 14. Since 20 >

14, proceed to the right child of 14,

which is 23.3. Compare ITEM = 20 with 23. Since 20 18 does not have a right child, insert 20as the right child of 18.


20/20

Lesson 8 - 20

Year 1

CS113/0401/v1

38

14 56

8 23 45 82

18 70

20

SEARCHING AND


Diagram below shows the newtree with ITEM = 20 inserted.

meljun cortes tree rm104tr-8

Documents