Tất tần tật về cây trong ngôn ngữ lập trình C/C++

Cây là một cấu trúc phân cấp trên một tập hợp các đối tượng. Một ví dụ quen thuộc về cây, đó là cây thư mục. Cây được sử dụng rộng rãi trong rất nhiều vấn đề khác nhau. Chẳng hạn, nó được áp dụng để tổ chức thông tin trong các hệ cơ sở dữ liệu, để mô tả cấu trúc cú pháp của các chương trình nguồn khi xây dựng các chương trình dịch. Rất nhiều các bài toán mà ta gặp trong các lĩnh vực khác nhau được quy về việc thực hiện các phép toán trên cây. Bài viết ngày hôm nay, cùng Isinhvien đi tìm hiểu về một số khái niệm quan trọng về cây trong ngôn ngữ lập trình C/C++ nhé!

Cây và một số khái niệm thường gặp

Cây: là một tập hợp hữu hạn các phần tử, mỗi phần tử gọi là một nút (Node), trong đó có một nút đặc biệt gọi là gốc (Root), giữa các nút có một quan hệ phân cấp gọi là quan hệ cha con.

Ví dụ về cây:

Ở ví dụ trên, ta có:

• A là nút gốc
• A là nút cha của B, C, D
• B, C, D là các nút con của A

Một số khái niệm thường gặp:

• Cây rỗng là cây không có nút nào cả.
• Cấp của nút là số nút con của nó, vd nút D có cấp là 2.
• Cấp của cây là cấp lớn nhất của các nút có trên cây. Cây có cấp n gọi là cây n phân, ví dụ cây trên là cây tam phân.
• Lá: chính là nút có cấp là 0, ví dụ các lá G, F, H, K , L.
• Mức: Nút gốc có mức là 1. Nút cha có mức i thì nút con có mức i+1
• Chiều cao của cây chính là mức lớn nhất trên cây, ví dụ cây trên có chiều cao 4
• Nút trước, nút sau: Nút x là nút trước của nút y nếu cây con gốc x có chứa nút y, khi đó y là nút sau của nút x. ví dụ D là nút trước của nút K.
• Đường đi (path): Dãy nút u1, u2, . . . uk mà nút bất kỳ ui là cha của nút ui+1 thì dãy đó là đường đi từ nút u1 đến nút uk.
• Độ dài đường đi: số cạnh có trên đường đi, ví dụ dãy DEH là đường đi từ nút D đến nút H với độ dài là 2.
• Rừng là là tập hợp hữu hạn các cây phân biệt
• Cây có thứ tự (ordered tree): là cây mà nếu ta thay đổi vị trí của các cây con thì ta có một cây mới. Như vậy nếu ta đổi các nút bên trái và bên phải thì ta được một cây mới, ví dụ sau đây là 2 cây khác nhau:

Cây nhị phân

Cây nhị phân là cây mà mọi nút trên cây có tối đa 2 con. Trong cây nhị phân người ta có phân biệt nút con trái và nút con phải, như vậy cây nhị phân là cây có thứ tự.

Các dạng đặc biệt của cây nhị phân

• Cây nhị phân suy biến là cây lệch trái hoặc cây lệch phải
• Cây zic-zắc
• Cây nhị phân hoàn chỉnh: các nút ứng với các mức trừ mức cuối cùng đều có 2 con
• Cây nhị phân đầy đủ: có các nút tối đa ở cả mọi mức. Cây nhị phân đầy đủ là một trường hợp đặc biệt của cây nhị phân hoàn chỉnh

Các tính chất:

• Mức i của cây nhị phân có tối đa 2^{i-1} nút
• Cây nhị phân với chiều cao i có tối đa 2^{i}-1 nút
• Cây nhị phân với n nút thì chiều cao h>=log_2(n)

Cây nhị phân tìm kiếm

Cây nhị phân tìm kiếm (CNPTK) là cây nhị phân mà tại mỗi nút bất kỳ thì khóa của nút đang xét lớn hơn khóa của tất cả các nút thuộc cây con trái và nhỏ hơn khóa của tất cả các nút thuộc cây con phải.

Ví dụ về cây nhị phân tìm kiếm:

Nhờ có sự ràng buộc về khóa nên chúng ta có thể dễ dàng thao tác hơn trên Cây nhị phân tìm kiếm như:

• Tìm một phần tử trên cây
• Thêm một phần tử vào cây sao cho phù hợp
• Xóa một phần tử trên cây

==> Xem chi tiết hơn qua bài viết Thuật toán thao tác cơ bản trên cây nhị phân tìm kiếm trong C/C++ của Isinhvien nhé!

Trên đây là một số lý thuyết và khái niệm cơ bản về cây trong ngôn ngữ lập trình C/C++. Nếu các bạn thấy bài viết này hay, bồ ích thì đừng quên chia sẻ nó cho bạn bè cùng biết nhé. Nhớ theo dõi Isinhvien để có thêm nhiều kiến thức hay hơn mỗi ngày. Isinhvien chúc các bạn nhiều sức khỏe và thành công trong cuộc sống!