Xây Dựng CTDL Cây Nhị Phân Với Ngôn Ngữ C

Xây Dựng CTDL Cây Nhị Phân Với Ngôn Ngữ C

Cây tìm kiếm nhị phân (Binary Search Tree) là một trong những cấu trúc dữ liệu cơ bản mà mọi lâp trình viên đều phải biết. Cây tìm kiếm nhị phân được biết đến là cấu trúc hỗ trợ người sử dụng trong việc lưu trữ cũng như tìm kiếm dữ liệu dễ dàng hơn.

Các bạn có thể tìm hiểu khái niệm về cây tìm kiếm nhị phân trong link sau: 5-phut-thong-thao-binary-search-tree

Trong bài viết này, mình và các bạn sẽ cùng nhau xây dựng cấu trúc cây nhị phân bằng ngôn ngữ C với các thao tác đơn giản sau:

  • Insert: thêm dữ liệu
  • Search: tìm kiếm dữ liệu
  • Remove: xóa dữ liệu
  • Traversal: duyệt cây, gồm 3 loại chính: preorder, inorder, postorder.

Chuẩn bị

Để bắt đầu xây dựng cấu trúc cây nhị phân ta tạo 1 file thư viện là BST.h để lưu các function và 1 file BST.c để xây dựng các function. Sau đây là file BST.h:

#ifndef _BST_H_
#define _BST_H_

typedef int element_t;

struct TreeNode {
  element_t data;
  struct TreeNode *left;
  struct TreeNode *right;
};

typedef struct TreeNode* tree;

tree createNullTree();

int isNullTree(tree t);

tree createLeaf(element_t x);

tree insertBST(tree t, element_t x);

tree removeBST(tree t, element_t x);

tree searchBST(tree t, element_t x);

void inorderPrint(tree t);

void preorderPrint(tree t);

void postorderPrint(tree t);

#endif

Ở đây, element_t là giá trị của 1 nút trong cây, mình để giá trị là kiểu int

Tiếp theo tạo nút với struct, mỗi 1 nút sẽ là 1 con trỏ kiểu TreeNode, 1 nút bao gồm 1 biến data chứa giá trị, 1 biến con trỏ để lưu địa chỉ của nút con trái,  1 biến con trỏ để lưu địa chỉ của nút con phải. Sau đó lần lượt là các hàm để phục vụ cho việc xây dựng các thao tác đã nói ở trên.

Đây là file BST.c để chúng ta xây dựng code:

#include<stdio.h>
#include <stdlib.h>
#include <string.h>
#include "BST.h"
//
tree createNullTree() {
	return (tree)NULL;
}
//
tree createLeaf(element_t x) {
  	tree tmp = (tree)malloc(sizeof(struct TreeNode));
  	tmp->data = x;
  	tmp->left = (tree)NULL;
  	tmp->right = (tree)NULL;
  	return tmp;
}
//
int isNullTree(tree t) {
	return (t == NULL);
}
//
tree insertBST(tree t, element_t x){
}
//
tree left_most(tree t){
}
//
tree removeBST(tree root, element_t x){
}
//
tree searchBST(tree t, element_t x){
}

void inorderPrint(tree t){
}

void preorderPrint(tree t){
}

void postorderPrint(tree t){
}

Mình sử dụng 1 số thư viện stdio, stdlib và cả thư viện BST.h để phục vụ cho việc xây dựng.

Tiếp đến là các hàm:

  • createNullTree() là để tạo cây rỗng
  • createLeaf() với tham số truyền vào là element_t, dùng để tạo nút lá
  • isNullTree() với tham số truyền vào là 1 con trỏ, dùng để kiểm tra cây rỗng
  • Hàm insertBST(), removeBST(), searchBST() để thêm, xóa và tìm kiếm

Các bạn có thể thấy mình đã tạo sẵn code cho hàm tạo cây rỗng, hàm tạo nút lá và hàm kiểm tra cây rỗng.

Sau đây là các thao tác trong cây nhị phân sẽ được xây dựng trên file BST.c.

1. Insert

Khi muốn thêm một giá trị x vào cây nhị phân, ta bắt đầu từ nút gốc (root), nếu giá trị x nhỏ hơn giá trị nút gốc thì tìm vị trí trống của cây con bên trái nút gốc, nếu x lớn hơn giá trị nút gốc ta tìm vị trí trống của cây con bên phải nút gốc. Trường hợp tìm được giá trị của 1 node trong cây bằng với x thì xác nhận x đã tồn tại trong cây.

Pseudo code cho insert:

insertBST(root, element x)

            if t == NIL

                        root.data = x

                        return root

            else if root.data < x

                        root.right-child = insertBST(root.right-child, x)

            else if root.data > x

                        root.left-child = insert(root.left-child, x)

            return root

Code cho function insertBST:

tree insertBST(tree t, element_t x){

	if(isNullTree(t)) 
		return createLeaf(x);
	
  	if(t->data == x) return t;
  	else if(t->data > x){
    
    	t->left = insertBST(t->left, x);
    	return t;
  	}else{
    	 t->right = insertBST(t->right, x);
    	return t;
    }
}

2. Remove

Trong hoạt động xóa 1 node của cây nhị phân chúng ta sẽ gặp phải 3 trường hợp sau:

  • Node cần xóa chỉ có 1 node con (trái hoặc phải): thay thế nút cần xóa với nút con.
  • Node cần xóa không có node con: đơn giản chỉ cần xóa nút đó đi.
  • Node cần xóa có cả 2 node: tìm 1 node thay thế, thỏa mãn điều kiện lớn hơn tất cả node con trái của nút cần xóa và bé hơn tất cả node con phải của nút cần xóa.

