Chapter 1 : What is a data structure?

A data structure is created by taking existing data and building a structure according to a defined standard.
1.1 Steps in creating a data structure .
1. Create an abstract data type (ADT ) definition for each data structure.
2. Implement the defined ADT by writing a program in a computer language such as... C language
Java as defined ( ADT ) which was built upon step 1.
3. After implementation , a new data structure ( ADT ) will be obtained, based on the definition created
in step 1.
Abstract Data Type ( &
ADT )
definitions of each data structure , which consist of:
1. -
Set of data
2. %
Data relationships AUP + implement I data structure
operater code stat
3. Group of actors Lu

An example of an Abstract Data Type is the Stack 's ADT. array

limit
array
1. A set of data, such as {3, 1, 7, 15, 29}.

↑ 2. Data relationship: Data is stored so that later entered data is retrieved first.
3. Group of actors
<-

=> Operater 2 ว
- -

enquene

dequence //
ad - Push : Enter data.
=>

- Pop : Extract data.

=>

We will start with two simple abstract data types : Collection and List.
Collection ADT
1. A set of data, such as {3, 1, 7, 15, 29}.
-

2. Data relationships: Data is stored like a data container that only allows addition and deletion.
-

-operater
3. Group of actors ่ม อไม่ไ ด ้ ไ ่ได
-

Array & เ
ูลไ
สอperม
- add ( Object O ) : Add data O to the bin. Array List & เ ม อ

&- remove ( Object O ) : Delete data O from the Recycle Bin.

⑨- contains ( Object O ) : Asks if the container contains the data O. If it does, Return true if there is
-

no content; return false if there is no content. ถาม า ไ

่

ana List s address ไม่จ วเ ง//ใก

น อง ท
2 โหนด / ก ห นด งเ บ add
+*
อ งด
ี &,
Q งจะเ น llink

①recallinte *
#. . . # # แต
#

จะะโมงไป หา ใคร ร อ งโย งไป address น อไ ได

#next -1 - class mode of I ab

วแปร 2 ต
ตั
ต่
ว่
รั
ต้
จึ
ต้
กั
นึ
สิ
อี
ตั
ม่
ต่
ต้
ปิ่
ยู
มี
ข่
ก้
ม่
พื
ตั้
ล้
ด้
พิ
ติ
 &- isEmpty (): asks if the data container is empty. If it is empty, it returns true; if it is not empty, it
returns false.
④- size (): Returns the number of data entries in the bin.
4 มี
List ADT
1. A set of data, such as {3, 1, 7, 15, 29}.
2. Data relationships: Data is stored like a data container that accommodates the addition and removal
of data in a specific order, indicating the position of each data item before another, based on the
sequence in which they were entered into the container.
3. This group of operators consists of 5 operators already in the ADT Collection , plus 4 more as follows:
- add ( int i, Object O ) : Adds data O to the bin at position i.
- remove ( int i ): Delete the data at position i from the bin.
- get ( int i ): retrieves the data at position i without deleting the data from the repository.
- set ( int i, Object O ) : Overwrite the data at position i with the new data, which is O.
1.2 Create a data structure .
After defining Collections and Lists, we will implement these definitions to obtain the data structures
of Collections and Lists. Since Arrays are a basic data structure, we will start by implementing the definitions
of Collections and Lists using Arrays.
An array is a basic data structure that can store groups of data, with the following properties:
1. Contiguous data is placed in fields containing adjacent addresses .
2. The data in an array must be of the same data type.
3. Once an array is reserved , it cannot be expanded or contracted to include the reserved spaces.

1.2.1 Collection implemented by array .

The 5 methods in the interface below represent the 5 operators in the definition of Collection ; that is,
this part of the Collection interface is like... Abstract Data Type of Collection
public interface Collection {
public void add ( Object e ) ;
public void remove ( Object e ) ;
public boolean contains ( Object e ) ;
public boolean isEmpty ( ) ;
กี
 public int size ( ) ;
}
ArrayCollection class below implements ... Complete the 5 methods in the interface above. This class
is like a new data structure called Collection , created from the definition above.
public class ArrayCollection implements Collection{
private Object [] data;
private int size;

public ArrayCollection ()
{
data = new Object [ 1 ] ;
size = 0;
}
public void add ( Object e )
{
capacity ( size + 1 ) ; // If the array is full, it will simulate expanding first, then add new data.
data [ size ] = e;
size ++ ;
}
public int size ()
{ return size; }

public boolean isEmpty ()

{ return size == 0; }

public boolean contains ( Object e )

{
return indexOf ( e ) != - 1;
}
// When removing data from an unordered array , overwrite the data to be removed with the last element.
 public void remove ( object e )
{
int i = indexOf ( e ) ;
if ( i != - 1 ) // If no data e to be deleted is found It will not be removed .
{
data [ i ] = data [ size - 1 ] ; // Replace the data to be deleted with the last element.
size -- ;
data [ size ] = null;
}
}
private int indexOf ( Object e )
{
for ( int i = 0; i < size; i ++)
{
if ( data [ i ]. equals ( e )) return i;
}
return - 1;
}
private void capacity ( int a ) // This effectively expands the array size to twice its original size.

{
if ( a > data . length )
{
Object [] arr = new Object [ 2 * data . length ] ;
for ( int i = 0; i < size; i ++)
arr [ i ] = data [ i ] ;
data = arr;
}
}
 } // end of class ArrayCollection

public class Test {

public static void main ( String [] args )
{
ArrayCollection a = new ArrayCollection ( ) ;
Integer ob1 = new Integer ( 20 ) ;
Integer ob2 = new Integer ( 30 ) ;
[Link] ( ob1 ) ;
[Link] ( ob2 ) ;
a . remove ( ob1 ) ;
System . out . print ( a . size () ) ;
boolean c = a . contains ( ob2 ) ;
}
}

1.2.2 List implemented by Array

The interface below represents 9 operators. The first 5 are drawn from the Collection definition, and 4
more are added. This means the definition or Abstract Data Type of List has 9 operators. Therefore, the List
interface below has a total of 9 operators. methods by Extends from interface Collection 5 methods.
public interface List extends Collection {
public void add ( int i, Object e ) ;
public void remove ( int i ) ;
public Object get ( int i ) ;
public void set ( int i, Object e ) ;
}
ArrayList class below has been implemented. Complete the 9 methods in the interface above. This
class is like a new data structure called a List , created from the definition above.

public class ArrayList implements List{

private Object [] data;
private int size;
public ArrayList ()
{
data = new Object [ 1 ] ;
size = 0;
}
public void add ( Object e )
{
add ( size,e ) ;
}
public int size ()
{ return size; }

public boolean isEmpty ()

{ return size == 0; }

public boolean contains ( Object e )

{
return indexOf ( e ) != - 1;
}

public void remove ( object e )

{
int i = indexOf ( e ) ;
if ( i != - 1 ) // If no data e to be deleted is found It will not be removed .
{
remove ( i ) ;
}
}
 private int indexOf ( Object e )
{
for ( int i = 0; i < size; i ++)
{
if ( data [ i ]. equals ( e )) return i;
}
return - 1;
}
private void capacity ( int a ) // This effectively doubles the size of the array .

{
if ( a > data . length )
{
Object [] arr = new Object [ 2 * data . length ] ;
for ( int i = 0; i < size; i ++)
arr [ i ] = data [ i ] ;
data = arr;
}
}

public void remove ( int i )

{
if ( i > = 0 && i < = size - 1 ) // Will not delete data in locations that contain no data.

{
// Move all elements after position j up 1 position.
for ( int j = i + 1; j < size; j ++)
{ data [ j - 1 ] = data [ j ] ; }
size -- ;
data [ size ] = null;
}
}
public Object get ( int i ) // Will not retrieve data if i is a location where no data exists.

{
if ( i > = 0 && i < = size - 1 )
{
return data [ i ] ;
}
}

public void set ( int i, Object e ))

{
if ( i > = 0 && i < = size - 1 ) // The data will not be changed if i is a location where no data exists.

{
data [ i ] = e;
}
}

public void add ( int i, Object e )

