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) 
Thuật toán kiếm tra số nguyên tố 
Lệnh cin và cout trong C++ 
Random trong Python: Tạo số random ngẫu nhiên 
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ìm phần tử nhỏ nhất của cây nhị phân trong Java
Tìm phần tử nhỏ nhất của cây nhị phân trong Java. Đây là một dạng bài tập để giúp bạn hiểu rõ hơn về Tree trong Java.
Dưới đây chúng ta sẽ thực hiện chương trình tìm phần tử nhỏ nhất của cây nhị phân trong Java.
Tìm phần tử nhỏ nhất của cây nhị phân 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.
Theo yêu cầu bài toán thì chúng ta sẽ tìm ra node nhỏ nhất trong cây nhị phân đã cho. Trước tiên, chúng tôi xác định biến min sẽ chứa dữ liệu của root. Sau đó, chúng tôi duyệt qua cây con bên trái để tìm node nhỏ nhất. So sánh nó với min và lưu trữ nhỏ nhất hai trong một biến min. Sau đó, chúng tôi duyệt qua cây con bên phải để tìm node nhỏ nhất và so sánh nó với giá trị nhỏ nhất. Cuối cùng, min sẽ có giá trị nhỏ nhất.
Bài viết này được đăng tại [free tuts .net]
Với cây nhị phân trên, để tìm kiếm phần tử có giá trị nhỏ nhất hãy cùng freetuts tìm hiểu về thuật toán của chương trình.
Thuật toán tìm phần tử nhỏ nhất của cây nhị phân trong Java
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: Dữ liệu của node sẽ được gán là data, các node left và right là null
Bước 3:
- Root được gán bằng null
smallestElement()sẽ tìm ra phần tử có giá trị nhỏ nhất.- Nó kiểm tra xem gốc có rỗng không, nếu có thì nghĩa là cây rỗng.
- Nếu cây không trống, hãy xác định biến
minsẽ lưu trữ dữ liệu của tạm thời. - Tìm ra node nhỏ nhất trong cây con bên trái bằng cách gọi đệ quy
smallestElement(). Lưu trữ giá trị đó trongleftmin. So sánh giá trị củaminvớileftminvà lưu trữ nhỏ nhất hai thànhmin. - Tìm ra node nhỏ nhất trong cây con bên phải bằng cách gọi đệ quy
smallestElement(). Lưu trữ giá trị đó trongrightmin. So sánh giá trị củaminvớirightminvà lưu trữ nhỏ nhất hai thànhmin. - Cuối cùng,
minsẽ giữ node nhỏ nhất trong cây nhị phân.
Cùng freetuts triển khai chương trình dưới đây để có thể hiểu hơn về yêu cầu bài toán.
Chương trình tìm kiếm phần tử nhỏ nhất của cây nhị phân 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
*/
public class smallestNode {
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 smallestNode() {
root = null;
}
public int smallestElement(Node temp) {
if (root == null) {
System.out.println("Tree is empty");
return 0;
} else {
int leftmin, rightmin;
int min = temp.data;
if (temp.left != null) {
leftmin = smallestElement(temp.left);
min = Math.min(min, leftmin);
}
if (temp.right != null) {
rightmin = smallestElement(temp.right);
min = Math.min(min, rightmin);
}
return min;
}
}
public static void main(String[] args) {
smallestNode bt = new smallestNode();
bt.root = new Node(15);
bt.root.left = new Node(20);
bt.root.right = new Node(35);
bt.root.left.left = new Node(74);
bt.root.right.left = new Node(55);
bt.root.right.right = new Node(6);
System.out.println("Chương trình được đăng tại freetuts.net");
System.out.println("Phần tử có giá trị nhỏ nhất của cây nhị phân đã cho là: " + bt.smallestElement(bt.root));
}
}
Kết quả:
Như vậy chúng ta đã thực hiện xong chương trình tìm giá trị độ rộng nhỏ nhất của cây nhị phân trong Java. Chúc các bạn thực hiện thành công!!!
