Bạn đang xem bài viết Duyệt Cây Trong Cấu Trúc Dữ Liệu Và Giải Thuật được cập nhật mới nhất trên website Nhatngukohi.edu.vn. Hy vọng những thông tin mà chúng tôi đã chia sẻ là hữu ích với bạn. Nếu nội dung hay, ý nghĩa bạn hãy chia sẻ với bạn bè của mình và luôn theo dõi, ủng hộ chúng tôi để cập nhật những thông tin mới nhất.
Duyệt cây là gì?
Duyệt cây là một tiến trình để truy cập tất cả các nút của một cây và cũng có thể in các giá trị của các nút này. Bởi vì tất cả các nút được kết nối thông qua các cạnh (hoặc các link), nên chúng ta luôn luôn bắt đầu truy cập từ nút gốc. Do đó, chúng ta không thể truy cập ngẫu nhiên bất kỳ nút nào trong cây. Có ba phương thức mà chúng ta có thể sử dụng để duyệt một cây:
Duyệt tiền thứ tự (Pre-order Traversal)
Duyệt trung thứ tự (In-order Traversal)
Duyệt hậu thứ tự (Post-order Traversal)
Nói chung, chúng ta duyệt một cây để tìm kiếm hay là để xác định vị trí phần tử hoặc khóa đã cho trong cây hoặc là để in tất cả giá trị mà cây đó chứa.
Duyệt trung thứ tự trong cây nhị phân
Trong cách duyệt này, cây con bên trái được truy cập đầu tiên, sau đó là nút gốc và sau đó là cây con bên phải. Bạn nên luôn luôn ghi nhớ rằng mỗi nút đều có thể biểu diễn một cây con.
Nếu một cây nhị phân được duyệt trung thứ tự, kết quả tạo ra sẽ là các giá trị khóa được sắp xếp theo thứ tự tăng dần.
Ở hình ví dụ minh họa trên, A là nút gốc. Với phương thức duyệt trung thứ tự, chúng ta bắt đầu từ nút gốc A, di chuyển tới cây con bên trái B của nút gốc. Tại đây, B cũng được duyệt theo cách thức duyệt trung thứ tự. Và tiến trình tiếp tục cho đến khi tất cả các nút đã được truy cập. Kết quả của cách thức duyệt trung thứ tự cho cây trên sẽ là:
D → B → E → A → F → C → G Giải thuật cho cách duyệt trung thứ tự
Duyệt cho tới khi tất cả các nút đều được duyệt:Bước 1: Duyệt các cây con bên trái một cách đệ qui Bước 2: Truy cập nút gốc Bước 3: Duyệt các cây con bên phải một cách đệ quiDuyệt tiền thứ tự trong cây nhị phân
Trong cách thức duyệt tiền thứ tự trong cây nhị phân, nút gốc được duyệt đầu tiên, sau đó sẽ duyệt cây con bên trái và cuối cùng sẽ duyệt cây con bên phải.
Ở hình ví dụ minh họa trên, A là nút gốc. Chúng ta bắt đầu từ A, và theo cách thức duyệt tiền thứ tự, đầu tiên chúng ta truy cập chính nút gốc A này và sau đó di chuyển tới nút con bên trái B của nó. B cũng được duyệt theo cách thức duyệt tiền thứ tự. Và tiến trình tiếp tục cho tới khi tất cả các nút đều đã được truy cập. Kết quả của cách thức duyệt tiền thứ tự cây này sẽ là:
A → B → D → E → C → F → G Giải thuật cho cách duyệt tiền thứ tự
Duyệt cho tới khi tất cả các nút đều được duyệt:Bước 1: Truy cập nút gốc Bước 2: Duyệt các cây con bên trái một cách đệ qui Bước 3: Duyệt các cây con bên phải một cách đệ quiDuyệt hậu thứ tự trong cây nhị phân
Trong cách thức duyệt hậu thứ tự trong cây nhị phân, nút gốc của cây sẽ được truy cập cuối cùng, do đó bạn cần chú ý. Đầu tiên, chúng ta duyệt cây con bên trái, sau đó sẽ duyệt cây con bên phải và cuối cùng là duyệt nút gốc.
Ở hình ví dụ minh họa trên, A là nút gốc. Chúng ta bắt đầu từ A, và theo cách duyệt hậu thứ tự, đầu tiên chúng ta truy cập cây con bên trái B. B cũng được duyệt theo cách thứ duyệt hậu thứ tự. Và tiến trình sẽ tiếp tục tới khi tất cả các nút đã được truy cập. Kết quả của cách thức duyệt hậu thứ tự của cây con trên sẽ là:
D → E → B → F → G → C → A Giải thuật cho cách duyệt hậu thứ tự
Duyệt cho tới khi tất cả các nút đều được duyệt:Bước 1: Duyệt các cây con bên trái một cách đệ qui Bước 2: Duyệt các cây con bên phải một cách đệ qui Bước 3: Truy cập nút gốc.Theo Tutorialspoint
Bài trước: Giải thuật tìm kiếm theo chiều rộng
Bài tiếp: Cây tìm kiếm nhị phân (Binary Search Tree)
Cấu Trúc Dữ Liệu Và Giải Thuật (Data Structure And Algorithms): Cấu Trúc Dữ Liệu Là Gì?
Cấu trúc dữ liệu và giải thuật (Data Structure and Algorithms): Cấu trúc dữ liệu là gì?
Khái niệm cấu trúc dữ liệu (Data Structure)
Cấu trúc dữ liệu (Data Structure) là gì?
Với các sinh viên chuyên nghành tin học thì cụm từ Cấu trúc dữ liệu (Data Structure) không còn là xa lạ. Đây là một môn học bắt buộc và sẽ là thực sự khó cho bất kỳ sinh viên nào nếu không có sự chuẩn bị kỹ lưỡng và dành cách tiếp cận tích cực cho môn học này. Vậy Cấu trúc dữ liệu là gì?
Cấu trúc dữ liệu và giải thuật
Cấu trúc dữ liệu và giải thuật (Data Structure and Algorithms): Cài đặt môi trường trong cấu trúc dữ liệu
Cấu trúc dữ liệu là gì?
Cấu trúc dữ liệu là cách lưu trữ, tổ chức dữ liệu có thứ tự, có hệ thống để dữ liệu có thể được sử dụng một cách hiệu quả.
Interface: Mỗi cấu trúc dữ liệu có một Interface. Interface biểu diễn một tập hợp các phép tính mà một cấu trúc dữ liệu hỗ trợ. Một Interface chỉ cung cấp danh sách các phép tính được hỗ trợ, các loại tham số mà chúng có thể chấp nhận và kiểu trả về của các phép tính này.
Implementation (có thể hiểu là sự triển khai): Cung cấp sự biểu diễn nội bộ của một cấu trúc dữ liệu. Implementation cũng cung cấp phần định nghĩa của giải thuật được sử dụng trong các phép tính của cấu trúc dữ liệu.
Đặc điểm của một Cấu trúc dữ liệu
Chính xác: Sự triển khai của Cấu trúc dữ liệu nên triển khai Interface của nó một cách chính xác.
Độ phức tạp về thời gian (Time Complexity): Thời gian chạy hoặc thời gian thực thi của các phép tính của cấu trúc dữ liệu phải là nhỏ nhất có thể.
Độ phức tạp về bộ nhớ (Space Complexity): Sự sử dụng bộ nhớ của mỗi phép tính của cấu trúc dữ liệu nên là nhỏ nhất có thể.
Tại sao Cấu trúc dữ liệu là cần thiết?
Ngày nay, các ứng dụng ngày càng phức tạp và lượng dữ liệu ngày càng lớn với nhiều kiểu đa dạng. Việc này làm xuất hiện 3 vấn đề lớn mà mỗi lập trình viên phải đối mặt:
Tìm kiếm dữ liệu: Giả sử có 1 triệu hàng hóa được lưu giữ vào trong kho hàng hóa. Và giả sử có một ứng dụng cần để tìm kiếm một hàng hóa. Thì mỗi khi thực hiện tìm kiếm, ứng dụng này sẽ phải tìm kiếm 1 hàng hóa trong 1 triệu hàng hóa. Khi dữ liệu tăng lên thì việc tìm kiếm sẽ càng trở lên chậm và tốn kém hơn.
* Tốc độ bộ vi xử lý: Mặc dù bộ vi xử lý có tốc độ rất cao, tuy nhiên nó cũng có giới hạn và khi lượng dữ liệu lên tới hàng tỉ bản ghi thì tốc độ xử lý cũng sẽ không còn được nhanh nữa.
Đa yêu cầu: Khi hàng nghìn người dùng cùng thực hiện một phép tính tìm kiếm trên một Web Server thì cho dù Web Server đó có nhanh đến mấy thì việc phải xử lý hàng nghìn phép tính cùng một lúc là thực sự rất khó.
Để xử lý các vấn đề trên, các cấu trúc dữ liệu là một giải pháp tuyệt vời. Dữ liệu có thể được tổ chức trong cấu trúc dữ liệu theo một cách để khi thực hiện tìm kiếm một phần tử nào đó thì dữ liệu yêu cầu sẽ được tìm thấy ngay lập tức.
Độ phức tạp thời gian thực thi trong cấu trúc dữ liệu và giải thuật
Có 3 trường hợp thường được sử dụng để so sánh thời gian thực thi của các cấu trúc dữ liệu khác nhau:
Trường hợp xấu nhất (Worst Case): là tình huống mà một phép tính của cấu trúc dữ liệu nào đó tốn thời gian tối đa (thời gian dài nhất). Ví dụ với ba số 1, 2, 3 thì nếu sắp xếp theo thứ tự giảm dần thì thời gian thực thi sẽ là dài nhất (và đây là trường hợp xấu nhất); còn nếu sắp xếp theo thứ tự tăng dần thì thời gian thực thi sẽ là ngắn nhất (và đây là trường hợp tốt nhất).
Trường hợp trung bình (Average Case): miêu tả thời gian thực thi trung bình một phép tính của một cấu trúc dữ liệu.
Trường hợp tốt nhất (Best Case): là tình huống mà thời gian thực thi một phép tính của một cấu trúc dữ liệu là ít nhất. Ví dụ như trên.
Thuật ngữ cơ bản trong Cấu trúc dữ liệu
Dữ liệu: Dữ liệu là các giá trị hoặc là tập hợp các giá trị.
Phần tử dữ liệu: Phần tử dữ liệu là một đơn vị đơn lẻ của giá trị.
Các phần tử nhóm: Phần tử dữ liệu mà được chia thành các phần tử con thì được gọi là các phần tử nhóm.
Các phần tử cơ bản: Phần tử dữ liệu mà không thể bị chia nhỏ thành các phần tử con thì gọi là các phần tử cơ bản.
Thuộc tính và Thực thể: Một thực thể là cái mà chứa một vài thuộc tính nào đó, và các thuộc tính này có thể được gán các giá trị.
Tập hợp thực thể: Các thực thể mà có các thuộc tính tương tự nhau thì cấu thành một tập hợp thực thể.
Trường: Trường là một đơn vị thông tin cơ bản biểu diễn một thuộc tính của một thực thể.
Bản ghi: Bản ghi là một tập hợp các giá trị trường của một thực thể đã cho.
File: Là một tập hợp các bản ghi của các thực thể trong một tập hợp thực thể đã cho.
Cấu Trúc Dữ Liệu Và Giải Thuật: Ngăn Xếp (Stack) Trong Swift
1. Ngăn xếp(stack) là gì
Ngăn xếp là 1 dạng đặc biệt của danh sách liên kết mà việc bổ sung hay loại bỏ 1 phần tử đều thực hiện ở 1 đầu của danh sách gọi là đỉnh.
Ngăn xếp có 2 thao tác cơ bản: thêm phần tử vào được gọi là push và loại bỏ phần tử được gọi là pop.
Việc loại bỏ phần tử sẽ tiến hành loại bỏ phần tử mới nhất được đưa vào danh sách, chính vì tính chất này mà ngăn xếp còn được gọi là kiểu dữ liệu LIFO(last in first out – Vào sau ra trước)
2. Khởi tạo stack
2.1 . Định nghĩa kiểu dữ liệu stack
Vì stack là 1 dạng đặc biệt của danh sách liên kết nên ta có thể dùng kiểu dữ liệu Node đã trình bày ở bài danh sách liên kết để biểu diễn kiểu dữ liệu của stack
1
2
3
4
5
6
var
key
:
T
!
var
next
:
Node
?
}
Định nghĩa 1 class Stack với kiểu dữ liệu generic T và 1 node trên cùng gọi là top
1
2
3
4
5
}
2.2. Thêm 1 phần tử vào ngăn xếp (push)
Kiểm tra xem ngăn xếp có nil không, nếu nil thì gán đỉnh ngăn xếp vào phần tử muốn thêm vào.
Nếu đỉnh ngăn xếp không nil, tạo 1 nút mới, gán phần tử muốn thêm vào nút đó, gán đỉnh ngăn xếp vào nút vừa tạo.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func
push
(
key
:
T
)
{
// neu ngan xep chua co dinh
if
top
==
nil
{
}
// neu dinh ngan xep rong
if
top
.
key
==
nil
{
top
.
key
=
key
return
}
else
{
// khong thi tao 1 nut moi roi gan nut do vao dinh
newNode
.
key
=
key
newNode
.
next
=
top
top
=
newNode
}
}
2.3. Lấy 1 phần tử ra khỏi danh sách(pop)
Kiểm tra danh sách đỉnh có rỗng không, nếu rỗng thì kết thúc.
Nếu đỉnh danh sách không rỗng, kiểm tra nút đỉnh trỏ đến có rỗng không nếu rỗng thì gán đỉnh danh sách bằng nil( trường hợp danh sách chỉ có 1 phần sau khi lấy 1 phần tử ra thì danh sách trở thành rỗng), còn không gán đỉnh của danh sách vào nút tiếp theo.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// kiem tra xem dinh danh sach co rong khong
// neu rong thi ket thuc
guard
let
popItem
=
top
.
key
else
{
return
}
// kiem tra xem nut tiep theo cua dinh co rong khoong
if
let
nextNode
=
top
.
next
{
top
=
nextNode
}
else
{
top
=
nil
}
return
popItem
}
2.4. Xem phần tử đầu danh sách
Kiểm tra xem đỉnh của danh sách có rỗng không, nếu rỗng thì trả về nil còn không trả về giá trị của đỉnh danh sách.
1
2
3
4
5
6
7
8
9
10
11
12
// kiem tra xem dinh dach sach co rong khong
guard
let
topItem
=
top
.
key
else
{
// neu rong thi tra ve nil
return
nil
}
// con khong tra ve gia tri dinh danh sach
return
topItem
}
2.5. Test thử danh sách
2.5.1. Test build stack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func
buildStack
(
)
{
let
numberList
=
[
1
,
4
,
7
,
9
,
10
,
12
,
20
]
for
number
in
numberList
{
stack
.
push
(
number
)
}
printStack
(
)
}
func
printStack
(
)
{
var
top
=
stack
.
top
(
top
.
key
)
while
top
.
next
!=
nil
{
top
=
top
.
next
(
top
.
key
)
}
}
2.5.2. Test push stack
1
2
3
4
5
6
7
func
pushStack
(
)
{
stack
.
push
(
40
)
printStack
(
)
}
2.5.3 Test pop stack
1
2
3
4
5
6
func
popStack
(
)
{
let
item
=
stack
.
pop
(
)
(
item
)
}
3. Một số ứng dụng của ngăn xếp
3.1. Đảo ngược xâu ký tự
Bài toán đảo ngược xâu ký tự yêu cầu hiển thị các ký tự của 1 xâu ký tự theo chiều ngược lại.
Ký tự cuối cùng của xâu sẽ được hiển thị trước, tiếp theo là ký tự sát ký tự cuối … và ký tự đầu tiên sẽ được hiển thị đầu tiên.
Để giải quyết bài toán, ta chỉ cần duyệt từ đầu đến cuối xâu, lần lượt cho các ký tự vào ngăn xếp.
Khi đó, các ký tự đầu tiên sẽ vào trước, tiếp theo đến ký tự thứ 2 … ký tự cuối cùng vào sau cùng. Sau khi đã cho toàn bộ ký tự của xâu vào ngăn xếp, lần lượt lấy các phần tử ra khỏi ngăn xếp và hiển thị lên màn hình.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
for
s
in
stringInput
.
characters
{
stringStack
.
push
(
String
(
s
)
)
}
var
newString
=
“”
var
item
=
stringStack
.
top
newString
+=
item
.
key
while
item
.
next
!=
nil
{
item
=
item
.
next
newString
+=
item
.
key
}
return
newString
}
3.2. Tính giá trị biểu thức dạng hậu tố
3.2.1. Bài toán
Một biểu thức toán học thông thường bao gồm các toán tử: + – * / , các toàn hạng và dấu ngoặc cho biết thứ tụ tính toán.
Chẳng hạn 1 biểu thức toán học: (3 * (((5 – 2) * (7 + 1)) – 6)) Như chúng ta đã thấy trong biểu thức trên , các toán tử bao h cũng nằm giữa 2 toàn hạng. Do vậy, cách viết trên được gọi là cách viết trung tố (infix). Để tính toán giá trị biểu thức trên, ta phải tính toán giá trị các phép toán trong ngoặc trước. Đôi khi ta cần lưu các kết quả tính toán này như 1 kết quả trung gian, sau đó sử dụng chúng như toán hạng tiếp theo. Ví dụ ở biểu thức trên, đầu tiên ta tính 5 – 2 = 3, lưu kết quả này lại. Trong các biểu thức dạng này, vị trí dấu ngoặc rất quan trọng. Nếu vị trí các dấu ngoặc thay đổi thì giá trị biểu thức cũng thay đổi theo. Đối với con người, cách trình bày biểu thức toán học theo dạng này có vẻ như là hợp lý nhất, nhưng đối với máy tính, việc tính toán nhũng biểu thức như vậy là tương đối phức tạp. Để dễ dạng cho máy tính trong việc tính toán các biểu thức, người ta đưa ra 1 cách trình bày khác cho biểu thức toán học, đó là dạng hậu tố (postfix).
Theo cách trình bày nay, toán tử không nằm giữa 2 toán hạng mà nằm ở ngay phía sau 2 toán hạng. Chẳng hạn ở biểu thức trên ta có thể viết dưới dạng hậu tố như sau: 3 5 2 – 7 1 + * 6 – * Toán tử – nằm ngay sau 2 toán hạng 5 và 2 nên lấy 5 – 2 = 3, lưu kết quả 3. Toán tử + nằm ngay sau 2 toán hạng 7 và 1 nên lấy 7 + 1 = 8, lưu kết quả 8. Toán tử * nằm ngay sau 2 kết quả vừa lưu nên lấy 3 * 8 = 24, lưu kết quả 24. Toán tử – nằm ngay sau kết quả vừa lưu và 6 nên lấy 24 – 6 = 18 Toán tử * nằm ngay sau kết quả vừa lưu và 3 nên lấy 3 * 18 = 54 là kết quả cuối cùng của biểu thức.
3.2.2. Cách thực hiện
Chuyển đổi biểu thức tiền tố sang hậu tố:
Duyệt từ trái qua phải.
Nếu gặp dấu mở ngoặc thì bỏ qua.
Nếu gặp số thì đưa vào biểu thức mới.
Nếu gặp toán tử thì đưa vào ngăn xếp.
Nếu gặp dấu đóng ngoặc thì lấy toán tử ra đưa vào biểu thức mới.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var
postfixExpression
=
“”
for
s
in
infixExpression
.
characters
{
let
x
=
String
(
s
)
if
numbers
.
rangeOfString
(
x
)
!=
nil
{
postfixExpression
+=
x
}
else
if
operators
.
rangeOfString
(
x
)
!=
nil
{
stackOperator
.
push
(
x
)
}
else
if
x
==
“)”
{
// gap dau dong ngoac lay toan tu ra dua vao bieu thuc moi
let
_operator
=
stackOperator
.
pop
(
)
postfixExpression
+=
_operator
!
}
else
{
// dau mo ngoac bo qua
}
}
return
postfixExpression
}
Tính toán biểu thức hậu tố:
Tính toán biểu thức hậu tố:
Duyệt biểu thức từ trái qua phải.
Nếu gặp toán hạng thì đưa vào ngăn xếp.
Nếu gặp toán tử, lấy ra 2 toán hạng từ ngăn xếp, sử dụng toán tử để tính, sau đó đưa kết quả vào ngăn xếp.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func
calculateInfixExpression
(
)
{
let
infixExpression
=
“(3*(((5-2)*(7+1))-6))”
let
postfixExpression
=
convertInfixToPostfixExpression
(
infixExpression
)
for
s
in
postfixExpression
.
characters
{
let
x
=
String
(
s
)
if
numbers
.
rangeOfString
(
x
)
!=
nil
{
resultStack
.
push
(
Int
(
x
)
!
)
}
else
if
operators
.
rangeOfString
(
x
)
!=
nil
{
let
number1
=
resultStack
.
pop
(
)
!
let
number2
=
resultStack
.
pop
(
)
!
let
result
=
calculate
(
number1
,
number2
:
number2
,
_operator
:
x
)
resultStack
.
push
(
result
)
}
else
{
}
}
(
resultStack
.
top
.
key
)
}
4. Demo
https://github.com/pqhuy87it/MonthlyReport
5. Tài liệu tham khảo
https://www.cs.cmu.edu/~adamchik/15-121/lectures/Stacks%20and%20Queues/Stacks%20and%20Queues.html
Via Viblo
DVMS chuyên:
– Tư vấn, xây dựng, chuyển giao công nghệ Blockchain, mạng xã hội,… – Tư vấn ứng dụng cho smartphone và máy tính bảng, tư vấn ứng dụng vận tải thông minh, thực tế ảo, game mobile,… – Tư vấn các hệ thống theo mô hình kinh tế chia sẻ như Uber, Grab, ứng dụng giúp việc,… – Xây dựng các giải pháp quản lý vận tải, quản lý xe công vụ, quản lý xe doanh nghiệp, phần mềm và ứng dụng logistics, kho vận, vé xe điện tử,… – Tư vấn và xây dựng mạng xã hội, tư vấn giải pháp CNTT cho doanh nghiệp, startup,…
Cấu Trúc Dữ Liệu Và Giải Thuật (Data Structure And Algorithms) Cơ Bản
Cấu trúc dữ liệu và giải thuật (Data Structure and Algorithms) là một trong những khối lượng kiến thức quan trọng nhất trong bất cứ chương trình học nào của sinh viên các ngành công nghệ thông tin. Bạn đã được nghe các bậc tiền bối ở đâu đó nói rằng, học lập trình bắt buộc phải học cấu trúc dữ liệu và giải thuật, điều này không hẳn nhưng lại là yếu tố tiên quyết để bạn đi được xa hơn trên con đường này. Đây là một khía cạnh kiến thức khó cho bất kỳ ai mới học nhưng lại là yếu tố cốt lõi trong mọi chương trình. Bạn có thể học một ngôn ngữ lập trình mới thành thạo trong chưa đầy một tháng nhưng để vận dụng nó tốt thì rất cần nắm vững các yếu tố đặc trưng của nó thể hiện ở các cấu trúc dữ liệu mà nó hỗ trợ, cách thức quản lý cấu trúc dữ liệu đó và các lớp giải thuật hỗ trợ sẵn có trong nó cũng như quan trọng hơn là cách thức để triển khai các thuật toán để giải quyết các vấn đề bằng ngôn ngữ lập trình đó.
Cấu trúc dữ liệu cơ bản
Cấu trúc dữ liệu là gì? Tổng quan về cấu trúc dữ liệu
Cấu trúc dữ liệu mảng và những vấn đề cần biết
Danh sách liên kết và các thao tác trên danh sách liên kết
Danh sách liên kết đơn, sự khác biệt giữa danh sách liên kết và mảng
Danh sách liên kết đôi và các đặc điểm
Danh sách liên kết vòng và ứng dụng
Ngăn xếp và các thao tác trên ngăn xếp
Cấu trúc dữ liệu hàng đợi và các thao tác cơ bản
Một số kiểu hàng đợi
Circular Queue và ứng dụng
Priority Queue (Hàng đợi ưu tiên)
Deque và các phép toán trên Deque
Bảng băm và ứng dụng của bảng băm
Các cấu trúc dữ liệu dạng cây
Cấu trúc dữ liệu cây và ứng dụng
Duyệt cây và thứ tự duyệt cây
Cây nhị phân và các kiểu cây nhị phân
Cây nhị phân tìm kiếm và các ứng dụng
Cây AVL và các thao tác cơ bản trên cây AVL
Splay Tree và ứng dụng
B-Tree và ứng dụng của B-tree
B+ tree và ứng dụng
Cây đỏ đen (Red-Black Tree) và ứng dụng
Cấu trúc dữ liệu Heap và các phép toán
Cấu trúc dữ liệu đồ thị
Cấu trúc dữ liệu đồ thị (Graph) và ứng dụng
Cây khung và cây khung nhỏ nhất trong đồ thị
Thuật toán Tarjan trong tìm thành phần liên thông mạnh
Thuật toán BFS – Tìm kiếm theo chiều rộng trên đồ thị
Thuật toán DFS – Tìm kiếm theo chiều sâu trên đồ thị
Biểu diễn đồ thị bằng ma trận kề và danh sách kề
Thuật toán tổng quan
Thuật toán là gì? Mối liên hệ giữa cấu trúc dữ liệu và thuật toán
Độ phức tạp tính toán
Phân tích thiết kế thuật toán
Thuật toán tham lam (Greedy Algorithms)
Thuật toán chia để trị (Divide and Conquer)
Quy hoạch động (Dynamic Programming)
Thuật toán quay lui (Back Tracking)
Đệ quy và ước lượng độ phức tạp đệ quy bằng định lý thợ (Master Theorem)
Các giải thuật tìm kiếm
Thuật toán tìm kiếm tuyến tính
Thuật toán tìm kiếm nhị phân
Tìm kiếm nội suy
Các giải thuật sắp xếp
Thuật toán sắp xếp nổi bọt (Bubble Sort)
Sắp xếp chọn (Selection Sort)
Thuật toán Insertion Sort (sắp xếp chèn)
Merge Sort (sắp xếp trộn)
Quick sort (sắp xếp nhanh)
Counting Sort (sắp xếp đếm)
Radix Sort (sắp xếp theo cơ số)
Bucket Sort (sắp xếp theo khối)
Heap Sort (sắp xếp vun đống)
Shell Sort (ứng dụng của sắp xếp chèn)
Các thuật toán đối sánh mẫu, tìm xâu con
Thuật toán Knuth-Morris-Pratt trong tìm kiếm xâu con
Thuật toán Boyer-Moore trong tìm kiếm xâu con
Thuật toán Rabin-Karp ứng dụng trong đối sánh mẫu
Thuật toán Wu-Manber trong đối sánh đa mẫu
Thuật toán Aho-Corasick trong đối sánh đa mẫu
Các thuật toán trên đồ thị
Thuật toán Dijkstra và các cách thực thi
Thuật toán Bellman-Ford cho đồ thị có trọng số âm
Thuật toán Floyd-Warshall cho đồ thị dầy
Thuật toán Johnson cho đồ thị thưa
Cập nhật thông tin chi tiết về Duyệt Cây Trong Cấu Trúc Dữ Liệu Và Giải Thuật trên website Nhatngukohi.edu.vn. Hy vọng nội dung bài viết sẽ đáp ứng được nhu cầu của bạn, chúng tôi sẽ thường xuyên cập nhật mới nội dung để bạn nhận được thông tin nhanh chóng và chính xác nhất. Chúc bạn một ngày tốt lành!