{
// Data can only be inserted where existing data exists, including adding data to the field immediately
following the last data element.
if ( i > = 0 && i < = size )
{
capacity ( size + 1 ) ;
// Shift the element at the desired insertion position and all elements following the desired insertion position
down 1 position.
for ( int j = size - 1; j > = i; j --)
{ data [ j + 1 ] = data [ j ] ; }
// insert new member Enter the empty space.
data [ i ] = e;
 size ++ ;
}
}
} // end of class ArrayList
public class Test {
public static void main ( String [] args )
{
ArrayList a = new ArrayList ( ) ;
Integer ob1 = new Integer ( 20 ) ;
Integer ob2 = new Integer ( 30 ) ;
Integer ob3 = new Integer ( 50 ) ;
Integer ob4 = new Integer ( 70 ) ;

[Link] ( ob1 ) ;
[Link] ( ob2 ) ;
a . add ( 1,ob3 ) ;
a . add ( 0,ob4 ) ;
a . remove ( ob1 ) ;
System . out . print ( a . size () ) ;
boolean c = a . contains ( ob2 ) ;
a . remove ( 1 ) ;

}
}

Because a list of data is ordered by entry, the method for removing data at the desired position is
to shift all elements immediately following the desired position up one position, so that the new element
overlaps the element being deleted. For example, to delete the position at the 'i'th position.
 อยา
กแทร
#st

#- At

Because the list data is ordered by placement, the method for adding to a specific position is to shift
the element at the desired insertion position and all subsequent elements down one position to create space
for the insertion.
For example, we want to insert data at the i- th position.

Whether deleting or inserting data, the data is shifted a maximum of n characters using only a single for loop .
Therefore, the complexity is only O(n).
End-of-chapter exercises
ถ้
Write a program to create a data structure list using an array , with the following details:
1. Create a Collection interface to specify the list of necessary methods , which are:
- add ( Object o ) to add the desired data.
- remove ( Object o ) is used to delete the desired data.
- contain s ( Object o ) for searching for the desired information.
- isEmpty () To check if there is any data inside this data reservoir.
- size () is used to check the quantity of data.
- add ( int i, Object e ) to add data at position i.
- remove ( int i ) deletes the data at position i.
- get ( int i ) retrieves data at position i.
- set ( int i, Object e ) replaces the data at position i with the data e.

2. Create an ArrayList class to construct a list data structure using an array , implementing it from the
List interface and making the abstract methods within that interface complete methods .
3. Create a Test Class named Test2 to verify the data storage operation. The results will be displayed
on the screen after the following operations:
3.1 Add integer data nodes with values 20 and 30.
3.2 Delete the data node with the value 20 from the data bin.
3.3 Delete the data node with a value of 50 from the bin.
3.4 Find the data node that has a value of 30 in the data bucket.
 Chapter 2 Linked List
The next data structure is a Linked List , which is a data structure that connects nodes together in a chain.
There are 3 types .
- Singly Linked List
- Circular Linked List
- Doubly Linked List
2.1 Singly Linked List
The following conditions apply as stated in this document:
1. There must be a pointer pointing to the first node, in this case named 'first'.
2. The last node in the `next` section must be `null` , indicating that there is no address for the next node.
3. The first indicator It is not movable; it must point to the first node, which serves as the pointer for
accessing the Linked List. To access any node in the Linked List , one must enter through the first node.

<null
The difference between a Linked List and an Array is:
1. An array contains contiguous elements in its addresses , but a linked list doesn't necessarily
require contiguous addresses .
2. The data in an array must be of the same type, but in a linked list, the data is of the same type.
They don't have to be the same type.
3. Once an array is reserved , its number of reserved elements cannot be expanded or contracted.
However, a linked list can be expanded indefinitely.
2.1.1 Nodes
Since a linked list consists of nodes connected to each other, we must first understand the nodes before
creating a linked list.
A node consists of two parts.
- data section, as shown in the image below, is the first node in the data section , storing the data '
a '.
- The part that stores the address of the next node ( next ) is shown in the figure below. The first
node's part, `next`, stores the address of the next node, which is the address of the node
containing data (b).
 (store address of b)

- If the ` next` node doesn't yet store the address of any node, it will look like the image below.

object 3 = Sty

ให้ ก 28 แ ม

แ ่ ter Mos cast. "instance es of

To create a node, you need a node class. The node class has two instance variables , `data` and
`next` , which store the data and addresses of the next node respectively. Therefore, it has four instance
methods . Methods for retrieving ( get ) and replacing ( set ) data on the `data` element and `next` element.
node ประกอบ 2 ว
-dat
ส า ดลก
ง
-nex

public class MyNode {

=>

า งาน!!เ น private Object data;

private MyNode-next;
instance
นา อ อบอ
var

&

<- => Moc, er r address nos node

Bank A &- #Bank>1000
1 -

&. t public MyNode ( Object obj, MyNode n ) {

7
ra2 ser
surfe data = obj; constructe
return เ น
next = n;
}
Gi public void setNext ( MyNode n ) {
↓

next = n;ใส่ดมาต
=
ต วห

เขา

} method

+
public void setData ( Object d ) {
=

=
-
data = d; ↓

}
public MyNode getNext () {
-
ส่
ร้
ข้
ตั
ช่
ม่
ร้
ล่
ลู
น้
กี
 return next;
}
public Object getData () {
= >

return data;
}

}
2.1.2 Creating a Singly Linked List
1. Start with an empty Linked List or an empty trash can.
empty linked list means that `first` has no next node to point to; therefore, `first = null;`

2. Insert the first element into a linked list ; for example, to insert the element ' a ' into an empty bin.
Before adding data ' a ' to a Linked List , a node must be created to store the data ' a '.
=>
Mynode t = new Mynode ( a,/
null ) ; ( 1A
)

After that, take... First , point to the image below.

first = t; ( 2 )
Currently, `first` points to the first node, and ` next` , the node of the last one, is null. This means that
the condition of a Linked List is met. Therefore, the data ' a ' is now the first item in the Linked List .

Or you can combine commands ( 1 ) and ( 2 ) into one command as in the command above.

3. Add a new node to the end ( method addEnd ).

Suppose a linked list already contains 3 pieces of data, and we want to add piece of data (1) to the end.
 first pointer. It cannot be moved; it can only point to the first node. Therefore, we need to create
another pointer to move to the last node. In this case, this pointer is named ' start' and is created using the
command below.
while ( start . getNext () != null )
start = [Link] ( ) ;

When `start` points to the last node, set the `next` portion of `start` to the address of the newly created
node, which has a value of 1, as shown in the image below.

4. Insert a new node. Insert a page. ( method add )

If the linked list already contains data 2 , data 4 will be inserted in front of it.

First, create a new node that stores the value 4 , and set the `next` clause of this new node to the
address of the first node. This address was originally stored in the variable `first` , as shown in the image and
command below.
 Then, change `first` to point to the new node instead, because now the new node is the first node in
the Linked List , a c c o r d i n g t o t h e c o m m a n d a n d
image below. That is, the variable ` first` stores the address of the new node, which is stored in the variable
`p`.

5. Remove a node from a Linked List ( method) remove )

It is possible that the node to be deleted is the first node, a middle node, or the last node.
5.1 Delete the first node .
To delete the node with the value 8 below, which is the first node...

Move `first` to point to the second node instead of the first node, as shown in the command and
image below.
5.2 Delete the intermediate node .
If we need to enclose the node with the value of 3 below, which is the middle node.

first pointer. Since it cannot be moved, another pointer must be created to move to the desired
location for deletion. In this case, this pointer is named ' start'. Because the 'next' part of the node preceding
the one to be deleted must point to the node following the one to be deleted, an additional pointer is needed
to move it before the ' start' pointer . In this case, that pointer is named ' pre'.
Before moving the pointers, set pre and start equal to first , meaning that pre and start begin pointing
to the first node .

Before moving the start value, the preset value must be the same as the original start value . That is,
when the start value is moved, the preset value will move immediately after the start value , as shown in the
command and image below.

Then, set the value in the 'next' section of the node pointed to by the 'pre' pointer to the address of
the node next to the node to be deleted, which is pointed to by the 'start' pointer ( the node with a value of 3).
As shown in the instructions and image below.
5.3 Delete the tail node .
To delete the node below that has a value of 5 , which is the last node.

