Các kiểu dữ liệu trong C ( int - float - double - char ...) 
Thuật toán tìm ước chung lớn nhất trong C/C++ 
Cấu trúc lệnh switch case trong C++ (có bài tập thực hành) 
ComboBox - ListBox trong lập trình C# winforms 
Random trong Python: Tạo số random ngẫu nhiên 
Lệnh cin và cout trong C++ 
Cách khai báo biến trong PHP, các loại biến thường gặp 
Download và cài đặt Vertrigo Server 
Thẻ li trong HTML 
Thẻ article trong HTML5 
Cấu trúc HTML5: Cách tạo template HTML5 đầu tiên 
Cách dùng thẻ img trong HTML và các thuộc tính của img 
Thẻ a trong HTML và các thuộc tính của thẻ a thường dùng Tính tổng số cây nhị phân tìm kiếm có thể được tạo ra bởi N nodes trong Java
Tính tổng số cây nhị phân tìm kiếm có thể được tạo ra bởi N nodes trong Java. Đây là bài tập căn bản giúp các bạn nắm vững kiến thức về Tree.
Dưới đây chúng ta sẽ thực hiện chương trình tính tổng số cây nhị phân tìm kiếm có thể được tạo ra bởi N nodes bằng ngôn ngữ Java.
Cách tính tổng số cây nhị phân tìm kiếm có thể được tạo ra bởi N nodes trong Java
Trong phần này, freetuts sẽ hướng dẫn các bạn về thuật toán cũng như cách triển khai bài toán này trong Java.
Để hoàn thành nhiệm vụ chúng ta cần tìm tổng số cây tìm kiếm nhị phân có thể được xây dựng với n giá trị. Sơ đồ dưới đây cho thấy một cây tìm kiếm nhị phân có thể có với giá trị khóa là 3. Vì vậy, chúng ta có thể xây dựng tổng cộng năm cây tìm kiếm nhị phân. Khi chúng ta chọn nút 1 làm nút gốc, chúng ta sẽ có hai cây. Tương tự, một cây với 2 là nút gốc và hai cây khi chúng ta chọn 3 làm nút gốc.
Cách tiếp cận này liên quan đến việc chọn đệ quy một nút làm nút gốc và tạo cây tìm kiếm nhị phân có thể tạo ra được.
Bài viết này được đăng tại [free tuts .net]
Một cách dễ dàng để tính tổng số cây tìm kiếm nhị phân có thể là thông qua số Catalan:
Cn = (2n)! / n! *(n+1)!
Các bước của thuật toán trên như sau:
Bước 1: Khởi tạo class Node có 3 thuộc tính: data, Node left và Node right
Bước 2: root = null
Bước 3: numOfBST() sẽ tìm ra tổng số cây tìm kiếm nhị phân có thể tạo ra từ n đã cho:
- Nó sẽ tính toán số Catalan bằng số n đã cho bằng cách thực hiện
factorial(). - Số Catalan có thể được tính bằng công thức:
Cn = (2n)! / N! *(n+1)! factorial()sẽ tính giai thừa của một số đã cho.
Chương trình tính tổng số cây nhị phân tìm kiếm có thể được tạo ra bởi N nodes trong Java
Dưới đây là chương trình mà freetuts đã viết, mời các bạn tham khảo:
/**
* Học lập trình Java miễn phí tại freetuts.net
*
* @author freetuts
*/
import java.util.Scanner;
public class BinarySearchTree {
public static class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
public Node root;
public BinarySearchTree() {
root = null;
}
public int factorial(int num) {
int fact = 1;
if (num == 0) {
return 1;
} else {
while (num > 1) {
fact = fact * num;
num--;
}
return fact;
}
}
public int numOfBST(int key) {
int catalanNumber = factorial(2 * key) / (factorial(key + 1) * factorial(key));
return catalanNumber;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
BinarySearchTree bt = new BinarySearchTree();
System.out.println("Chương trình được đăng tại freetuts.net");
System.out.print("Nhập số key: ");
int key = sc.nextInt();
System.out.println("Tổng số cây nhị phân tìm kiếm có thể tạo ra được bởi số được nhập vào: " + bt.numOfBST(key));
}
}
Kết quả:
Như vậy chúng ta đã thực hiện xong chương trình tính tổng số cây nhị phân tìm kiếm có thể tạo bởi một số đã cho trong Java. Chúc các bạn thực hiện thành công!!!
