Cấu trúc dữ liệu dạng cây (Tree) là một cấu trúc dữ liệu phi tuyến phổ biến, được sử dụng để mô tả các mối quan hệ phân cấp. Nó gồm các nút (nodes) được tổ chức thành một cấu trúc phân nhánh. Mỗi nút chứa dữ liệu và có thể có các nút con.

Dữ liệu phi tuyến (Non-linear Data Structure) là kiểu cấu trúc dữ liệu trong đó mối quan hệ giữa các phần tử không theo thứ tự tuyến tính

Đặc điểm chính của cấu trúc dữ liệu Tree

1. Nút gốc (Root):
   • Là nút đầu tiên của cây.
   • Một cây chỉ có một nút gốc duy nhất.
2. Nút con (Child):
   • Các nút xuất phát từ một nút cha được gọi là các nút con.
3. Nút cha (Parent):
   • Một nút được gọi là cha nếu nó có các nút con.
4. Nút lá (Leaf):
   • Là các nút không có nút con.
5. Mức độ (Depth/Level):
   • Mức độ của một nút là số cạnh từ nút gốc đến nó.
6. Chiều cao của cây (Height):
   • Là số mức độ lớn nhất của bất kỳ nút nào trong cây.
7. Độ bậc của nút (Degree):
   • Là số nút con trực tiếp của một nút.

Cấu trúc cơ bản của cây

• Mỗi nút trong cây bao gồm:
  1. Dữ liệu.
  2. Con trỏ đến các nút con.

Ví dụ biểu diễn cây trong Python:

class Node:
    def __init__(self, data):
        self.data = data
        self.children = []  # Danh sách các nút con

class Tree:
    def __init__(self, root):
        self.root = root

# Tạo cây
root = Node("A")  # Nút gốc
root.children.append(Node("B"))  # Nút con của A
root.children.append(Node("C"))
root.children[0].children.append(Node("D"))  # Nút con của B
root.children[1].children.append(Node("E"))  # Nút con của C

Cấu trúc cây ở ví dụ trên:

       A
     /   \
    B     C
   /       \
  D         E

Trê (Tree) là một cấu trúc dữ liệu phi tuyến phổ biến, được sử dụng để mô tả các mối quan hệ phân cấp. Nó gồm các nút (nodes) được tổ chức thành một cấu trúc phân nhánh. Mỗi nút chứa dữ liệu và có thể có các nút con.

---

Đặc điểm chính của cấu trúc dữ liệu Tree

1. Nút gốc (Root):
   • Là nút đầu tiên của cây.
   • Một cây chỉ có một nút gốc duy nhất.
2. Nút con (Child):
   • Các nút xuất phát từ một nút cha được gọi là các nút con.
3. Nút cha (Parent):
   • Một nút được gọi là cha nếu nó có các nút con.
4. Nút lá (Leaf):
   • Là các nút không có nút con.
5. Mức độ (Depth/Level):
   • Mức độ của một nút là số cạnh từ nút gốc đến nó.
6. Chiều cao của cây (Height):
   • Là số mức độ lớn nhất của bất kỳ nút nào trong cây.
7. Độ bậc của nút (Degree):
   • Là số nút con trực tiếp của một nút.

---

Cấu trúc cơ bản của cây

• Mỗi nút trong cây bao gồm:
  1. Dữ liệu.
  2. Con trỏ đến các nút con.

Ví dụ biểu diễn cây trong Python:

pythonCopy codeclass Node:
    def __init__(self, data):
        self.data = data
        self.children = []  # Danh sách các nút con

class Tree:
    def __init__(self, root):
        self.root = root

# Tạo cây
root = Node("A")  # Nút gốc
root.children.append(Node("B"))  # Nút con của A
root.children.append(Node("C"))
root.children[0].children.append(Node("D"))  # Nút con của B
root.children[1].children.append(Node("E"))  # Nút con của C

Cấu trúc cây ở ví dụ trên:

mathematicaCopy code       
       A
     /   \
    B     C
   /       \
  D         E

---

Phân loại cây

1. Cây tổng quát (General Tree):
   • Một nút có thể có bất kỳ số lượng nút con nào.
2. Cây nhị phân (Binary Tree):
   • Mỗi nút có tối đa 2 nút con (trái và phải).

    A
   / \
  B   C

Cây nhị phân tìm kiếm (Binary Search Tree – BST):

• Là một cây nhị phân, trong đó:
  • Các nút ở bên trái nhỏ hơn nút cha.
  • Các nút ở bên phải lớn hơn nút cha.

Cây cân bằng (Balanced Tree):

• Là cây mà chiều cao của hai nhánh con bất kỳ không chênh lệch quá nhiều (như AVL Tree, Red-Black Tree).

Cây AVL:

• Là cây nhị phân tìm kiếm tự cân bằng, đảm bảo rằng chênh lệch chiều cao của hai nhánh con không vượt quá 1.

Heap Tree:

• Là một dạng cây nhị phân đặc biệt, trong đó:
  • Max Heap: Nút cha luôn lớn hơn hoặc bằng các nút con.
  • Min Heap: Nút cha luôn nhỏ hơn hoặc bằng các nút con.

Thao tác chính trên cây

Duyệt cây (Traversal):

• Duyệt theo chiều sâu (Depth-First Search – DFS):
  • Thứ tự: Preorder (NLR), Inorder (LNR), Postorder (LRN).
  Duyệt theo chiều rộng (Breadth-First Search – BFS):
  • Duyệt theo từng mức từ trên xuống dưới.

Ví dụ duyệt Preorder:

def preorder(node):
    if not node:
        return
    print(node.data, end=" ")  # Xử lý nút hiện tại
    for child in node.children:
        preorder(child)

preorder(root)  # Output: A B D C E

1. Thêm nút:
   • Tùy thuộc vào loại cây, thêm nút vào đúng vị trí theo quy tắc.
2. Xóa nút:
   • Phức tạp hơn, đặc biệt khi cần duy trì tính chất của cây (như BST).
3. Tìm kiếm:
   • Tìm kiếm tuần tự hoặc theo quy tắc của loại cây (nhanh hơn ở BST).

Ứng dụng của Tree

1. Quản lý dữ liệu phân cấp:
   • Hệ thống file/thư mục, cây thư mục.
2. Cây nhị phân tìm kiếm (BST):
   • Tìm kiếm nhanh hơn mảng/sắp xếp O(log(n)) so với O(n).
3. Heap Tree:
   • Quản lý bộ nhớ, thuật toán sắp xếp (Heap Sort).
4. Cây quyết định (Decision Tree):
   • Trí tuệ nhân tạo (AI) và học máy (Machine Learning).
5. Cây đồ thị (Spanning Tree):
   • Tìm đường đi ngắn nhất trong đồ thị.