Duyệt cây và thứ tự duyệt cây

<p style="text-align: justify;">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.</p> <h2 style="text-align: justify;">1. Kh&aacute;i niệm</h2> <p style="text-align: justify;">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.</p> <p style="text-align: justify;">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.</p> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/e53381cb-4abc-4b54-b720-5f69d2d0ca70" alt="duyet-cay-va-thu-tu-duyet-cay" /></p> <p style="text-align: justify;">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.</p> <p style="text-align: justify;"><strong><em>1. Bắt đầu từ tr&ecirc;n xuống, từ tr&aacute;i sang phải.</em></strong></p> <pre class="language-markup"><code>2 4 3 1 8</code></pre> <p style="text-align: justify;"><strong><em>2. Bắt đầu từ dưới l&ecirc;n, từ tr&aacute;i sang phải</em></strong></p> <pre class="language-markup"><code>3 1 4 8 2</code></pre> <p style="text-align: justify;">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.</p> <p style="text-align: justify;">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.</p> <pre class="language-cpp"><code>struct node { int data; struct node* left; struct node* right; }</code></pre> <p style="text-align: justify;">Cấu tr&uacute;c của một n&uacute;t bao gồm hai con trỏ l&agrave; <span class="lang:default decode:true crayon-inline">left</span> v&agrave; <span class="lang:default decode:true crayon-inline">right</span>, 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.</p> <p style="text-align: justify;">Theo cấu tr&uacute;c n&agrave;y, mỗi c&acirc;y l&agrave; sự kết hợp của</p> <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> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/b42697d7-30b8-4230-9cd0-99b043abfecf" alt="duyet-cay-va-thu-tu-duyet-cay-2" /></p> <p style="text-align: justify;">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.</p> <h2 style="text-align: justify;">2. C&aacute;c kiểu duyệt c&acirc;y</h2> <p style="text-align: justify;">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.</p> <p style="text-align: justify;"><strong>2.1. Duyệt theo thứ tự Inorder</strong></p> <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> <p style="text-align: justify;">V&iacute; dụ:</p> <pre class="language-cpp"><code>inorder(left) print(root) inorder(right)</code></pre> <p style="text-align: justify;"><strong>2.2. Duyệt theo thứ tự Preorder</strong></p> <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> <p style="text-align: justify;">V&iacute; dụ:</p> <pre class="language-cpp"><code>print(root) preorder(left) preorder(right)</code></pre> <p style="text-align: justify;"><strong>2.3. Duyệt theo thứ tự Postorder</strong></p> <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> <p style="text-align: justify;">V&iacute; dụ:</p> <pre class="language-cpp"><code>postorder(left) postorder(right) print(data)</code></pre> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/034f85da-d71c-44db-8800-4b982c9c30db" alt="duyet-cay-va-thu-tu-duyet-cay-3" /></p> <p style="text-align: justify;">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ớ.</p> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/a98077f7-055c-4659-ac1f-0bcbd05fe763" alt="duyet-cay-va-thu-tu-duyet-cay-4" /></p> <p style="text-align: justify;">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.</p> <p style="text-align: justify;">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</p> <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> <p style="text-align: justify;">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.</p> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/5e05faae-f3b8-41e4-8c10-8830a695cebd" alt="duyet-cay-va-thu-tu-duyet-cay-5" /></p> <p style="text-align: justify;">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.</p> <p style="text-align: justify;">Đặ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.</p> <p style="text-align: justify;">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:</p> <pre class="language-markup"><code>3 4 1 2 8</code></pre> <p style="text-align: justify;">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.</p> <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> <p style="text-align: justify;">V&iacute; dụ: Triển khai duyệt c&acirc;y bằng ng&ocirc;n ngữ lập tr&igrave;nh C.</p> <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> <p style="text-align: justify;">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;">Ta sẽ c&oacute; sơ đồ h&igrave;nh c&acirc;y trong đoạn m&atilde; tr&ecirc;n như sau:</p> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/38c59c45-3af9-462d-8741-97a49fd42961" alt="duyet-cay-va-thu-tu-duyet-cay-6" /></p> <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ề 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;!</p>