[Thực hành] Cài đặt cây tìm kiếm nhị phân

Mục đích

Luyện tập cài đặt cây tìm kiếm nhị phân với thao tác chèn và duyệt theo thứ tự inorder

Mô tả 

Theo mẫu thiết kế của Java Collection Framework API, sử dụng interface Tree để định nghĩa tất cả các thao tác chung cho cây và lớp trừu tượng AbstractTree là sự thực thi cụ thể từ interface Tree. Lớp BST được định nghĩa kế thừa từ lớp AbstractTree

Trong lớp BST gồm các thành phần

• Thuộc tính:
  • root là node gốc của cây
  • size là số node trong cây
  • Phương thức khởi tạo không tham số
  • Phương thức khởi tạo 1 tham số là một mảng đối tượng, khởi tạo mặc định các node trong cây
  • Phương thức path() trả về đường dẫn từ node gốc tới node xác định. (Phương thức này sẽ được cài đặt trong phần bài tập)

Hãy cài đặt cây tìm kiếm nhị phân như sơ đồ trên, với phương thức chèn một node vào cây và duyệt theo thứ tự inorder.

Xây lớp TestBST để kiểm tra lớp BST đã cài đặt.

Hướng dẫn nộp bài:

• Up mã nguồn lên github
• Paste link github vào phần nộp bài

Hướng dẫn

Bước 1: Cài đặt lớp TreeNode

public class TreeNode<E> {     protected E element;     protected TreeNode<E> left;     protected TreeNode<E> right;      public TreeNode(E e) {         element = e;     } }

Bước 2: Cài đặt interface Tree

public interface Tree<E> {
    /**
     * Insert element e into the binary search tree.
     * Return true if the element is inserted successfully.
     */
    public boolean insert(E e);
    /**
     * Inorder traversal from the root
     */
    public void inorder();
    /**
     * Get the number of nodes in the tree
     */
    public int getSize();
}

Bước 3: Cài đặt lớp AbstractTree

public abstract class AbstractTree<E> implements Tree<E> {
    @Override /** Inorder traversal from the root*/
    public void inorder() {
    }
}

Bước 4: Tạo lớp BST

public class BST<E extends Comparable<E>> extends AbstractTree<E> {    protected TreeNode<E> root;    protected int size = 0;    public BST() {    }    public BST(E[] objects) {        for (int i = 0; i < objects.length; i++)            insert(objects[i]);    }}

Bước 5: Cài đặt phương chèn trong BST

@Overridepublic boolean insert(E e) {    if (root == null)        root = createNewNode(e); /*create a new root*/    else {        /*locate the parent node*/        TreeNode<E> parent = null;        TreeNode<E> current = root;        while (current != null) {            if (e.compareTo(current.element) < 0) {                parent = current;                current = current.left;            } else if (e.compareTo(current.element) > 0) {                parent = current;                current = current.right;            } else                return false; /*Duplicate node not inserted*/        }        if (e.compareTo(parent.element) < 0)            parent.left = createNewNode(e);        else            parent.right = createNewNode(e);    }    size++;    return true; /*element inserted successfully*/}protected TreeNode<E> createNewNode(E e) {    return new TreeNode<>(e);} 

Bước 6: Cài đặt phương thức getSize()

@Override
public int getSize() {
   return size;
}

Bước 7: Cài đặt phương thức duyệt cây theo thứ tự inorder

@Overridepublic void inorder() {    inorder(root);}protected void inorder(TreeNode<E> root) {    if (root == null) return;    inorder(root.left);    System.out.println(root.element + " ");    inorder(root.right);}

Bước 8: Tạo lớp TestBST chứa phương thức main thực thi ứng dụng

public class TestBST {
    public static void main(String[] args) {
        //create a BST
        BST<String> tree = new BST<>();
        tree.insert("George");
        tree.insert("Michael");
        tree.insert("Tom");
        tree.insert("Adam");
        tree.insert("Jones");
        tree.insert("Peter");
        tree.insert("Daniel");
        //traverse tree
        System.out.println("Inorder (sorted): ");
        tree.inorder();
       System.out.println("The number of nodes is: " + tree.getSize());
    }
}

Bước 9: Chạy chương trình. Quan sát kết quả.
Guide