Before moving the pointers, set pre and start equal to first , meaning that pre and start begin pointing
to the first node .

Move the pointers `pre` and `start` together. `start` will stop at the node to be deleted, which is the
last node, and `pre` will stop at the node before the one ` start` pointed to, as shown in the command and the
two figures below.
 To remove the last node, which stores the value 5 , we set the ` next` attribute of the node preceding
the one to be removed, which is pointed to by the `pre` pointer, to `null`. This means there is no address for
the next node, indicating that the node pointed to by `pre` is now the last node, as shown in the command and
image below.

2.2 Collection implementation using Linked List .

It's time to create a Collection data structure using a Linked List . First, we need the Collection 's
Abstract Data Type , which is the Collection interface and has five methods.

public interface Collection {

public void add ( Object e ) ;
-
Abstract method
ใน inter free.
ร public void remove ( Object e ) ;
-

-> insolo,
⑧ public boolean contains ( Object e ) ;
override
-
5 method p

& public boolean isEmpty ( ) ;

- งจ กลามเป

⑤ public int size ( ) ;

data structure
&
-

Before creating a data structure using a Linked List, a node class is needed to create nodes to store
each data point. Since each node has two instance variables , ` data` and `next` , as explained above, this
class has four methods for `set` and ` get`. These two instance variables
ถึ
 public class MyNode {
private Object data;
private MyNode next;

public MyNode ( Object obj, MyNode n ) {

data = obj;
next = n;
}
บ public void SetNext ( MyNode n ) {
=>

next = n;
}

public void setData ( Object d ) {

=

data = d;
}

~ public MyNode getNext () {

=

return next;
}

public Object getData () {

· return data;
=

}
}

Next, create a bin using a Linked List and manage the data in this bin using the LinkedCollection
class below. This is a Collection data structure implemented using a Linked List ; therefore, this class will
handle the management of the data within it .
- Create an empty container in the class's constructor , setting `first = null;`.
- Enter the information into the Linked List.
 Connect the data nodes using the `add` method . Or the `addEnd` method (add to the end).
By definition, data in a Collection does not have a specific order for storing or deleting data.
Therefore, when adding new data, it can be added to the beginning or to the end of a Linked List . Thus, the
LinkedCollection class below, which is the Collection data structure , only has the `add` method (for adding
data to the beginning) or the `addEnd` method (for adding data to the end) for adding new data.
- Deleting data from... Linked List by method remove ( Object o )
First, we need to find out which node the data 'o' is located in. This linked list uses a while loop to
move the 'start' pointer to the node containing the item to be deleted, and the 'pre' pointer to the node
preceding the ' start' pointer.

Then, upon leaving... If the while loop doesn't find a node containing the data (o) , it exits the remove
method using the keyword ` remove`. return However, if you encounter a node containing the data you want to
delete , check whether it is the first node of the linked list or a middle node. A linked list is the last node of a
list. Linked List: Then , once you know whether it's the first, middle , or last node , follow the deletion steps
described in Sections 5.1-5.3 of Section 2.1.2 above , respectively .
- Ask if the data specified in this Linked List exists , using the contain ( Object o ) method.
First, find out which node in the linked list contains the data 'o' using a while loop. The 'start' pointer
moves to the node containing the data you're looking for, similar to the ' remove' method 's while loop , but the
search doesn't require the 'pre' pointer. At the end of the while loop, the ' start' pointer points to the node
containing data 'o' (the node being searched). If the node containing data 'o' is not found, the 'start' pointer
moves to the end, reaching null (the 'next' part of the last node).
- Check if this data bin or linked list is empty using the isEmpty () method.
If the pointer ` first` doesn't point to any node, it means there's no data in this bucket; that is, `first =
null`.
- To find out how many entries are in this bin, or how many nodes are in this Linked List , use the
`size ()` method.
Return the variable ' size' , that is, return the variable ' size'.
- An additional method not included in the Collection ADT is the printlist() method . This method
displays the current contents of a linked list , from the first node to the last. It works by moving the pointer from
the start node to each node and printing the value of that node, continuing until the end of the linked list ( the
last node ).
 public class LinkedCollection implements Collection{
ง mode
private MyNode first; & first (1 ข แรก

privateconuisize
=> int size; cos ***

↑
public LinkedCollection () { //Start at an empty bin
first = null; W ง เปล Link Lis

size = 0; } + แบ มน เ นแ บบ เ ยง
public boolean isEmpty () {
~

return first == null; // or size == 0; -> แสดง า empi

-
add 1 จา

} firs ⑤
public int size () { -
return size; add ho's
⑤
nor
} add 3 add
add rew
* *
public void add ( Object value ) // Adding a node to·
the front
⑤
- - -
-

3)
125

{ * *

#units
Daniel
first = new MyNode ( value, first ) ;
size ++ ;
=

} #

public void printlist () // Traversing the list

fi
{ MyNode start = first;
while ( start != null )
{
System . out . println ( start . getData () ) ; เอามา แทน ลง null ให้ไ
first / ว
* ส าว

S
start = [Link] ( ) ; ก

order first
I am /
#
}
} add ห ง
ง
public void addEnd ( Object obj ) //Adding a node to&
the end

%
{ if ( isEmpty ())
=
add ( obj ) ;
else { MyNode start = first;
ถึ
นี้
ตั
อั
ป็
ร้
ถั
ลั
รี
ว่
 ปร
* จ:ป ล ันจ ะไป วท

น
int
↓
์ จะป
กกรณ
while (-
start . getNext () != null ) S! = ncl

System.
------
Out,
print (S.
get Date());
M
start = [Link] ();
<++ แ งใช้ size) <หงหนาด 8 3 nu
MyNode tmp = new MyNode ( obj, start . getNext () ) ;
#

* [Link] ( tmp ) ;
size ++ ;
Wor
}
}
public void remove ( Object o )
{
if ( isEmpty ()) // If there is no data, it cannot be removed .
return;
MyNode pre;
MyNode start = first;
while ( start . getNext () != null && !( start . getData (). equal ( o )))
{ pre = start;
start = [Link] ( ) ;
//Move the start line to the node containing the data to be deleted.
}

if (!( start . getData (). equal ( o )) // If no data to be deleted is found

System . out . println (“ Not Found ”) ;
else
{
if ( start == first )
first = [Link] () ; // Delete the first node of the Linked List
else
[Link] ( [Link] ( ) ) ; // Remove the middle or last node of the Linked List
size -- ;
}
// Finish remove
ทีี่
มั
ตี
ถั
รั่
ตั
ถั
ล้
public boolean contains ( Object o )
{
MyNode start = first;
while ( start != null && !( start . getData (). equal ( o )))
{start = [Link] () ; // Attempt to move start to the desired node }
}
return start != null; //if "start = null" means that the requested information was not found.
}
// End of LinkedCollection class

The test class below is used to test the LinkedCollection class , a data structure created using a
Linked List. It checks whether data is added, removed, whether the specified data exists, how many items are
in the collection, or whether the collection is empty. It checks if all of this works correctly .

public class Test{

public static void main ( String [] args ) {
LinkedCollection list = new LinkedCollection ( ) ;
Integer ob1 = new Integer ( 20 ) ;
Integer ob2 = new Integer ( 30 ) ;
Integer ob3 = new Integer ( 50 ) ;
[Link] ( ob1 ) ;
[Link] ( ob2 ) ;
[Link] ( ob1 ) ;
System . out . print ( list . size () ) ;
boolean c = list . contains ( ob2 ) ;
[Link] ( ob3 ) ;
}
}

2.3 List implementation using Linked List .

 Next, we will create a data structure for a List using a Linked List. First, we need the Abstract Data
Type of List , which is the List interface. It has a total of 9 methods , 5 of which extend from the collection and
4 add to it .

public interface List extends Collection {

public void add ( int i, Object e ) ;
public void remove ( int i ) ;
public Object get ( int i ) ;
public void set ( int i, Object e ) ;
}
Before creating a data structure using a Linked List, you need a node class to create nodes to store
each piece of data. This node class will be the same as the one used to create the Collection structure
because it also uses a singly Linked List.

public class MyNode {

private Object data;
private MyNode next;

public MyNode ( Object obj, MyNode n ) {

data = obj;
next = n;
}
public void SetNext ( MyNode n ) {
next = n;
}
public void setData ( Object d ) {
data = d;
}
public MyNode getNext () {
return next;
}
 public Object getData () {
return data;
}
}
Next, create a bin using a Linked List and manage the data in this bin using the LinkedList class
below. This class is a List data structure implemented using Linked Lists ; therefore, this class will handle the
data management.
- Create an empty container in the class's constructor , setting `first = null;`.
- Enter the information into the Linked List.
Connect the data nodes together using the `add ( Object obj )` method.
By definition, a List has a sequence for storing and deleting data. Therefore, when adding new data,
it is added to the end of the Linked List. Thus, the LinkedList class below, which is a List data structure , only
has a ` add ( Object obj )` method for adding new data to the end.
- Deleting data from a Linked List using the remove ( Object o ) method.
First, we need to find out which node in the linked list contains the data 'o'. Using a while loop , we
move the 'start' pointer to the node containing the data to be deleted and the 'pre' pointer to the node
containing the data. Point to the node preceding the start pointer. Then, upon exiting the while loop , if no
node containing the data (o) is found , exit the remove method using the keyword. return
But if you encounter a node containing the data you want to delete , check if it is the first node of... A
linked list can be identified as either the first , middle, or last node. Once you know whether it's the first, middle
, or last node, follow the deletion instructions described in sections 5.1-5.3 of section 2.1.2 above , in that
order .
- Asks whether the data specified in this Linked List exists. The method contains ( Object o )
First, find out which node in the linked list contains the data 'o' using a while loop. The 'start' pointer
moves to the node containing the data you're looking for, similar to the ' remove' method 's while loop , but the
search doesn't require the 'pre' pointer. At the end of the while loop, the ' start' pointer points to the node
containing data 'o' (the node being searched). If the node containing data 'o' is not found, the 'start' pointer
moves to the end, reaching null (the 'next' part of the last node).
- Check if this data bin or linked list is empty using the isEmpty () method.
 If the pointer ` first` doesn't point to any node, it means there's no data in this bucket; that is, `first =
null`.
- The `size ()` method asks how many entries are in this bin or how many nodes are in this linked list.
Return the variable ' size' , that is, return the variable ' size'.
-The additional method not included in the ADT list is the printlist () method. This method displays the
current contents of the linked list on the screen, from the first node to the last. It works by moving the pointer
from the start node to each node and printing the value of that node, repeating this process until the end of the
linked list.

public class LinkedList implements List{

private MyNode first;
private int size;

public LinkedList () {
first = null;
size = 0;
}
public boolean isEmpty () {
return first == null; // size == 0;
}
public int size () {
return size;
}
public void printlist () // Traversing the list
{ MyNode start = first;
while ( start != null )
{
System . out . println ( start . getData () ) ;
start = [Link] ( ) ;
}
}
 public void add ( Object obj ) //It's not possible to add a node from the back to the front because of the
order.
{
if ( isEmpty ())
first = new MyNode ( obj, first ) ;
else {
MyNode cur = first;
while ( cur . getNext () != null )
cur = [Link] ( ) ;
MyNode tmp = new MyNode ( obj, cur . getNext () ) ;
[Link] ( tmp ) ;
size ++ ;
}
}

public void remove ( Object o )

{
if ( isEmpty ())
return;
MyNode pre;
MyNode start = first;
while ( start . getNext () != null && !( start . getData (). equal ( o )))
{ pre = start;
start = [Link] ( ) ;
}
if (!( start . getData (). equal ( o )) // If not found
System . out . println (“ Not Found ”) ;
else
{
 if ( start == first )
first = [Link] ( ) ; // Delete the first node
else
pre . setNext ( start . getNext () ) ;
size -- ;
}
// Finish remove

public boolean contains ( Object o )

{
MyNode start = first;
while ( start != null && !( start . getData (). equal ( o )))
{start = start . getNext () ; }
return start != null;
}

public void remove ( int i )

{ // remove by specifying the position, where the first node has position 0 }
if ( i > = 0 && i < = size - 1 )
{ if ( i == 0 ) first = first . getNext ( ) ;
else {
MyNode pre, start = first;
for ( int j = 1; j < = i; j ++)
{ pre = start;
start = [Link] ( ) ;
}
pre . setNext ( start . getNext () ) ;

// End else
size -- ;
 }
}

2.4 Sort using Linked List .

Let's define another Abstract Data Type called Sort.
Sort ADT
1. A set of data, such as {3, 1, 7, 15, 29}.
2. Data relationships: Data is stored like a data container that can accommodate additions and
deletions according to the data's value, such as sorting from highest to lowest value.
3. Group of actors
- add ( Object O ) : Add data O to the bin.
- remove ( Object O ) : Delete data O from the Recycle Bin.
- contain s ( Object O ) : Asks if the container contains data O. If it does, it returns true; if not, it
returns false.
- isEmpty (): asks if the data container is empty. If it is empty, it returns true; if it is not empty, it
returns false.
Next, we will use a Singly Linked List to implement the Sort Abstract Data Type as defined above.
Because all of Sort 's methods are similar to Collection , except for the `add` method , which is
different. In Collection , data can be added to the beginning or end of a linked list, as long as it can be placed
in the `bin`. In Sort, when adding new data, it must determine the correct position of the data being added. For
example, if the list contains the values 3, 8, 10, and 35, adding 9 requires placing it between the nodes
containing 8 and 10. It cannot simply insert data before or after the linked list . Therefore, data added to the
Sort bin has the potential to be placed at the very beginning, in the middle, or at the end of the linked list ,
depending on its insertion position.
2.4.1 Inserting a node into the front of a Linked List .
To insert 2 into this bin or the Linked List below , because Sort sorts the data, the item 2 must be
inserted at the beginning of the Linked List. closs Mode

I object data.

mode nex

&

class Linked
implement called

first = well;

#- + เ ย
todoy
นรวม

is Empty
Size
รี
 #st เ ยงล

อย
ู
่ๆ จะเ อาเ ลขอะ
:: 4: มา แทรก ห
แทรก ห ง

5 P

ใ ้S chec

ขสเหต < ให
้
>เ อ นไปเร
ื

Create a node to store the value 2, then set the ` next` part of this new node to the address of the first
node, where the variable ` first` stores the value 2. The address is there; that is, this new node points to the
first node, which is the node that stores the value 3. Then, move the pointer " first" to point to the new node
instead by assigning a variable... First , store the address of the new node, which is node 2 . Address of node
3 That means this new node, which stores the value 2 , has become the first node of the Linked List.

#
M

1. setNextSt)

tsetnext ( +1

2.4.2 Inserting a new node into the center of a Linked List .

To insert the number 4 into this bin or the Linked List below , since Sort arranges the data by value,
the number 4 must be placed in the middle of the Linked List , between the node with the value 3 and the
node with the value 4. Link 2 L = new Link (((

2. add. ( 3)

1. add ( 5) ;
·
2. Add /3)
รี
ลั
น้
ช้
ลื
ำ
 public Void add ( Object &(

My node &= first ;

Mynode S = first;
Link 2 L = new Link (((
While (S. getNext 1) <d && SI = null (
<- add. ( 1)
S =
P = >j
S.
get Next () 2. add
/5) ;
·
- > o r
loop แ วน
2. Add /3)
=

#
ก บมมาตรง

cal!"
if (s #

getaut "best rathon แบบ ไ ่ อะไรก มา

return
n

<return ไ ่ อ ะไรไ ใน ro i

My node -+ = new
My nodeld, null);
fron
thadd
if JS = = = first) * coccision add uw

if = = =
first()
&#
o to setNext

าเ น first ส

· t = +, 5 ส บ-

else if ( = = = = null) // add end add หล

9. setNext ( +) ;

else { add กลาง

1. setNextSt)

t setnext ( +1
ซ้
ลั
ถ้
ด้
มี
ล้
มี
ลั
ม่
ป็
ลั
ม่
 Since we need to know the position of the new value to be inserted beforehand, a while loop is
used to move the pointer continuously until it finds a node with a value greater than the data to be inserted (in
the case of sorting from smallest to largest as in the example). This pointer is named cur1 , and a pointer,
cur2, follows closely behind to stop before cur1.
Initially, set the pointers cur1 and cur2 to point to the first node, i.e., set cur1 and cur2 equal to `first`, as
shown in the command and image below.

Move the cur1 pointer to a node with a value greater than the data to be entered, then move the
cur2 pointer. Coming one after another. It stops at the node preceding the node pointed to by cur1 , as shown
in the image below, using... The two statements below should be inside a while loop. See the `add ( Object
value )` method in the LinkedSort class.

Next, create a new node and store the value 4. Set the `next` section of the node `cur2` to the
address of the new node (i.e., point to the new node). Then, set the ` next` section of the new node to the
address of the node `cur1` (i.e., point to the node that `cur1` points to). In other words, insert the node
between node `cur2` and node `cur1` as shown in the image below using the command below.
2.4.3 Adding a new node to the end of a linked list .
To add the number 8 to this list (or linked list) , since Sort sorts the data, the number 8 must be
appended to the end of the linked list.

Initially, the pointers cur1 and cur2 point to the first node, i.e., set cur1 and cur2 equal to `first` , which
stores the address of the first node, as shown in the figure and the two commands below.

Because the while loop in the `add ( Object value )` method of the LinkedSort class below contains
the statements `cur2 = cur1; cur1 = [Link] ( ) ; ` , which moves the pointer of `cur1` to a node with a
value greater than the data to be inserted, but in the case of appending to the end of a Linked List , the data
to be inserted will have a value greater than all other values in the Linked List. Therefore, the pointer of `cur1`
stops at `null` , which is the `next` part of the last node, while the pointer of `cur2` stops before ` cur1` , i.e. , at
the last node, as shown in the three figures below.

Create a new node and store 8. Then , set the `next` parameter to ` cur1` , which means it should be
null. Then, set the `next` value of the last node pointed to by the cur2 pointer to the address of the new node;
that is, point to the new node, thus adding the new node to the end of the Linked List according to the
command and the image below.
2.4.4 Implement Sort using a Singly Linked List .
It's time to create a data structure using a Linked List. First, we need the Abstract Data Type of Sort ,
which is the Sort interface and has four methods.
public interface Sort {
public void add ( Object e ) ;
public void remove ( Object e ) ;
public boolean contains ( Object e ) ;
public boolean isEmpty ( ) ;
}
Before creating a data structure using a Linked List , you need a node class to create nodes to store
each piece of data.
Because a singly linked list is used to create the data structure, Sort uses the MyNode class to create each
node as before.

public class MyNode {

private Object data;
private MyNode next;

public MyNode ( Object obj, MyNode n ) {

data = obj;
next = n;
}
public void setNext ( MyNode n ) {
next = n;
 }
public void setData ( Object d ) {
data = d;
}
public MyNode getNext () {
return next;
}
public Object getData () {
return data;
}
}

Let's create a Sort data structure from the LinkedSort class below. Since it uses a singly linked list to
create data, like a Collection , most methods are implemented similarly, except for the add method, which
differs significantly between Sort and other data structures. And the Collection
- Starting with the constructor , which represents an empty data container, it has the same command as the
collection data structure : ` first = null ;`

- The `add ( Object value )` method differs because Collections can add data before or after the list, as long
as the data is added to the node. Sort, however , requires checking the index of the data to be added. For
example, if the list contains the 3, 8, 10, and 35 , adding 9 requires placing it between the nodes containing 8
and 10 ; it cannot be inserted before or after the list. Therefore, data added to a Sort node can be placed at
the very beginning, in the middle , or at the end of the linked list , as explained in sections 2.4.1-2.4.3 above .

- The method remove ( Object o ) is similar to The `remove` function of the `LinkedCollection` class is useful
because there are three ways to delete a node: the first node, the middle node, or the last node of the linked
list. The difference lies in how the pointer moves from `start` to the node containing the data to be deleted. In
a Collection , the data is not sorted, so you need to search for the data to be deleted from the first to the last
node of the linked list. In contrast, `sort` sorts the data in a given list. It's already a linked list. Therefore , if the
pointer moves from 'start' to a node with a value greater than the one to be deleted (if the data is sorted from
smallest to largest) and still doesn't find it, it means the desired item hasn't been found, so the pointer stops
moving. This means the search stops without needing to search to the last node. Linked List

- method The `contains ( Object o )` method in the `sort` data structure differs from the `contains` method of
the `collection` data structure only in how the pointer moves from ` start` to the desired node. When a node
with a value greater than the desired node is found (if the data is sorted from smallest to largest), the search
stops. This is the same reasoning as the `remove` method above.
- The `isEmpty ()` method is the same for both Collections and Sorts ; it simply checks if the `first` pointer
exists, even if there is no node to point to , or if `first = null` , meaning the collection is empty.
- An additional method not included in Sort ADT is the printlist() method . This method displays the current
contents of a linked list , from the first node to the last. It works by moving the pointer from the start node to
each node and printing the value of that node, repeating this process until the end of the linked list.

public class LinkedSort implements Sort {

private MyNode first;

public LinkedSort () { //Initialize empty bin

first = null;
}
public boolean isEmpty () { // Ask if the bucket is empty. If it is empty, then first = null
return first == null;
}
public void printList () { // Display all items in the Linked List on the screen
MyNode start = first;

while ( start != null ) {

System . out . print ( start . getData ()+ " \t " ) ;
start = [Link] ( ) ;
}
[Link] ( ) ;
System . out . println ("------------------------------------------------") ;
}

public void remove ( Object o ) { // Delete the node with the value o
if ( isEmpty ())
return;
else
System . out . println (" Remove Value : " + o ) ;

MyNode pre = null, start = first;

int a = ( Integer ) start . getData ( ) ;
int v = ( Integer ) o;
// The check where a<v is located means that if a node is found that is greater than the node being deleted, it
means the search is stopped.
while ( start . getNext () != null && !( start . getData (). equals ( o )) && ( a < v )) {
pre = start;
start = [Link] ( ) ;
a = ( Integer ) start . getData ( ) ;
}
if (!( start . getData (). equals ( o )))
System . out . println (" Not Found ") ;
else{
if ( start == first ) // Delete the first node of the Linked List
first = [Link] ( ) ;
else
[Link] ( [Link] ( )) ; // Delete the middle or last node of the Linked List
}
}
public boolean contains ( Object o ) {
MyNode start = first;
while ( start != null && !( start . getData (). equals ( o )))
{ Integer b = ( Integer ) o;
Integer a = ( Integer ) start . getData ( ) ;
if ( a > b ) // If a node with a data value greater than the one being searched for is found, stop and return from
the method.
{
return false;
}
start = [Link] ( )
}
return start != null;
}
public void add ( Object value ) {
if ( contains ( value )) { // If there is already data to be inserted into the Linked List
[Link] ( value + " has already existed in List ") ; // Indicates that it already exists
return; //Do not add , exit the method
}
else // Start adding
System . out . println (" Add Value : " + value )
if ( isEmpty ())
{ //If the data to be inserted is the first and only data of the Linked List
first = new MyNode ( value, first ) ;
}
else{
MyNode cur1 = first, cur2 = null;
int a = ( Integer ) cur1 . getData () ;
int v = ( Integer ) value;
if ( a > v ) { // Insert a new data element at the beginning of the linked list
first = new MyNode ( value, first ) ;
}
else{
cur1 pointer to the node with a data value greater than the data to be entered, and cur2 to the node before
cur1.
 while ( cur1 != null && a < v )
{
cur2 = cur1;
cur1 = [Link] ( ) ;
if ( cur1t != null )
{
a = ( Integer ) cur1 . getData () ;
}
// Close while
}
MyNode tmp = new MyNode ( value, cur1 ) ;
[Link] ( tmp ) ; // Insert a new node into the middle or end of the Linked List
}
}
}
}
The test class below is used to test the LinkedSort class. Data structures built using linked lists can
be checked for input, output, whether the specified data exists, or whether the data container is empty. Are all
these processes working correctly?

public class Main {

public static void main ( String [] args ) {
LinkedSort list = new LinkedSort ( ) ;
Integer ob1 = new Integer ( 20 ) ;
Integer ob2 = new Integer ( 30 ) ;
Integer ob3 = new Integer ( 15 ) ;
Integer ob4 = new Integer ( 25 ) ;
Integer ob5 = new Integer ( 30 ) ;
Integer ob6 = new Integer ( 40 ) ;
Integer ob7 = new Integer ( 28 ) ;
Integer ob8 = new Integer ( 35 ) ;
[Link] ( ob1 ) ;
[Link] ( ) ;
[Link] ( ob2 ) ;
[Link] ( ) ;
[Link] ( ob3 ) ;
[Link] ( ) ;
[Link] ( ob4 ) ;
[Link] ( ) ;
[Link] ( ob5 ) ;
[Link] ( ob6 ) ;
[Link] ( ) ;

System . out . println (" Is " + ob2 + " in the List? " ) ;
boolean a = list . contains ( ob2 ) ;
System . out . println ( a ) ;
System . out . println (" Is " + ob7 + " in the List? " ) ;
boolean b = list . contains ( ob7 ) ;
System . out . println ( b ) ;

[Link] ( ob3 ) ;
[Link] ( ) ;
list . remove ( ob4 ) ;
[Link] ( ) ;
list . remove ( ob8 ) ;
[Link] ( ) ;

}
}
 Chapter 4 trees
A tree is a data structure that stores individual data in nodes. The nodes are arranged like an inverted
tree, starting from the root and followed by children, down to the lowest node which has no children, called a
leaf. Trees have levels , starting from level 0 at the root , as shown in the diagram below.

The term "subtree" refers to both left and right subtrees. In the image above, the left subtree of node
1 is...

From the image above, the subtree to the right of node 1 is...
1713 4.1 Binary tree
A tree that can have a maximum of 2 offspring, meaning it has a 0, 1 , or 2 chance of producing offspring from
any node.
4.1.1 Tree nodes
A node consists of three parts:
- The data storage area is the top part of the image below.
- The area where the child's address is stored on the left, or the left pointer, is the bottom left part
of the image below.
- The area where the child's address is stored , or the right-hand pointer, is the bottom right corner
of the image below.

An example of a node that has no children is child 0.

You can see that the parts storing the addresses of the left and right children are null , meaning there
are no nodes to point to, as shown in the image below.

An example of a node with one child on the left.

 on the right that stores the child addresses is... Null means there is no node to point to. However, the
left side stores the address of the child node on the left, meaning there is a pointer to the left, as shown in the
image below.

An example of a node with one child to the right.

You can see that the part storing the address of the left child node is null , meaning there is no node
to point to. However, the right node stores the address of the right child node, indicating a pointer to the right,
as shown in the image below.

To create a tree node, you need a node class. The node class has three instance variables : data...
The `left` and `right` methods store the address of the left child node and the address of the right child node,
respectively. Therefore, there are 6 instance methods . Methods for retrieving data. ( Get ) and change the
new information. ( set ) on data , left pointer, and right pointer.
class
My Mode class BTNode

public class BTNode {

- >
publi c class tree

BTNode root,
private Object data; public Tree(){
root =
null; }
private BTNode left;
private BTNode right;

public BTNode ( Object obj, BTNode l, BTNode r ) {

 data = obj;
left = l;
right = r;
}
public void setLeft ( BTNode l ) {
left = l;
}
public void setRight ( BTNode r ) {
right = r;
}
public BTNode getLeft () {
return left;
}
public BTNode getRight () {
return right;
}
public Object getData () {
return data;
}
}

LV < Mr

4.2 Binary Search Tree RV > MU

It is a binary tree with the following conditions:

=

1. The child on the left must have a value less than the parent node.
2. The child on the right must have a value greater than the parent node.

An example of a binary search tree.

 The example below is not a binary search tree.

#while

if
Croot =Yu

%
retur

Because the child node on the right is not greater than the parent node. 5
6
4.2.1 Creating a Binary Search Tree public
void. Add ( Object d)

The process of creating a binary search tree. BTNode = new BTNode ( d, hull, null)
* อ>สร้างเป ็น No de

If the input data is:·8, 10, 1, 3, 9, 2, 4, 12 BTNode P, S = root

BTNode -+ = new
BENode ( 8, null, wull)
root = t
While ( S! = null

P= =
&

④ddS/ if ( d 8s. getDate()

roo

6 = 3.
getLett
·
else if / &> s. getData() (
· S= 3. gelRight (
"ี -

·ต else { t ("ช ไ ท ") d == [Link]

From the image above , since 10 is greater than 8 , it is connected as the right child of thereturn
node storing the
is = nuแล: )
value 8.
if Id > ↑. getData()) {
↑. set Left ( +'; }

else { 8. Set Right (+;

From the image above , since 1 is less than 8 , it is connected as the left child of the node storing the value 8.
้ำ
ำ
ม่
ต้
 From the image above, since 3 is less than 8 , the node traverses to the left of the node storing the
value 8. Upon encountering the node storing the value 1, it compares whether 3 is greater than or less than 1.
In reality, 3 is greater than 1 , so the node 3 is connected as a right child of the node storing the value 1.

From the image above, since 9 is greater than 8 , the node traverses to the right of the node storing
8. Upon encountering the node storing 10 , it compares whether 9 is greater than or less than 10. In reality, 9 ?
# recursive

is less than 10, so node 9 is connected to the left child of the node storing 10. public InO ( BTNode) {
" void

#23.59
if (r = = = null) return;

repetitionalStroke
Pure
a

els
10 8
root
no [Link]
Traversal
>
tree pre order
- ⑤ 3. 0.
P getData
Cr.
3. 0.
P getData
Cr.

A. # A % InO Cr.
get Right

-
In Order
InO Cr.
get Right
Pre
* A A
Pos A
5

&
A
roo

·
+

↑ Po
0
⑤

:Qing
9 10
3 ↓

1 A
#8 public int size (BT mode
r)
if Jr = = null) return #
1+ 1 + 1 = 3
8 1 3 2 10 9
else if Ir != null)

, \
· I size ( 8.
getleftll) +1 + size ( ro get Right());
-

/ ·
& ป
ดั
 #
#

#
S

public boolean contain

/object ef

BTuodes=

·to
root ;

while ( S! = null)
#

%
if 12 < 6. getData 1)
1 2
S = so
getLeft 1); 3)

else if 12 > s
getData 1. Set Right (null)

5 = S.
getRight();
Piset left (null)
100 el s Ne = S. getData 11,
root = wel
& retur true

return false 11 ออก ลุ

if ( S = = = root)

root = hell

/
}else if (paget Right 1) = = 3) {
9. Set Right ( hull);

public void
remove ( object a) 3 else { 1) ( pagetleft 1) == S

- ไห ht
tinal
Post
ก

- าไ ี I retur nไม
"
> ไม

4 ไ ปช
ี แม่

http
in
we want

ก
ก

ก
ก
& order

sirinSite ·SO
BTnodes : root

while ( S! ==null) "

&
P= S

if /2 < getDatall)S.

3 = S. getleftl);
alse if
Je > s.
getDatall) ก if (S. getleft 1) != nell)

↓I
S = 3. get Right(); if ( S = = root

alse }

ไ
#k;
post .ent
!
-
if 28 = =
wull) {

/ไม
print "ไม่เจอ !ไ ง

return;
-check
·Prop setheft
(

ไ ม กทม
7 else 11 100
ก
! { if16:
=200

if S. getleft)) = = null &&

#
sgetlight = = null) 11 ก-
I rootsssthigh-!--

superh
else se

( posetRightssohtt
ase Pent
# sort -
↓

↑ yelse
มี
มี
ลู
ลู
ทีี่
ม่
ลู
มี
ลู
มี
ก็
ลู
มี
ซ้
ถ้
ม่
ลู
ทั้
ชี
 3) 3

+- Dimax
left
-> าง: หา m
Lef

- get min, ma

roo

S Level. - าไม่ม ีท ออกเ ลม อ

=>

·
int size ( Thode 2)
if (2 = = null) return ·"
ese

⑤
14
max/ level ( rogetleft()))
level [Link]())

:50
↑

-root & 1#

&
2 3
5
· 1+ max#SO), (

-ร
↑

#
-I
It imall, #Mul
le

⑧ ·- I

1 + Max /level 2) ,Level (nu11)

↓ -I -

max ( Level (hull), level snull)

14

เ อกต
ว
ที่
ตั
ลื
คื
ถ้
ถ้
 From the image above , since 2 is less than 8 , the node traverses to the left of the node storing 8.
Upon encountering the node storing 1 , it compares whether 2 is greater than or less than 1. Since 2 is greater
than 1 , the node traverses to the right of node 1, reaching node 3. It compares again, and since 2 is less than
เร

3 , it connects node 2 as a left child of the node storing 3.

From the image above , since 4 is less than 8 , the node traverses to the left of the node storing 8.
Upon encountering the node storing 1 , it compares whether 4 is greater than or less than 1. Since 4 is greater
than 1 , the node traverses to the right of node 1, reaching node 3. It compares again, and since 4 is greater
than 3 , it connects node 4 as a right child of the node storing 3.

From the image above , since 12 is greater than 8 , we traverse to the right of the node storing the
value 8. When we encounter the node storing the value 10 , we compare whether 12 is greater than or less
than 10. In reality, 12 is greater than 10, so we proceed to the node containing 12. Connect it as the right child
of the node that stores the value 10.
4.2.2 Deleting Nodes in a Binary Search Tree
Since a binary search tree has a maximum of 2 children , the node to be removed has a chance of
having 0 children, 1 child , or 2 children .
Case of deleting a node that has 0 children.
- If the node to be deleted is the root.

When a node is deleted, the root becomes null , meaning there are no nodes left on the tree, as shown in the
command and image below.

- If the node to be deleted is the left child of the parent.

Delete by setting the left pointer of the parent to null ; that is, the parent will no longer have any children on its
left, as shown in the command and image below.
- If the node to be deleted is the right child of the parent.

Delete by setting the right pointer of the parent to null , meaning the parent will no longer have any children to
its right, as shown in the command and image below.

Case of deleting a node that has 1 child.

If the node to be deleted is the root.
-If the node to be deleted is the root and has one child to its right.
Deleted by set. The root directory becomes the right-hand child of the directory you want to delete, as shown
in the command and image below.

- If the node to be deleted is the root and has one child to its left.

Deleted by set. The root directory becomes the left-hand child of the directory you want to delete, as shown in
the command and image below.

If the node to be deleted is the left child of the parent.

In the case where the node to be deleted is the left child of the parent, but there is one child on the right, as
shown in the image below.
To delete, set the left pointer of the parent node of the node to be deleted to the right child node of the node
to be deleted, as shown in the command and image below.

- If the node to be deleted is the left child of the parent, but there is one child on the left side as
well.

To delete, set the left pointer of the parent node of the node to be deleted to the left child node of the node to
be deleted, as shown in the command and image below.
If the node to be deleted is the right child of the parent.
- If the node to be deleted is the right child of the parent, but there is one child on the right side of
that node.

To delete, set the right pointer of the parent node of the node to be deleted to the right child node of the node
to be deleted, as shown in the command and image below.
 -
- If the node to be deleted is the right child of the parent, but there is one child on the left.

To delete, set the right pointer of the parent node of the node to be deleted to the left child node of the node
to be deleted, as shown in the command and image below.
If the node to be deleted has 2 children.
two ways to do it :
1. Select the node with the highest value that is less than the node you want to delete; that is, the
bottom right node of the left subtree of the node you want to delete.
2. Select the node with the smallest value that is greater than the node you want to delete; that is, the
bottom left node of the right subtree of the node you want to delete.
Once you have the node from step 1 or 2 , overwrite the value of the node you want to delete with the
value of one of those nodes. Then, delete the node obtained from step 1 or 2 .
Below is a demonstration of deletion using only method 1.
To delete a node that stores the value 31 and has two children , the following steps would be taken:
1. Select the node with the highest value that is less than the node you want to delete. This means
selecting the bottom right node of the left subtree of the node you want to delete; that is, the
node that stores the value 30.
2. the value in node 31 with the value 30.
3. Delete the original node that stored the value 30.
Move the `start` pointer to the node you want to delete, and the ` pre` pointer to the parent node of the node
you want to delete, as shown in the image below.
Set the pre2 pointer to the same location as the start pointer , and the cur pointer to the root of the left
subtree, as shown in the command and image below.
Then, move the cur pointer forward to the bottom right node, with the pre2 pointer following, as shown in the
command and image below.

Then, move the cur pointer towards the bottom right node, with the pre2 pointer following. As per the
instructions and image below.
cur pointer has now reached the largest node that is less than the node to be deleted, specifically the node
containing the value 30 , as shown in the command and image below.
Then, the value in the node pointed to by `cur` overwrites the value in the node `start` , which is the node
intended to be deleted, as shown in the command and image below.
Next, delete the original node that stored the value 30 by setting the right pointer of the parent node of node
30 , which is pointed to by the pre2 pointer, to... The address of the left child node of node 30 is shown in the
figure below. Because node 30 is the bottom right node, it cannot have a child to the right. As per the
instructions and image below.
Example 2 : Case where there is no bottom right node in the left subtree.
Set the pre2 pointer to the same location as the start pointer , and set the cur pointer to the root of the left
subtree, as shown in the image below.

Since there is no right node to the cur pointer, it means that the cur pointer stores the largest value in
the left subtree of the node to be deleted, which is the node that the start pointer is pointing to. Then, the value
in the node pointed to by cur overwrites the value in the node that starts , which is the node intended to be
deleted, as shown in the image below. That is, node 4 is overwritten with the value 2, as shown in the image
below.

Then, delete node 2 that the cur pointer is pointing to using the command. [Link] ( [Link] ( ) ) ;
results in the image below .
4.3 Tree traversal
There are 3 types .
1. Inorder means traversing to... Left subtree, Root, Right subtree, in that order.
2. Preorder means traversing the Root, Left subtree, and Right subtree in that order.
3. Postorder is a navigation tool that goes to... Left subtree, Right subtree, Root, in that order.
Example 1

Example 2
Example 3

4.4 Creating data structures using ... Binary Search Tree

Before creating a data structure using a Binary Search Tree, a node class is needed to create nodes to store
each piece of data.
Since a Binary Search Tree is a binary tree , it has the characteristics of nodes and node classes as described
in section 4.1.1.
public class BTNode {
private Object data;
private BTNode left;
private BTNode right;

public BTNode ( Object obj, BTNode l, BTNode r ) {

data = obj;
left = l;
right = r;
}
public void setLeft ( BTNode l ) {
left = l;
}
public void setRight ( BTNode r ) {
right = r;
}
public BTNode getLeft () {
return left;
}
public BTNode getRight () {
return right;
}
public Object getData () {
return data;
}
}

Now let's create the data structure from the BinarySearchTree class below, using Binary Search Tree
to construct the data structure.
- Starting with the constructor , which represents an empty data container, the command is `root = null; `,
meaning there isn't even a root node.
- The `add ( Object e )` method adds a node with the value 'e' to the tree. First, we need to determine the
location of 'e' in the tree. The `while` loop within the `add` method handles this. The `start` pointer initially
points to the root and moves down until it finds the correct position. The `while` loop checks whether the
added value is greater than or less than the value of the node in the tree indicated by the ` start` pointer. If the
value at the node pointed to by 'pre' is greater than the value at the node pointed to by 'pre', the ' start ' pointer
moves to the right. If the value at the node pointed to by 'pre' is less than the value at the node pointed to by
'pre' , the new node will connect to it as a child. After exiting the while loop , only the node pointed to by 'pre'
is returned (the node the new node will connect to as a child). However, it's not yet clear whether the new
node will be a right or left child. Therefore, an 'if' statement is used to determine if the value at the node pointed
to by 'pre' is greater than or less than the new value being entered. If the new value is greater than the value
at the node pointed to by ' pre' , the new node will connect as a right child of the node pointed to by 'pre' .
Conversely, if the new value is less than the value at the node pointed to by 'pre' , the new node will connect
as a left child of the node pointed to by 'pre' .
- The `contains ( Object e )` method moves the `start` pointer to the desired node. It's similar to the `add`
method 's `while` loop , where the `start` pointer initially points to the root and moves down until it finds the
desired value. Within the `while` loop , it checks if the value of `e` is greater than or less than the value of the
node in the tree that the ` start` pointer is pointing to. If it's greater, the `start` pointer moves to the right; if it's
less, it moves to the left. If the ` start` pointer stops at `null` , it means the desired value wasn't found.
- The `isEmpty ()` method checks if the root pointer contains no nodes to point to, or if ` root = null` means the
container is empty.
- The `printTree()` method is used to display the current data in the tree from the first node to the last node.
This method prints the value of each node in three ways, depending on tree traversal : Preorder, InOrder, or
PostOrder.
- The getMin () method returns the smallest value in the tree by having the start pointer navigate to the bottom
left node of the tree, which is the node with the smallest value.
The getMax () method returns the largest value in the tree by having the start pointer navigate to the bottom
right node of the tree, which is the node with the largest value.

public class BinarySearchTree {

private BTNode root;

 Interface

private int size;

public BinarySearchTree () { //Start at an empty bin -class BST

-rop

root = null; -ad

EU

size = 0;
-print
For
}
curtai

public int size () { publi

boolean is Empty() {
return root = = well;
return size;
} public void. In Order ( BTS node r)
if Ir! = null)
public boolean isEmpty () { //Is this bucket empty? In Order Cr.
get Left( 1)
return root == null; // Checking if the root is equal to null . 3. 0. P. Cr. get data(1)
In Order Cr. get Right())
}

public Object contains ( Object e ) { //Does this container contain data e ?

BTNode start;
start = root;
int value = ( Integer ) e;

while ( start != null ) {

int BTNode = ( Integer ) start . getData ( ) ;
if ( BTNode == value )
return true;
else{
if ( BTNode > value ) // If the value to be entered is less than the current node pointed to by start.
start = [Link] ( ) ; // Move start down to the left
else //If the value to be entered is greater than the current node that start is pointing to.

start = [Link] ( ) ; // Move start down to the right

}
}
return false; // No data found
}

public void add ( Object e ) {

if ( e == null )
return;
BTNode start = root, pre = null;
BTNode tmp = new BTNode ( e,null,null ) ; // Create a new node that stores the value e
int value = ( Integer ) e;

if ( root == null ) { // If the bin is empty, any new node entering will immediately become the root of the tree.
root = tmp;
size ++ ;
}

else{
while ( start != null ) {
pre = start;
int BTNode = ( Integer ) start . getData ( ) ;
if ( BTNode == value ) {
System . out . println (" Object : " + e +" has existed in the tree ." ) ;
start = null;
return;
}
else{
if ( BTNode > value )
start = [Link] ( ) ;
else
start = start . getRight ( ) ;
}
// When the while loop ends This will create the parent node of the new node, which will have a `pre` pointer
pointing to it.
int curNode = ( Integer ) pre . getData ( ) ;
if ( curNode > value ) { // If the new node has a value less than the node that pre points to, the new node
becomes the left child.
[Link] ( tmp ) ;
size ++ ;
}
else if ( curNode < value ) { // If the new node has a value greater than the pre -curNode } The indicator points
the new node to be its right child.
[Link] ( tmp ) ;
size ++ ;
}
}
} // end of Method ddd

public Object getMin () {

BTNode start = root;
if ( start == null )
return null;
while ( start . getLeft () != null ) { // Move the start pointer to the bottom left node of the tree
start = [Link] ( ) ;
}
return [Link] ( ) ; // return the value of the smallest node in the tree
}

public Object getMax () {

BTNode start = root;
if ( start == null )
return null;
while ( start . getRight () != null ) { // Move the start pointer to the bottom right node of the tree
start = start . getRight ( ) ;
}
return [Link] ( ) ; // return the value of the node with the highest value in the tree
}

public void printTree () {

BTNode r = root;
if ( isEmpty ()) // If the bin is empty, nothing can be printed .
System . out . println (" Tree is empty .") ;

System . out . println (" Preorder ") ;

preOrder ( r ) ; // Call the preOrder method to print the tree by passing the root r of the tree into the method .
[Link] ( ) ;

System . out . println (" Inorder " ) ;

inOrder ( r ) ; // Call the inOrder method to print the tree by passing the root r of the tree into the method .
[Link] ( ) ;
System . out . println (" Postorder ") ;
postOrder ( r ) ; // Call the postOrder method to print the tree by passing the root r of the tree into the method .
[Link] ( ) ;
}
public void preOrder ( BTNode r ) { // Print tree using preOrder
if ( r != null ) {
System . out . print ( r . getData ()+ " \t " ) ;
preOrder ( [Link] ( ) ) ;
preOrder ( r . getRight () ) ;
}
}
public void inOrder ( BTNode r ) { // Printing the tree using inOrder
if ( r != null ) {
inOrder ( [Link] ( ) ) ;
System . out . print ( r . getData ()+ " \t " ) ;
inOrder ( [Link] ( ) ) ;
}
}
public void postOrder ( BTNode r ) { // Printing the tree postOrder
if ( r != null ) {
postOrder ( r . getLeft () ) ;
postOrder ( r . getRight () ) ;
System . out . print ( r . getData () + " \t " ) ;
}
}
// End of BinarySearchTree class
The `Main` class below is used to test the `BinarySearchTree` class , a data structure built using
Binary Search Tree. It checks whether data is inserted, removed, whether the specified data exists, or whether
the data container is empty, and whether all of this works correctly.

public class Main {

public static void main ( String [] args ) {
BinarySearchTree BST = new BinarySearchTree ( ) ;
Integer ob1 = new Integer ( 9 ) ;
Integer ob2 = new Integer ( 2 ) ;
Integer ob3 = new Integer ( 12 ) ;
Integer ob4 = new Integer ( 1 ) ;
Integer ob5 = new Integer ( 5 ) ;
Integer ob6 = new Integer ( 10 ) ;
Integer ob7 = new Integer ( 15 ) ;
Integer ob8 = new Integer ( 20 ) ;
[Link] ( ob1 ) ;
[Link] ( ob2 ) ;
[Link] ( ob3 ) ;
[Link] ( ob4 ) ;
[Link] ( ob5 ) ;
[Link] ( ob6 ) ;
[Link] ( ob7 ) ;
BST . printTree () ;
System . out . println (" Size : " + BST . size ()) ;
System . out . println (" Min : " + BST . getMin ()) ;
System . out . println (" Max : " + BST . getMax ()) ;
System . out . println (" Is " + ob3 + " in the tree? " + " \t " + BST . contains ( ob3 )) ;
System . out . println (" Is " + ob8 + " in the tree? " + " \t " + BST . contains ( ob8 )) ;
}
}

Output
run :
Preorder
9 2 1 5 12 10 15
Inorder
1 2 5 9 10 12 15
Postorder
1 5 2 10 15 12 9
Size : 7
Min : 1
Max : 15
Is 12 in the tree? True
Is 20 in the tree? False
[Link] ( ob1 ) ;
[Link] ( ob2 ) ;
[Link] ( ob3 ) ;
[Link] ( ob4 ) ;
[Link] ( ob5 ) ;
[Link] ( ob6 ) ;
[Link] ( ob7 ) ;
BST . printTree () ;
System . out . println (" Size : " + BST . size ()) ;
System . out . println (" Min : " + BST . getMin ()) ;
System . out . println (" Max : " + BST . getMax ()) ;
System . out . println (" Is " + ob3 + " in the tree? " + " \t " + BST . contains ( ob3 )) ;
System . out . println (" Is " + ob8 + " in the tree? " + " \t " + BST . contains ( ob8 )) ;
}
}

Output
run :
Preorder
9 2 1 5 12 10 15
Inorder
1 2 5 9 10 12 15
Postorder
1 5 2 10 15 12 9
Size : 7
Min : 1
Max : 15
Is 12 in the tree? True
Is 20 in the tree? False