Cây nhị phân – Binary Tree

0
This entry is part 9 of 10 in the series Cấu trúc dữ liệu

Phần trước mình đã hướng dẫn các bạn về danh sách liên kết. Trong phần hướng dẫn tiếp theo này, chúng ta sẽ đi tìm hiểu về cấu trúc dữ liệu Cây. Bài hôm nay sẽ trình bày về cây nhị phân(binary tree), bài tiếp theo sẽ trình bày về cây tìm kiếm nhị phân(binary seach tree).

1. Lý thuyết về cây nhị phân

Cây nhị phân là một cấu trúc bao gồm các Node, trong đó mỗi Node bao gồm 3 thành phần sau:

  1. Data element: Lưu giữ giá trị 1 phần tử với kiểu dữ liệu bất kỳ
  2. Left pointer: Con trỏ trỏ tới cây nhị phân bên trái của Node
  3. Right pointer: Con trỏ trỏ tới cây nhị phân bên phải của Node

Nếu một cây nhị phân trống, nó sẽ được biểu diễn thành con trỏ NULL. Hình ảnh dưới đây sẽ cho bạn cái nhìn tổng quát về cây nhị phân:

Hình ảnh minh họa cấu trúc Cây nhị phân
Hình ảnh minh họa cấu trúc Cây nhị phân

Các thuật ngữ sử dụng trong cấu trúc Cây

  • Root: Node tổ tiên của cây. Là Node mà không có cha
  • Child: Là Node con của một Node cụ thể nào đó
  • Parent: Ngược lại của Child
  • Siblings: Các Node có cùng một cha
  • Descendant: Node có thể truy cập bằng cách duyệt từ cha tới con
  • Ancestor: Node có thể truy cập bằng cách duyệt từ con đến cha
  • Leaf: Node không có Child
  • Internal node: Node có ít nhất 1 Child
  • External node: Node không có Child

2. Cài đặt cây nhị phân

Chúng ta cần định nghĩa kiểu dữ liệu Node cho cây nhị phân. Như đã trình bày, mỗi Node của cây nhị phân sẽ như sau:

2.1. Khởi tạo 1 Node

Khởi tạo Node gốc, không sử dụng con trỏ.

Khởi tạo con trỏ Node:

2.2. Tính chiều cao/ chiều sâu của cây

Ý tưởng của việc tính chiều cao là duyệt theo thứ tự PostOrder và lưu trên 2 biến độc lập cho cây con trái và cây con phải. Kết quả chiều sâu của cây là giá trị lớn hơn.

Đó là các chức năng cơ bản có trong cây nhị phân. Chúng ta sẽ đi sâu hơn khi tìm hiểu về cây tìm kiếm nhị phân ở bài tiếp theo.

3. Ứng dụng của Cây

  1. Phân cấp dữ liệu
  2. Hỗ trợ tìm kiếm dễ dàng hơn(xem thêm về duyệt cây)
  3. Thao tác trên các danh sách dữ liệu đã được sắp xếp
  4. Sử dụng như một quy trìn để tổng hợp hình ảnh kỹ thuật số cho hiệu ứng hình ảnh
  5. Sử dụng trong các thuật toán định tuyến luồng

 

Series Navigation<< Danh sách liên kết vòng – Circular Linked ListCây tìm kiếm nhị phân – Binary search tree >>

ĐỂ LẠI BÌNH LUẬN

Vui lòng nhập nội dung bình luận
Vui lòng nhập tên