Cấu trúc Tree trong Java Collection Framework

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)

Minh họa cây nhị phân

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


Hãy tham gia nhóm Học lập trình để thảo luận thêm về các vấn đề cùng quan tâm.

Leave a Reply

Your email address will not be published. Required fields are marked *