Ch&agrave;o mừng c&aacute;c bạn đến với kh&oacute;a học "Cấu tr&uacute;c dữ liệu v&agrave; Giải thuật" tại TEK4.VN!
Bạn đ&atilde; bao giờ tự hỏi rằng để trở th&agrave;nh một lập tr&igrave;nh vi&ecirc;n xuất sắc, bạn cần những kiến thức v&agrave; kỹ năng g&igrave;? Kh&oacute;a học n&agrave;y ch&iacute;nh l&agrave; ch&igrave;a kh&oacute;a để mở ra c&aacute;nh cửa của tri thức đ&oacute;. Với nội dung phong ph&uacute; v&agrave; chi tiết, kh&oacute;a học Cấu tr&uacute;c dữ liệu v&agrave; Giải thuật tại TEK4.VN hứa hẹn sẽ gi&uacute;p bạn x&acirc;y dựng nền tảng vững chắc v&agrave; th&agrave;nh thạo trong lập tr&igrave;nh.
Trong kh&oacute;a học n&agrave;y, ch&uacute;ng ta sẽ tập trung v&agrave;o việc kh&aacute;m ph&aacute; v&agrave; hiểu r&otilde; c&aacute;c cấu tr&uacute;c dữ liệu quan trọng như mảng, chuỗi k&yacute; tự, danh s&aacute;ch li&ecirc;n kết, ngăn xếp, h&agrave;ng đợi, bảng băm, tập hợp, c&acirc;y, đồ thị v&agrave; heap. C&aacute;c cấu tr&uacute;c dữ liệu n&agrave;y l&agrave; nền tảng của lập tr&igrave;nh, gi&uacute;p ch&uacute;ng ta giải quyết c&aacute;c vấn đề phức tạp một c&aacute;ch hiệu quả.
Kh&oacute;a học cũng sẽ gi&uacute;p bạn hiểu r&otilde; c&aacute;c thuật to&aacute;n cơ bản v&agrave; n&acirc;ng cao, bao gồm thuật to&aacute;n sắp xếp, thuật to&aacute;n t&igrave;m kiếm, thuật to&aacute;n t&igrave;m kiếm nhị ph&acirc;n, thuật to&aacute;n t&igrave;m kiếm chuỗi k&yacute; tự, giải thuật tham lam, thuật to&aacute;n quay lui v&agrave; quy hoạch động. Bạn sẽ học c&aacute;ch &aacute;p dụng c&aacute;c thuật to&aacute;n n&agrave;y v&agrave;o c&aacute;c vấn đề thực tế, gi&uacute;p tăng cường kỹ năng giải quyết vấn đề của m&igrave;nh.
Ngo&agrave;i ra, ch&uacute;ng m&igrave;nh sẽ chia sẻ một số kinh nghiệm cần thiết cho buổi phỏng vấn, gi&uacute;p bạn chuẩn bị tốt nhất cho c&aacute;c cơ hội nghề nghiệp li&ecirc;n quan đến lập tr&igrave;nh trong tương lai. Bạn sẽ được học c&aacute;ch hiểu r&otilde; y&ecirc;u cầu của người phỏng vấn, thể hiện kỹ năng lập tr&igrave;nh của m&igrave;nh một c&aacute;ch hiệu quả v&agrave; trả lời c&aacute;c c&acirc;u hỏi một c&aacute;ch tr&ocirc;i chảy. Ch&uacute;ng m&igrave;nh tự tin rằng, sau khi bạn ho&agrave;n th&agrave;nh kh&oacute;a học n&agrave;y, bạn sẽ trở n&ecirc;n nhạy b&eacute;n trong tư duy lập tr&igrave;nh hiệu quả.
H&atilde;y tham gia kh&oacute;a học n&agrave;y để t&igrave;m hiểu s&acirc;u hơn về lập tr&igrave;nh v&agrave; mở rộng kỹ năng của bạn. TEK4.VN rất mong được hỗ trợ bạn trong qu&aacute; tr&igrave;nh học tập n&agrave;y.

Cấu trúc dữ liệu và Giải thuật

