Chào ace, bài này chúng ta sẽ tìm hiểu về Cấu trúc dữ liệu Binary Tree trong series tự học về cấu trúc dữ liệu(CTDL) và giải thuật, sau đây cafedev sẽ giới thiệu và chia sẻ chi tiết(khái niệm, độ phức tạp, ứng dụng của nó, code ví dụ…) về nó thông qua các phần sau.
Trees: Không giống như Arrays (mảng), Linked Lists (danh sách liên kết), Stack (ngăn xếp) và Queues (hàng đợi) đều là các cấu trúc dữ liệu dạng tuyến tính (linear data structures), Trees là cấu trúc dữ liệu dạng phân cấp.
Tree Vocalbulary (từ vựng cần biết khi làm việc với Tree): Node ở trên cùng được gọi là root (gốc) của tree. Các phần tử mà nằm ngay dưới một phần tử cụ thể thì được gọi là các children nodes (node con) của nó. Node/Phần tử nằm ngay phía trên một số Nodes/Phần tử cụ thể nào đó, thì được gọi là parent node (node cha) của chúng. Ví dụ, ‘a’ là child (con) của ‘f’, và ‘f’ là parent (cha) của ‘a’. Cuối cùng, các Node/Phần tử mà không có children (con) nào thì được gọi là các leaf nodes/leaves, tức là các node lá hay là các lá.
tree
—-
j <– root
/ \
f k
/ \ \
a h z <– leaves
Nội dung chính
1. Tại sao cần sử dụng Tree?
1. Lý do đầu tiên để sử dụng Tree có thể là vì chúng ta muốn lưu trữ thông tin/dữ liệu dưới dạng một hệ thống phân cấp tự nhiên. Ví dụ: File system – Hệ thống tệp tin trên máy tính.
file system
———–
/ <– root
/ \
… home
/ \
ugrad course
/ / | \
… cs101 cs112 cs113
2. Các loại Trees (với một số cách bố trí được thiết lập, ví dụ như BST – Binary Search Tree – Cây tìm kiếm nhị phân) cung cấp khả năng truy cập/tìm kiếm với tốc độ vừa phải (nhanh hơn so với Linked List, và chậm hơn so với Array).
3. Các loại Trees cung cấp khả năng chèn/xóa node với tốc độ vừa phải (nhanh hơn so với Array và chậm hơn so với Unordered Linked List – Danh sách liên kết không có thứ tự).
4. Giống với Linked List và không giống với Array, Tree không có một giới hạn cận trên nào về số lượng các nodes, bởi vì ở trong Tree, các nodes đều được liên kết với nhau bằng các pointers – con trỏ.
2. Các ứng dụng chính của Trees
1. Cung cấp khả năng xử lý/thao tác với dữ liệu ở dạng phân cấp (hierachical data).
2. Làm cho việc tìm kiếm dữ liệu/thông tin trở nên dễ dàng hơn.
3. Cung cấp khả năng xử lý/thao tác với các danh sách dữ liệu đã được sắp xếp (sorted lists of data).
4. Đóng vai trò như là một workflow (quy trình làm việc) trong quá trình hợp lại/ghép lại các hình ảnh kỹ thuật số nhằm tạo ra các hiệu ứng hình ảnh.
5. Được sử dụng trong các thuật toán định tuyến/tìm đường (router algorithms).
6. Cho phép hình thành nên một cấu trúc dữ liệu có khả năng đưa ra các quyết định khác nhau ở các giai đoạn khác nhau (multi-stage decision-making).
3. Binary Tree
Binary Tree – Cây nhị phân là một loại cấu trúc dữ liệu thuộc họ Tree mà trong đó các nodes/phần tử của nó chỉ có nhiều nhất hai node con. Bởi vì mỗi node/phần tử bên trong Binary Tree chỉ có thể có nhiều nhất 2 node con, nên chúng ta thường đặt tên cho các node con này là node con bên trái – hay node trái và node con bên phải – hay nói ngắn gọn là node phải.
4. Biểu diễn Binary Tree trong ngôn ngữ lập trình C
Trong ngôn ngữ lập trình C, một tree có thể được biểu diễn bằng một pointer – con trỏ trỏ tới node trên cùng của tree. Nếu tree đang empty – trống (tức là không có node/phần tử nào trong tree), thì giá trị của node root (node gốc nằm trên cùng của tree) sẽ là NULL.
Một node của tree sẽ chứa các phần sau:
1. Data – Dữ liệu
2. Pointer to left child – Con trỏ trỏ đến node con bên trái của nó
3. Pointer to right child – Con trỏ trỏ đến node con bên phải của nó
Trong ngôn ngữ lập trình C, chúng ta có thể biểu diễn một node của tree bằng cách sử dụng struct. Dưới đây là ví dụ về một node của tree, trong đó dữ liệu được chứa bên trong node này thuộc kiểu integer và bằng các ngôn ngữ khác:
Code C/C++
struct node
{
int data;
struct node *left;
struct node *right;
};
Code Python
# A Python class that represents an individual node
# in a Binary Tree
class Node:
def __init__(self,key):
self.left = None
self.right = None
self.val = key
Java
/* Class containing left and right child of current
node and key value*/
class Node
{
int key;
Node left, right;
public Node(int item)
{
key = item;
left = right = null;
}
}
C#
/* Class containing left and right child
of current node and key value*/
class Node
{
int key;
Node left, right;
public Node(int item)
{
key = item;
left = right = null;
}
}
5. Ví dụ xây dựng một tree đơn giản
Trong phần này, chúng ta sẽ tham khảo các ví dụ sử dụng các ngôn ngữ lập trình khác nhau để cài đặt một cấu trúc dữ liệu tree đơn giản, gồm 4 node, như sau:
tree
—-
1 <– root
/ \
2 3
/
4
Sử dụng C++:
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* left;
struct Node* right;
// val is the key or the value that
// has to be added to the data part
Node(int val)
{
data = val;
// Left and right child for node
// will be initialized to null
left = NULL;
right = NULL;
}
};
int main()
{
/*create root*/
struct Node* root = new Node(1);
/* following is the tree after above statement
1
/ \
NULL NULL
*/
root->left = new Node(2);
root->right = new Node(3);
/* 2 and 3 become left and right children of 1
1
/ \
2 3
/ \ / \
NULL NULL NULL NULL
*/
root->left->left = new Node(4);
/* 4 becomes left child of 2
1
/ \
2 3
/ \ / \
4 NULL NULL NULL
/ \
NULL NULL
*/
return 0;
}
Sử dụng C:
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *left;
struct node *right;
};
/* newNode() allocates a new node with the given data and NULL left and
right pointers. */
struct node* newNode(int data)
{
// Allocate memory for new node
struct node* node = (struct node*)malloc(sizeof(struct node));
// Assign data to this node
node->data = data;
// Initialize left and right children as NULL
node->left = NULL;
node->right = NULL;
return(node);
}
int main()
{
/*create root*/
struct node *root = newNode(1);
/* following is the tree after above statement
1
/ \
NULL NULL
*/
root->left = newNode(2);
root->right = newNode(3);
/* 2 and 3 become left and right children of 1
1
/ \
2 3
/ \ / \
NULL NULL NULL NULL
*/
root->left->left = newNode(4);
/* 4 becomes left child of 2
1
/ \
2 3
/ \ / \
4 NULL NULL NULL
/ \
NULL NULL
*/
getchar();
return 0;
}
Sử dụng Python:
# Python program to introduce Binary Tree
# A class that represents an individual node in a
# Binary Tree
class Node:
def __init__(self,key):
self.left = None
self.right = None
self.val = key
# create root
root = Node(1)
''' following is the tree after above statement
1
/ \
None None'''
root.left = Node(2);
root.right = Node(3);
''' 2 and 3 become left and right children of 1
1
/ \
2 3
/ \ / \
None None None None'''
root.left.left = Node(4);
'''4 becomes left child of 2
1
/ \
2 3
/ \ / \
4 None None None
/ \
None None'''
Sử dụng Java:
/* Class containing left and right child of current
node and key value*/
class Node
{
int key;
Node left, right;
public Node(int item)
{
key = item;
left = right = null;
}
}
// A Java program to introduce Binary Tree
class BinaryTree
{
// Root of Binary Tree
Node root;
// Constructors
BinaryTree(int key)
{
root = new Node(key);
}
BinaryTree()
{
root = null;
}
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*create root*/
tree.root = new Node(1);
/* following is the tree after above statement
1
/ \
null null */
tree.root.left = new Node(2);
tree.root.right = new Node(3);
/* 2 and 3 become left and right children of 1
1
/ \
2 3
/ \ / \
null null null null */
tree.root.left.left = new Node(4);
/* 4 becomes left child of 2
1
/ \
2 3
/ \ / \
4 null null null
/ \
null null
*/
}
}
Sử dụng C#:
// A C# program to introduce Binary Tree
using System;
/* Class containing left and right child
of current node and key value*/
public class Node
{
public int key;
public Node left, right;
public Node(int item)
{
key = item;
left = right = null;
}
}
public class BinaryTree
{
// Root of Binary Tree
Node root;
// Constructors
BinaryTree(int key)
{
root = new Node(key);
}
BinaryTree()
{
root = null;
}
// Driver Code
public static void Main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*create root*/
tree.root = new Node(1);
/* following is the tree after above statement
1
/ \
null null */
tree.root.left = new Node(2);
tree.root.right = new Node(3);
/* 2 and 3 become left and right children of 1
1
/ \
2 3
/ \ / \
null null null null */
tree.root.left.left = new Node(4);
/* 4 becomes left child of 2
1
/ \
2 3
/ \ / \
4 null null null
/ \
null null
*/
}
}
// This code is contributed by PrinciRaj1992
6. Tổng kết
Tree là một cấu trúc dữ liệu có dạng phân cấp. Công dụng chính của Tree bao gồm: Giúp duy trì dữ liệu ở dạng phân cấp, cung cấp khả năng truy cập và các thao tác chèn/xóa node với tốc độ vừa phải. Binary Tree – Cây nhị phân là một trường hợp đặc biệt của Tree mà trong đó mọi node của nó đều chỉ có nhiều nhất hai node con.
Nguồn và Tài liệu tiếng anh tham khảo:
Tài liệu từ cafedev:
- Full series tự học Cấu trúc dữ liệu và giải thuật từ cơ bản tới nâng cao tại đây nha.
- Ebook về Cấu trúc dữ liệu và giải thuật tại đây.
- Các series tự học lập trình khác
Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:
Chào thân ái và quyết thắng!
 và giải thuật, sau đây cafedev sẽ giới thiệu và chia sẻ chi){kind=link}