Cấu trúc Tree trong Java Collection Framework


Giới thiệu Tree và Binary Tree

  • Tree lưu trữ dữ liệu trên các node
  • Các node có mối quan hệ cha-con, node trên cùng được gọi là node gốc (root node)
  • Binary Tree (Cây nhị phân) là cây mà mỗi node có 0, 1 hoặc 2 cây con (subtree)
  • 2 cây con được gọi lần lượt là left-subtree (cây con trái) và right-subtree (cây con phải)

>> Xem ngay Tài liệu Java Core giúp bạn “Nâng Cấp” kỹ năng lập trình

Các khái niệm

  • Độ dài của đường đi (length of the path) là số lượng các cạnh
  • Chiều sâu của node là độ dài của đường đi tính từ root node đến node đó
  • Node anh em (sibling) là các node có cùng node cha
  • Node không có node con thì gọi là node lá (leaf node)
  • Chiều cao của cây là độ dài của đường đi từ node gốc đến node lá

Binary Search Tree (BST)

  • Binary Tree (Cây nhị phân) là một cấu trúc phân tầng
  • Bao gồm:
    • Một nút gốc (root)
    • Một cây con trái (left subtree)
    • Một cây con phải (right subtree)
    • Một nút có thể có 0, 1 hoặc 2 cây con
  • Cây tìm kiếm nhị phân:
  • Là cây nhị phân có trật tự
  • Giá trị nút bên trái nhỏ hơn nút hiện tại
  • Giá trị nút bên phải lớn hơn nút hiện tại
  • BSTđược biểu diễn bằng một tập các node liên kết với nhau
  • Mỗi node chứa dữ liệu và 2 liên kết: 1 liên kết sang node con bên trái và. 1 liên kết sang node con bên phải

Minh hoạ cấu trúc cây tìm kiếm nhị phân

Triển khai BST

class TreeNode<E> {     protected E element;     protected 
   TreeNode<E> left;     protected TreeNode<E> right;     public TreeNode(E e) {         element = e;     } }
 TreeNode<Integer> root = new TreeNode<>(60); root.left = new TreeNode<>(55); root.right = new TreeNode<>(100);

Tìm kiếm trên BST

public boolean search(E element) {     TreeNode<E> current = root;      while (current != null) {         if (element < current.element) {             current = current.left;         } else if (element > current.element) {             current = current.right;         } else             return true;     }     return false; }

Thêm phần tử vào BST

Minh hoạ thao tác thêm phần tử vào BST

Bài viết liên quan

Leave a Reply

Your email address will not be published.