Trong b&agrave;i viết n&agrave;y, ta sẽ c&ugrave;ng t&igrave;m hiểu về c&aacute;c kỹ thuật duyệt c&acirc;y v&agrave; thứ tự duyệt c&acirc;y kh&aacute;c nhau. Ngo&agrave;i ra, ta sẽ triển khai c&aacute;c v&iacute; dụ của c&aacute;c phương ph&aacute;p duyệt c&acirc;y kh&aacute;c nhau viết bằng ng&ocirc;n ngữ lập tr&igrave;nh C. C&aacute;c bạn c&oacute; thể xem qua về b&agrave;i <a href="../../../cau-truc-du-lieu-cay-va-ung-dung/">cấu tr&uacute;c dữ liệu dạng c&acirc;y</a> trước khi t&igrave;m hiểu về c&aacute;ch duyệt c&acirc;y được n&oacute;i trong b&agrave;i viết n&agrave;y.
<h2 style="text-align: justify;">1. Kh&aacute;i niệm</h2>
Duyệt c&acirc;y c&oacute; nghĩa l&agrave; đi qua từng n&uacute;t trong c&acirc;y. V&iacute; dụ, ta c&oacute; thể muốn th&ecirc;m tất cả c&aacute;c gi&aacute; trị trong c&acirc;y hoặc t&igrave;m gi&aacute; trị lớn nhất. Để thực hiện tất cả c&aacute;c thao t&aacute;c n&agrave;y, ta sẽ cần phải truy cập v&agrave;o từng n&uacute;t của c&acirc;y.
Cấu tr&uacute;c dữ liệu tuyến t&iacute;nh như mảng, ngăn xếp, h&agrave;ng đợi v&agrave; danh s&aacute;ch li&ecirc;n kết chỉ c&oacute; một c&aacute;ch để đọc dữ liệu. Nhưng cấu tr&uacute;c dữ liệu ph&acirc;n cấp như c&acirc;y c&oacute; thể được duyệt theo nhiều c&aacute;ch kh&aacute;c nhau.
<img style="width: 100%;" src="../../../public_files/e53381cb-4abc-4b54-b720-5f69d2d0ca70" alt="duyet-cay-va-thu-tu-duyet-cay" />
H&atilde;y nghĩ về c&aacute;ch ch&uacute;ng ta c&oacute; thể đọc c&aacute;c n&uacute;t của c&aacute;i c&acirc;y trong h&igrave;nh tr&ecirc;n.
1. Bắt đầu từ tr&ecirc;n xuống, từ tr&aacute;i sang phải.
<pre class="language-markup"><code>2 4 3 1 8</code></pre>
2. Bắt đầu từ dưới l&ecirc;n, từ tr&aacute;i sang phải
<pre class="language-markup"><code>3 1 4 8 2</code></pre>
Mặc d&ugrave; qu&aacute; tr&igrave;nh n&agrave;y c&oacute; phần dễ d&agrave;ng, nhưng n&oacute; kh&ocirc;ng xem x&eacute;t về mặt cấu tr&uacute;c hệ thống ph&acirc;n cấp của c&acirc;y, chỉ c&oacute; độ s&acirc;u của c&aacute;c n&uacute;t.
Thay v&agrave;o đ&oacute;, ch&uacute;ng ta sẽ sử dụng c&aacute;c phương ph&aacute;p duyệt c&oacute; xem x&eacute;t cấu tr&uacute;c cơ bản của c&acirc;y.
<pre class="language-cpp"><code>struct node {
 int data;
 struct node* left;
 struct node* right;
}</code></pre>
Cấu tr&uacute;c của một n&uacute;t bao gồm hai con trỏ l&agrave; left v&agrave; right, hai con trỏ n&agrave;y đại diện cho c&aacute;c n&uacute;t con của n&oacute; v&agrave; con n&uacute;t con n&agrave;y&nbsp; c&oacute; thể c&oacute; c&aacute;c n&uacute;t con tr&aacute;i v&agrave; phải kh&aacute;c, v&igrave; vậy ch&uacute;ng ta n&ecirc;n coi ch&uacute;ng l&agrave; c&aacute;c c&acirc;y con thay v&igrave; c&aacute;c n&uacute;t con.
Theo cấu tr&uacute;c n&agrave;y, mỗi c&acirc;y l&agrave; sự kết hợp của
<ul style="text-align: justify;">
<li>Một n&uacute;t chứa dữ liệu</li>
<li>Hai c&acirc;y con</li>
</ul>
<img style="width: 100%;" src="../../../public_files/b42697d7-30b8-4230-9cd0-99b043abfecf" alt="duyet-cay-va-thu-tu-duyet-cay-2" />
Mục ti&ecirc;u của ch&uacute;ng ta l&agrave; truy cập từng n&uacute;t, v&igrave; vậy ch&uacute;ng ta cần phải truy cập tất cả c&aacute;c n&uacute;t trong c&acirc;y con, truy cập n&uacute;t gốc v&agrave; truy cập tất cả c&aacute;c n&uacute;t trong c&acirc;y con.
<h2 style="text-align: justify;">2. C&aacute;c kiểu duyệt c&acirc;y</h2>
T&ugrave;y thuộc v&agrave;o thứ tự m&agrave; ch&uacute;ng ta thực hiện việc n&agrave;y, c&oacute; thể c&oacute; ba kiểu duyệt c&acirc;y như sau.
2.1. Duyệt theo thứ tự Inorder
<ol style="text-align: justify;">
<li>Đầu ti&ecirc;n, ta sẽ truy cập tất cả c&aacute;c n&uacute;t trong c&acirc;y con b&ecirc;n tr&aacute;i.</li>
<li>Sau đ&oacute; đến n&uacute;t gốc.</li>
<li>Truy cập tất cả c&aacute;c n&uacute;t trong c&acirc;y con b&ecirc;n phải.</li>
</ol>
V&iacute; dụ:
<pre class="language-cpp"><code>inorder(left)
print(root)
inorder(right)</code></pre>
2.2. Duyệt theo thứ tự Preorder
<ol style="text-align: justify;">
<li>Truy cập n&uacute;t gốc.</li>
<li>Truy cập tất cả c&aacute;c n&uacute;t trong c&acirc;y con b&ecirc;n tr&aacute;i.</li>
<li>Truy cập tất cả c&aacute;c n&uacute;t trong c&acirc;y con b&ecirc;n phải.</li>
</ol>
V&iacute; dụ:
<pre class="language-cpp"><code>print(root)
preorder(left)
preorder(right)</code></pre>
2.3. Duyệt theo thứ tự Postorder
<ol style="text-align: justify;">
<li>Truy cập tất cả c&aacute;c n&uacute;t trong c&acirc;y con b&ecirc;n tr&aacute;i.</li>
<li>Truy cập tất cả c&aacute;c n&uacute;t trong c&acirc;y con b&ecirc;n phải.</li>
<li>Truy cập v&agrave;o n&uacute;t gốc.</li>
</ol>
V&iacute; dụ:
<pre class="language-cpp"><code>postorder(left)
postorder(right)
print(data)</code></pre>
<img style="width: 100%;" src="../../../public_files/034f85da-d71c-44db-8800-4b982c9c30db" alt="duyet-cay-va-thu-tu-duyet-cay-3" />
Ch&uacute;ng ta sẽ duyệt qua c&acirc;y con b&ecirc;n tr&aacute;i trước. Ch&uacute;ng ta cũng cần nhớ duyệt qua n&uacute;t gốc v&agrave; c&acirc;y con b&ecirc;n phải sau khi ho&agrave;n th&agrave;nh từng c&acirc;y. Ngo&agrave;i ra, ta sẽ đặt tất cả những thứ n&agrave;y v&agrave;o một ngăn xếp để dễ ghi nhớ.
<img style="width: 100%;" src="../../../public_files/a98077f7-055c-4659-ac1f-0bcbd05fe763" alt="duyet-cay-va-thu-tu-duyet-cay-4" />
B&acirc;y giờ ch&uacute;ng ta duyệt qua c&acirc;y con được trỏ bởi TOP của ngăn xếp.
Một lần nữa, ch&uacute;ng ta sẽ tu&acirc;n theo quy tắc của c&aacute;ch duyệt theo thứ tự Inorder
<pre class="language-markup"><code>C&acirc;y con tr&aacute;i &rarr; n&uacute;t gốc &rarr; c&acirc;y con phải</code></pre>
Sau khi duyệt qua c&acirc;y con b&ecirc;n tr&aacute;i, ch&uacute;ng ta sẽ c&ograve;n lại c&aacute;c n&uacute;t sau.
<img style="width: 100%;" src="../../../public_files/5e05faae-f3b8-41e4-8c10-8830a695cebd" alt="duyet-cay-va-thu-tu-duyet-cay-5" />
V&igrave; n&uacute;t c&oacute; gi&aacute; trị l&agrave; 3 kh&ocirc;ng c&oacute; bất kỳ c&acirc;y con n&agrave;o, ch&uacute;ng ta sẽ in n&oacute; trực tiếp. Sau đ&oacute;, ch&uacute;ng ta in n&uacute;t cha của n&oacute; l&agrave; 4 v&agrave; sau đ&oacute; l&agrave; c&acirc;y con b&ecirc;n phải 1.
Đặt mọi thứ v&agrave;o một ngăn xếp sẽ rất hữu &iacute;ch bởi v&igrave; c&acirc;y con b&ecirc;n tr&aacute;i của n&uacute;t gốc đ&atilde; được duyệt qua, ch&uacute;ng ta c&oacute; thể in n&oacute; v&agrave; chuyển đến c&acirc;y con b&ecirc;n phải.
Sau khi đi qua tất cả c&aacute;c n&uacute;t, ch&uacute;ng ta sẽ nhận được thứ tự duyệt Inorder như sau:
<pre class="language-markup"><code>3 4 1 2 8</code></pre>
Ch&uacute;ng ta kh&ocirc;ng phải tự tạo ngăn xếp v&igrave; kỹ thuật đệ quy sẽ duy tr&igrave; thứ tự ch&iacute;nh x&aacute;c.
<h2 style="text-align: justify;">3. Triển khai kỹ thuật duyệt c&acirc;y v&agrave; thứ tự duyệt c&acirc;y</h2>
V&iacute; dụ: Triển khai duyệt c&acirc;y bằng ng&ocirc;n ngữ lập tr&igrave;nh C.
<pre class="language-cpp"><code>#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;

