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

<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ấu tr&uacute;c dữ liệu c&acirc;y nhị ph&acirc;n v&agrave; c&aacute;c kiểu cấu tr&uacute;c kh&aacute;c nhau của n&oacute;. Ngo&agrave;i ra, ta sẽ triển khai v&iacute; dụ về c&acirc;y nhị ph&acirc;n được viết bằng ng&ocirc;n ngữ C.</p> <h2 style="text-align: justify;">1. Kh&aacute;i niệm</h2> <p style="text-align: justify;">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.</p> <p style="text-align: justify;">H&igrave;nh ảnh minh họa dưới đ&acirc;y sẽ biểu diễn c&acirc;y nhị ph&acirc;n như sau.</p> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/e2a40110-4af4-4c5c-b4a1-b7ccab0ca55d" alt="cay-nhi-phan" /></p> <h2 style="text-align: justify;">2. C&aacute;c kiểu c&acirc;y nhị ph&acirc;n</h2> <h3 style="text-align: justify;">2.1. 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 nội bộ đều c&oacute; hai hoặc kh&ocirc;ng c&oacute; n&uacute;t con cả.</p> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/dfe9158a-587b-4d7c-833a-9488a5338b67" alt="cay-nhi-phan-2" /></p> <h3 style="text-align: justify;">2.2. 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ụ.</p> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/9f627fd0-3eae-42fd-81c1-218ecd974586" alt="cay-nhi-phan-3" /></p> <h3 style="text-align: justify;">2.3. 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 style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/20ce0006-16fe-4dec-a39e-1061201b4f60" alt="cay-nhi-phan-4" /></p> <h3 style="text-align: justify;">2.4. 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 style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/667fa788-0bbc-488c-8284-cc9cccb24976" alt="cay-nhi-phan-5" /></p> <h3 style="text-align: justify;">2.5. 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> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/eaef3a86-2bb8-4844-aed3-aec336917370" alt="cay-nhi-phan-6" /><img style="width: 100%;" src="../../../public_files/031026d4-89ab-4d08-a66e-19df801575db" alt="cay-nhi-phan-7" /></p> <h3 style="text-align: justify;">2.6. C&acirc;y nhị ph&acirc;n c&acirc;n bằng</h3> <p style="text-align: justify;">N&oacute; 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 style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/00b14f62-13b2-4bc2-83bf-06fef09c0592" alt="cay-nhi-phan-8" /></p> <h2 style="text-align: justify;">3. 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.</p> <pre class="language-cpp"><code>struct node { int data; struct node *left; struct node *right; };</code></pre> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/481da107-46f6-475f-8033-d74e4756f3f9" alt="cay-nhi-phan-9" /></p> <p style="text-align: justify;">V&iacute; dụ: Triển khai c&acirc;y nhị ph&acirc;n 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;">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 style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/bf384140-ca7c-4b69-81f0-de1c1ef16cb6" alt="cay-nhi-phan-10" /></p> <h2 style="text-align: justify;">4. Ứng dụng của c&acirc;y nhị ph&acirc;n</h2> <ul style="text-align: justify;"> <li>Để truy cập dữ liệu dễ d&agrave;ng v&agrave; nhanh ch&oacute;ng.</li> <li>Được sử dụng trong thuật to&aacute;n bộ định tuyến.</li> <li>Để triển khai cấu tr&uacute;c dữ liệu vun đống (heap).</li> <li>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. 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>