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 chiều rộng tối đa của cây nhị phân trong Java
Tìm chiều rộng tối đa 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 chiều rộng tối đa của cây nhị phân trong Java.
Tìm chiều rộng tối đa 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 cần tìm ra chiều rộng tối đa của cây nhị phân. Độ rộng của cây nhị phân là số node có mặt ở bất kỳ mức nào. Vì vậy, mức có số lượng node tối đa sẽ là chiều rộng tối đa của cây nhị phân. Để giải quyết vấn đề này, hãy duyệt qua cây theo cấp độ và đếm các node ở mỗi cấp độ.
Bài viết này được đăng tại [free tuts .net]
Ở cây nhị phân trên:
- Level 1: có 1 node, độ rộng là 1
- Level 2: có 2 node, độ rộng bằng 2
- Level 3: có 4 node, độ rộng bằng 4
- Level 4: có 1 node, độ rộng bằng 1
Vậy độ rộng lớn nhất của cây nhị phân trên đây là 4 ở level 3.
Tiếp theo chúng ta sẽ đi tìm hiểu sâu hơn về thuật toán để xử lí yêu cầu đề bài.
Thuật toán tìm kiếm độ rộng 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: findMaximumWidth() sẽ tìm ra được độ rộng lớn nhất của cây nhị phân trong Java
- Biến
maxWidthsẽ lưu trữ số lượng node tối đa - Hàng đợi được sử dụng để duyệt qua cây nhị phân theo từng cấp độ.
- 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 không, hãy thêm node gốc vào hàng đợi. Biến
nodesInLeveltheo dõi số lượng node ở mỗi cấp độ. - Nếu
nodesInLevel> 0, hãy xóa node khỏi đầu hàng đợi và thêm node con bên trái và bên phải của nó vào hàng đợi. Đối với lần lặp đầu tiên, node 1 sẽ bị xóa và các node con 2 và 3 của nó sẽ được thêm vào hàng đợi. Trong lần lặp thứ hai, node 2 sẽ bị xóa, node con 4 và 5 của nó sẽ được thêm vào hàng đợi, v.v. MaxWidthsẽ lưu trữmax(maxWidth, nodesInLevel). Vì vậy, tại bất kỳ thời điểm nào, nó sẽ đại diện cho số lượng node tối đa.- Điều này sẽ tiếp tục cho đến khi tất cả các cấp độ của cây được duyệt qua.
Chương trình tìm kiếm độ rộng 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
*/
import java.util.LinkedList;
import java.util.Queue;
public class BinaryTree {
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 BinaryTree(){
root = null;
}
public int findMaximumWidth() {
int maxWidth = 0;
int nodesInLevel = 0;
Queue<Node> queue = new LinkedList<Node>();
if(root == null) {
System.out.println("Tree is empty");
return 0;
}
else {
queue.add(root);
while(queue.size() != 0) {
nodesInLevel = queue.size();
maxWidth = Math.max(maxWidth, nodesInLevel);
while(nodesInLevel > 0) {
Node current = queue.remove();
if(current.left != null)
queue.add(current.left);
if(current.right != null)
queue.add(current.right);
nodesInLevel--;
}
}
}
return maxWidth;
}
public static void main(String[] args) {
BinaryTree bt = new BinaryTree();
bt.root = new Node(1);
bt.root.left = new Node(2);
bt.root.right = new Node(3);
bt.root.left.left = new Node(4);
bt.root.left.right = new Node(5);
bt.root.right.left = new Node(6);
bt.root.right.right = new Node(7);
bt.root.left.left.left = new Node(8);
System.out.println("Chương trình được đăng tại freetuts.net");
System.out.println("Giá trị độ rộng lớn nhất của cây nhị phân là: " + bt.findMaximumWidth());
}
}
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!!!