Cách giải quyết cho 3 trường hợp này được giải thích rõ hơn trong đường link gắn ở đầu bài.

Pseudo code cho cả 3 trường hợp:

removeBST(root, x)

          if root == NIL

                    return root

          if root.data == x

                    if root.left-child == NIL

                              root = root.right-child

                              return root

                    else if root.right-child == NIL

                              root = root.left-child

                              return root

                    else

                              tmp = left-most(root.right-child)

                              root.data = tmp.data;

                              root.right-child = removeBST(root.right-child, tmp.data)

          else if root.data > x

                    root.left-child = removeBST(root.left-child, x)

          else if roor.data < x

                    root.right-child = removeBST(root.right-child, x)

          return root

Code cho function removeBST:

tree left_most(tree t){
	if(t == NULL)
		return t;
	else{
		while(t->left != NULL){
			t = t->left;
		}
	}
	return t;
}
//
tree removeBST(tree root, element_t x){
	if(isNullTree(root)) return root;
	
	if(searchBST(root,x) != NULL){
	
		if(root->data == x){
			//
			if(root->left == NULL){
				tree tmp = root->right;
				free(root);
				return tmp;	
			}	
			//
			if(root->right == NULL){
				tree tmp = root->left;
				free(root);
				return tmp;
			}
			//
			root->data = left_most(root->right)->data;
			root->right = removeBST(root->right, root->data);
			return root;
		}else if(root->data > x){
			root->left = removeBST(root->left, x);
		}else{
			root->right = removeBST(root->right, x);
		}
	}else{
		printf("\nKhong ton tai gia tri can tim!");
	}
	
	return root;
}

Trong phần này, mình tạo thêm một function left_most() với tham số truyền vào là 1 node của cây nhị phân, hàm này là để trả về node nhỏ nhất của 1 cây, nói cách khác chính là node trái cùng của 1 cây nhị phân. Node này chính là nút thế (successor) trong trường hợp 3. 

3. Search

Để bắt đầu hoạt động tìm kiếm một giá trị x cho trước, chúng ta bắt đầu từ nút gốc (root). Nếu giá trị x nhỏ hơn giá trị của root thì chuyển đến so sánh với node con trái của root vì mọi node bên trái root sẽ nhỏ hơn root nên nếu giá trị x có tồn tại thì chỉ có thể ở bên trái root, còn với x lớn hơn giá trị của root thì chuyển đến so sánh với node con phải của root.

Pseudo code cho search:

searchBST(root, x)

            if root == NIL

                        return root

            if root.data = x

                        return root

            else if root.data < x

                        return searchBST(root.right-child, x)

            else id root.data > x

                        return searchBST(root.left-child, x)

Code cho function searchBST:

tree searchBST(tree t, element_t x){

  	if(isNullTree(t)) return NULL;

  	if(t->data==x) return t;
  	else if(t->data < x) return searchBST(t->right, x);
  	else{
    	return searchBST(t->left, x);
  	}

}

4.Traversal

4.1. Preorder traversal

Với cách duyệt này ta sẽ đi qua node cha trước sau đến node con trái rồi mới đến node con phải.

Pseudo code cho Preorder:

preorderPrint(root)

            print root.data

            preorderPrint(root.left-child)

            preorderPrint(root.right-child)

Code cho function preorderPrint:

void preorderPrint(tree t){
  if(t != NULL){
    printf("%d, ", t->data);
    preorderPrint(t->left);
    preorderPrint(t->right);
  }
}

4.2. Inorder traversal

Trong cách duyệt in-order, duyệt lần lượt node con trái sau đến node cha rồi đến node con phải.

Pseudo code cho Inorder:

inorderPrint(root)

            inorderPrint(root.left-child)

            print root.data

            inorderPrint(root.right-child)

Code cho function inorderPrint:

void inorderPrint(tree t){
  if(t != NULL){
    inorderPrint(t->left);
    printf("%d, ", t->data);
    inorderPrint(t->right);
  }
}

4.3. Postorder traversal

Ta duyệt lần lượt node con trái, node con phải rồi đến node cha.

Pseudo code cho Postorder:

postorderPrint(root)

            postorderPrint(root.left-child)

            postorderPrint(root.right-child)

            print root.data

Code cho function postorderPrint:

void postorderPrint(tree t){
  if(t != NULL){
    postorderPrint(t->left);
    postorderPrint(t->right);
    printf("%d, ", t->data);
  }

}

Sau khi đã hoàn thành code cho những chức năng cơ bản trên, các bạn có thể viết 1 chương trình main để chạy thử thư viện vừa code và kiểm tra lại như hình sau:

Đây là kết quả sau khi chạy câu lệnh gcc với Command Prompt và insert lần lượt 5,2,3,9,6,10, rồi remove 5, sau đó duyệt cây với preorder traversal:

Các bạn có thể tham khảo 3 file BST.c, BST.h, main.c tại đây: BST-in-C.

Lời kết

Qua bài viết này mình và các bạn đã xây dựng được cấu trúc cây tìm kiếm nhị phân với những thao tác cơ bản thêm, xóa, tìm kiếm, duyệt cũng như ôn lại những kiến thức cơ bản của lập tình C: con trỏ, đệ quy, ép kiểu dữ liệu, cấu trúc struct... Bạn đọc có thể tự viết thêm những thao tác, chức năng mới cho 1 cấu trúc dữ liệu cây nhị phân như tính tổng giá trị node, đếm leaf node, tính level của cây,...Việc này sẽ giúp các bạn ôn lại kiến thức cũ và học thêm được những kiến thức mới. Nếu có thắc mắc bạn đọc có thể comment bên dưới để mọi người cùng giải đáp. Cảm ơn bạn đọc, chúc bạn thành công trên con đường học tập!