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) 
Lệnh cin và cout trong C++ 
Random trong Python: Tạo số random ngẫu nhiên 
ComboBox - ListBox trong lập trình C# winforms 
Thuật toán kiếm tra số nguyên tố 
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ử lớn nhất của cây nhị phân trong Java
Tìm phần tử lớn 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ử lớn nhất của cây nhị phân trong Java.
Tìm phần tử lớn 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 lớn nhất trong cây nhị phân đã cho. Trước tiên, chúng tôi xác định biến max 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 lớn nhất. So sánh nó với max và lưu trữ tối đa hai trong một biến max. Sau đó, chúng tôi duyệt qua cây con bên phải để tìm node lớn nhất và so sánh nó với giá trị lớn nhất. Cuối cùng, max sẽ có node lớn 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ị lớn 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ử lớn 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
largestElement()sẽ tìm ra phần tử có giá trị lớn 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
maxsẽ lưu trữ dữ liệu của tạm thời. - Tìm ra node lớn nhất trong cây con bên trái bằng cách gọi đệ quy
largestElement(). Lưu trữ giá trị đó trongleftMax. So sánh giá trị củamaxvớileftMaxvà lưu trữ tối đa hai thànhmax. - Tìm ra node lớn nhất trong cây con bên phải bằng cách gọi đệ quy
largestElement(). Lưu trữ giá trị đó trongrightMax. So sánh giá trị củamaxvớirightMaxvà lưu trữ tối đa hai thànhmax. - Cuối cùng,
maxsẽ giữ node lớn 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ử lớn 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 LargestNode {
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 LargestNode() {
root = null;
}
public int largestElement(Node temp) {
if (root == null) {
System.out.println("Tree is empty");
return 0;
} else {
int leftMax, rightMax;
int max = temp.data;
if (temp.left != null) {
leftMax = largestElement(temp.left);
max = Math.max(max, leftMax);
}
if (temp.right != null) {
rightMax = largestElement(temp.right);
max = Math.max(max, rightMax);
}
return max;
}
}
public static void main(String[] args) {
LargestNode bt = new LargestNode();
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ị lớn nhất của cây nhị phân đã cho là: " + bt.largestElement(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 tối đa của cây nhị phân trong Java. Chúc các bạn thực hiện thành công!!!
