<p>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!</p>
<p>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.</p>
<p>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ả.</p>
<p>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.</p>
<p>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ả.</p>
<p>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.</p>

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

<p style="text-align: justify;">Như đ&atilde; n&oacute;i trong b&agrave;i trước, để bắt đầu với kiểu cấu tr&uacute;c dữ liệu c&acirc;y v&agrave; đồ thị, ta sẽ bắt đầu với dạng đơn giản nhất đ&oacute; l&agrave; c&acirc;y nhị ph&acirc;n. Trong b&agrave;i viết n&agrave;y, ta sẽ c&ugrave;ng t&igrave;m hiểu về cấu tr&uacute;c dữ liệu c&acirc;y nhị ph&acirc;n v&agrave; một số dạng biến thế kh&aacute;c nhau của n&oacute;. Đ&acirc;y l&agrave; cơ sở để bạn c&oacute; thể hiểu v&agrave; thực hiện c&aacute;c thao t&aacute;c duyệt c&acirc;y v&agrave; sử dụng c&acirc;y để giải c&aacute;c b&agrave;i to&aacute;n thực tế ở c&aacute;c b&agrave;i ph&iacute;a sau.</p>
<h2 style="text-align: justify;">C&acirc;y nhị ph&acirc;n</h2>
<p style="text-align: justify;">Về mặt định nghĩa, c&acirc;y nhị ph&acirc;n rất đơn giản. C&acirc;y nhị ph&acirc;n l&agrave; một cấu tr&uacute;c dữ liệu dạng c&acirc;y trong đ&oacute; mỗi n&uacute;t cha c&oacute; thể c&oacute; nhiều nhất hai n&uacute;t con. H&igrave;nh ảnh minh họa dưới đ&acirc;y biểu diễn dạng của một c&acirc;y nhị ph&acirc;n.</p>
<p><img style="width: 720px; display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/848cb845-05fa-4275-be51-090d79abd14b" alt="binary_tree_01" /></p>
<h2 style="text-align: justify;">Biểu diễn c&acirc;y nhị ph&acirc;n</h2>
<p style="text-align: justify;">Một n&uacute;t của c&acirc;y nhị ph&acirc;n được biểu diễn bằng một cấu tr&uacute;c chứa một phần dữ liệu v&agrave; hai con trỏ tới c&aacute;c cấu tr&uacute;c kh&aacute;c c&ugrave;ng kiểu. Đ&acirc;y l&agrave; c&aacute;c n&uacute;t (node) trong c&acirc;y.</p>
<pre class="language-cpp"><code>struct node
{
 int data;
 struct node *left;
 struct node *right;
};</code></pre>
<p>Như h&igrave;nh vẽ dưới đ&acirc;y.</p>
<p><img style="width: 100%;" src="https://tek4.vn/public_files/1a49e562-718a-4a77-808a-dc8bd3e83a40" alt="binary_tree_02" /></p>
<p style="text-align: justify;">V&iacute; dụ dưới đ&acirc;y l&agrave; c&aacute;ch triển khai c&acirc;y nhị ph&acirc;n bằng ng&ocirc;n ngữ lập tr&igrave;nh C. Bạn c&oacute; thể thử chỉnh sửa v&agrave; chạy đoạn m&atilde; dưới đ&acirc;y để xem kết quả.</p>
<p style="text-align: justify;">[___NOTE_Bạn chưa cần quan t&acirc;m đến c&aacute;c kiểu duyệt c&acirc;y. C&aacute;c c&aacute;ch duyệt c&acirc;y sẽ được học chi tiết hơn trong b&agrave;i sau. Ở đ&acirc;y, bạn chỉ cần nắm được c&aacute;ch cấu tạo l&ecirc;n c&acirc;y v&agrave; cấu tr&uacute;c của n&oacute;!!!_NOTE___]</p>
<div class="code-editor__wrapped code-editor__edit__wrapped" data-id="990af0a4-f837-46ed-91d2-914699448f79">
<table class="code-editor__table" data-id="b3d9bd54-a612-448b-b039-821526b2decb">
<tbody>
<tr class="code-editor__edit__row__first">
<td colspan="2">RUN_CODE (*** ph&acirc;n biệt ***)</td>
</tr>
<tr>
<td>C</td>
<td>
<pre class="language-c" data-content="#include" data-language="c" data-ace-language="c_cpp" data-name-language="C" data-main-file="main.c"><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>
</td>
</tr>
</tbody>
</table>
</div>
<p style="text-align: justify;"><br />&nbsp;Kết quả:</p>
<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>
<p style="text-align: justify;">Dưới đ&acirc;y l&agrave; c&acirc;y nhị ph&acirc;n được biểu diễn bởi đoạn m&atilde; b&ecirc;n tr&ecirc;n.</p>
<p><img style="width: 720px; display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/373dacb3-74de-4b55-9bc0-817426866b1a" alt="cay-nhi-phan-10" /></p>
<h2 style="text-align: justify;">C&aacute;c kiểu c&acirc;y nhị ph&acirc;n</h2>
<p>Dựa tr&ecirc;n số lượng n&uacute;t con của c&aacute;c n&uacute;t cha trong c&acirc;y m&agrave; ta c&oacute; thể chia c&acirc;y nhị ph&acirc;n th&agrave;nh một số dạng biến thể như sau.</p>
<h3 style="text-align: justify;">C&acirc;y nhị ph&acirc;n đầy đủ</h3>
<p style="text-align: justify;">C&acirc;y nhị ph&acirc;n đầy đủ l&agrave; một loại c&acirc;y nhị ph&acirc;n đặc biệt trong đ&oacute; mọi n&uacute;t cha hay n&uacute;t trong đều c&oacute; hai hoặc kh&ocirc;ng c&oacute; n&uacute;t con cả. Chẳng hạn c&acirc;y ở h&igrave;nh vẽ dưới đ&acirc;y l&agrave; một c&acirc;y nhị phần đầy đủ.</p>
<p><img style="width: 720px; display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/9d06a518-0215-4359-9a0a-15ea6c1a1308" alt="cay-nhi-phan-2" /></p>
<h3 style="text-align: justify;">C&acirc;y nhị ph&acirc;n l&yacute; tưởng</h3>
<p style="text-align: justify;">C&acirc;y nhị ph&acirc;n l&yacute; tưởng l&agrave; một loại c&acirc;y nhị ph&acirc;n trong đ&oacute; mỗi n&uacute;t b&ecirc;n trong c&oacute; đ&uacute;ng hai n&uacute;t con v&agrave; tất cả c&aacute;c n&uacute;t l&aacute; đều ở c&ugrave;ng một mức.</p>
<p style="text-align: justify;">V&iacute; dụ: H&igrave;nh dưới đ&acirc;y biểu diễn một c&acirc;y nhị ph&acirc;n l&yacute; tưởng.</p>
<p><img style="width: 50%; display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/ee59030d-ed92-4d8e-a1d5-71606a063211" alt="cay-nhi-phan-3" /></p>
<h3 style="text-align: justify;">C&acirc;y nhị ph&acirc;n ho&agrave;n chỉnh</h3>
<p style="text-align: justify;">Một c&acirc;y nhị ph&acirc;n ho&agrave;n chỉnh cũng giống như một c&acirc;y nhị ph&acirc;n đầy đủ, nhưng c&oacute; hai điểm kh&aacute;c biệt ch&iacute;nh như sau:</p>
<ul style="text-align: justify;">
<li>Mọi mức phải được lấp đầy ho&agrave;n to&agrave;n</li>
<li>Tất cả c&aacute;c n&uacute;t l&aacute; phải nghi&ecirc;ng về b&ecirc;n tr&aacute;i.</li>
<li>Phần tử l&aacute; cuối c&ugrave;ng c&oacute; thể kh&ocirc;ng c&oacute; n&uacute;t anh em b&ecirc;n phải, tức l&agrave; c&acirc;y nhị ph&acirc;n ho&agrave;n chỉnh kh&ocirc;ng nhất thiết phải l&agrave; c&acirc;y nhị ph&acirc;n đầy đủ.</li>
</ul>
<p style="text-align: justify;">V&iacute; dụ.</p>
<p><img style="width: 720px; display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/a9255bdb-978b-4715-8b3d-2e18feb0ab7b" alt="cay-nhi-phan-4" /></p>
<h3 style="text-align: justify;">C&acirc;y tho&aacute;i h&oacute;a</h3>
<p style="text-align: justify;">C&acirc;y tho&aacute;i h&oacute;a l&agrave; c&acirc;y c&oacute; một n&uacute;t con b&ecirc;n tr&aacute;i hoặc phải.</p>
<p><img style="width: 480px; display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/bcca2ef8-70c4-407a-a3c8-6f42b4d6cfc8" alt="cay-nhi-phan-5" /></p>
<h3 style="text-align: justify;">C&acirc;y nhị ph&acirc;n bị lệch</h3>
<p style="text-align: justify;">C&acirc;y nhị ph&acirc;n lệch l&agrave; c&acirc;y tho&aacute;i h&oacute;a, trong đ&oacute;, c&acirc;y bị chi phối bởi c&aacute;c n&uacute;t b&ecirc;n tr&aacute;i hoặc c&aacute;c n&uacute;t b&ecirc;n phải. Như vậy, c&oacute; hai loại c&acirc;y nhị ph&acirc;n lệch</p>
<ol style="text-align: justify;">
<li>C&acirc;y nhị ph&acirc;n lệch tr&aacute;i</li>
<li>C&acirc;y nhị ph&acirc;n lệch phải</li>
</ol>
<table style="border-collapse: collapse; width: 100%; height: 570px;" border="1">
<tbody>
<tr style="height: 570px;">
<td style="width: 49.2007%; height: 570px;"><img style="width: 720px; display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/d9d2dec7-6626-404a-984d-4d1103908768" alt="cay-nhi-phan-6" /></td>
<td style="width: 49.2007%; height: 570px;"><img style="width: 720px; display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/7b6a131d-11a2-4497-84f9-89b5018f5980" alt="cay-nhi-phan-7" /></td>
</tr>
</tbody>
</table>
<h3 style="text-align: justify;">C&acirc;y nhị ph&acirc;n c&acirc;n bằng</h3>
<p style="text-align: justify;">Đ&acirc;y l&agrave; một loại c&acirc;y nhị ph&acirc;n trong đ&oacute; sự ch&ecirc;nh lệch giữa c&acirc;y con b&ecirc;n tr&aacute;i v&agrave; c&acirc;y con b&ecirc;n phải cho mỗi n&uacute;t l&agrave; 0 hoặc 1.</p>
<p style="text-align: justify;">V&iacute; dụ:</p>
<p><img style="width: 720px; display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/d0c296a8-06b8-41a5-8e80-70f383e2d421" alt="cay-nhi-phan-8" /></p>
<h2 style="text-align: justify;">Ứng dụng của c&acirc;y nhị ph&acirc;n</h2>
<p style="text-align: justify;">C&acirc;y nhị ph&acirc;n c&oacute; nhiều ứng dụng thực tế kh&aacute;c nhau. Dưới đ&acirc;y l&agrave; một số ứng dụng điển h&igrave;nh của n&oacute;:</p>
<ul style="text-align: justify;">
<li style="text-align: justify;">Để truy cập dữ liệu dễ d&agrave;ng v&agrave; nhanh ch&oacute;ng.</li>
<li style="text-align: justify;">Được sử dụng trong thuật to&aacute;n bộ định tuyến.</li>
<li style="text-align: justify;">Để triển khai cấu tr&uacute;c dữ liệu vun đống (heap).</li>
<li style="text-align: justify;">Triển khai l&agrave;m c&acirc;y c&uacute; ph&aacute;p.</li>
</ul>
<p style="text-align: justify;">Tr&ecirc;n đ&acirc;y l&agrave; kh&aacute;i niệm v&agrave; v&iacute; dụ cơ bản về cấu tr&uacute;c dữ liệu c&acirc;y nhị ph&acirc;n. Trong b&agrave;i sau, ta sẽ tiếp tục t&igrave;m hiểu về c&aacute;c thao t&aacute;c tr&ecirc;n c&acirc;y nhị ph&acirc;n, đặc biệt l&agrave; duyệt c&acirc;y nhị ph&acirc;n. Về cơ bản hầu hết c&aacute;c b&agrave;i to&aacute;n li&ecirc;n quan đến cấu tr&uacute;c dữ liệu c&acirc;y nhị phần đều quy về thao t&aacute;c duyệt c&acirc;y.</p>

Cây nhị phân và các kiểu cây nhị phân