struct node {
 int data;
 struct node* left;
 struct node* right;
};

int inorder(struct node* root) {
 if (root == NULL)
 return 0;
 inorder(root-&gt;left);
 printf("%d ", root-&gt;data);
 inorder(root-&gt;right);
}

int preorder(struct node* root) {
 if (root == NULL)
 return 0;
 printf("%d ", root-&gt;data);
 preorder(root-&gt;left);
 preorder(root-&gt;right);
}

int postorder(struct node* root) {
 if (root == NULL)
 return 0;
 postorder(root-&gt;left);
 postorder(root-&gt;right);
 printf("%d ", root-&gt;data);
}

struct node* create(int a) {
 struct node* new_node = malloc(sizeof(struct node));
 new_node-&gt;data = a;
 new_node-&gt;left = NULL;
 new_node-&gt;right = NULL;
 return new_node;
}

struct node* add_left_node(struct node* root, int a) {
 root-&gt;left = create(a);
 return root-&gt;left;
}

struct node* add_right_node(struct node* root, int a) {
 root-&gt;right = create(a);
 return root-&gt;right;
}

int main() {
 struct node* root = create(34);
 add_left_node(root, 32);
 add_left_node(root-&gt;left, 42);
 add_right_node(root-&gt;left, 93);

 printf("\nDuyệt theo c&aacute;ch Inorder\n");
 inorder(root);

 printf("\nDuyệt theo c&aacute;ch Preorder\n");
 preorder(root);

 printf("\nDuyệt theo c&aacute;ch Postorder\n");
 postorder(root);
 return 0;
}</code></pre>
Kết quả:
<pre class="language-markup"><code>Duyệt theo c&aacute;ch Inorder
42 32 93 34
Duyệt theo c&aacute;ch Preorder
34 32 42 93
Duyệt theo c&aacute;ch Postorder
42 93 32 34</code></pre>
Ta sẽ c&oacute; sơ đồ h&igrave;nh c&acirc;y trong đoạn m&atilde; tr&ecirc;n như sau:
<img style="width: 100%;" src="../../../public_files/38c59c45-3af9-462d-8741-97a49fd42961" alt="duyet-cay-va-thu-tu-duyet-cay-6" />
Tr&ecirc;n đ&acirc;y l&agrave; kh&aacute;i niệm v&agrave; v&iacute; dụ cơ bản về kỹ thuật duyệt c&acirc;y v&agrave; thứ tự duyệt c&acirc;y. Hy vọng mọi người c&oacute; thể &aacute;p dụng v&agrave;o trong chương tr&igrave;nh của m&igrave;nh. Nếu mọi người c&oacute; đ&oacute;ng g&oacute;p g&igrave; th&ecirc;m th&igrave; c&oacute; thể để c&aacute;c b&igrave;nh luận b&ecirc;n dưới b&agrave;i viết n&agrave;y. Mọi người h&atilde;y tiếp tục theo d&otilde;i c&aacute;c b&agrave;i tiếp theo v&agrave; cập nhật c&aacute;c b&agrave;i mới nhất tr&ecirc;n <a href="http://tek4.vn">tek4</a> nh&eacute;!