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 khoảng cách lớn nhất giữa các node của cây nhị phân trong Java
Tìm khoảng cách lớn nhất giữa các node 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 khoảng cách lớn nhất giữa các node 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 cần tìm ra các nút có khoảng cách lớn nhất trong cây nhị phân. Theo cách tiếp cận của chúng tôi, tất cả khoảng cách giữa tất cả các nút của cây sẽ được giữ ở khoảng cách thay đổi. Khoảng cách với giá trị lớn nhất sẽ được giữ bằng cách sử dụng biến MaxDistance. Ban đầu, MaxDistance được khởi tạo với giá trị là khoảng cách. Nếu bất kỳ giá trị nào được tìm thấy lớn hơn MaxDistance, hãy ghi đè lên giá trị của MaxDistance.
Bài viết này được đăng tại [free tuts .net]
Lặp lại quá trình này cho đến khi chúng ta tìm được khoảng cách lớn nhất có thể giữa hai nút của cây. Thuật toán của quá trình được đưa ra dưới đây.
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: Khởi tạo MaxDistance chứa 2 thuộc tính: root và treeArray
Bước 3: nodesAtMaxDistance() sẽ lưu trữ giá trị khoảng cách lớn nhất giữa 2 node trong cây nhị phân.
- Nó sẽ tính toán khoảng cách giữa tất cả các nút có trong cây nhị phân và lưu trữ nó trong khoảng cách có thể thay đổi.
- MaxDistance theo dõi khoảng cách tối đa có thể giữa các nút. Nếu maxDistance nhỏ hơn khoảng cách, thì giá trị của khoảng cách sẽ được lưu trữ trong maxDistance. Xóa mảng để loại bỏ các giá trị được lưu trữ trước đó. Các nút ở khoảng cách tối đa sẽ được lưu trữ trong một mảng arr.
- Nếu có nhiều hơn một cặp nút ở maxDistance thì hãy lưu trữ chúng trong mảng arr.
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
*/
import java.util.ArrayList;
public class MaxDistance {
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;
int[] treeArray;
int index = 0;
public MaxDistance() {
root = null;
}
public int calculateSize(Node node) {
int size = 0;
if (node == null) {
return 0;
} else {
size = calculateSize(node.left) + calculateSize(node.right) + 1;
return size;
}
}
public void convertBTtoArray(Node node) {
if (root == null) {
System.out.println("Tree is empty");
return;
} else {
if (node.left != null) {
convertBTtoArray(node.left);
}
treeArray[index] = node.data;
index++;
if (node.right != null) {
convertBTtoArray(node.right);
}
}
}
public int getDistance(Node temp, int n1) {
if (temp != null) {
int x = 0;
if ((temp.data == n1) || (x = getDistance(temp.left, n1)) > 0
|| (x = getDistance(temp.right, n1)) > 0) {
return x + 1;
}
return 0;
}
return 0;
}
public Node lowestCommonAncestor(Node temp, int node1, int node2) {
if (temp != null) {
if (temp.data == node1 || temp.data == node2) {
return temp;
}
Node left = lowestCommonAncestor(temp.left, node1, node2);
Node right = lowestCommonAncestor(temp.right, node1, node2);
if (left != null && right != null) {
return temp;
}
if (left != null) {
return left;
}
if (right != null) {
return right;
}
}
return null;
}
public int findDistance(int node1, int node2) {
int d1 = getDistance(root, node1) - 1;
int d2 = getDistance(root, node2) - 1;
Node ancestor = lowestCommonAncestor(root, node1, node2);
int d3 = getDistance(root, ancestor.data) - 1;
return (d1 + d2) - 2 * d3;
}
public void nodesAtMaxDistance(Node node) {
int maxDistance = 0, distance = 0;
ArrayList<Integer> arr = new ArrayList<>();
int treeSize = calculateSize(node);
treeArray = new int[treeSize];
convertBTtoArray(node);
for (int i = 0; i < treeArray.length; i++) {
for (int j = i; j < treeArray.length; j++) {
distance = findDistance(treeArray[i], treeArray[j]);
if (distance > maxDistance) {
maxDistance = distance;
arr.clear();
arr.add(treeArray[i]);
arr.add(treeArray[j]);
}
else if (distance == maxDistance) {
arr.add(treeArray[i]);
arr.add(treeArray[j]);
}
}
}
System.out.println("Chương trình được đăng tại freetuts.net");
System.out.println("Phần tử có khoảng cách lớn nhất là : ");
for (int i = 0; i < arr.size(); i = i + 2) {
System.out.println("( " + arr.get(i) + "," + arr.get(i + 1) + " )");
}
}
public static void main(String[] args) {
MaxDistance bt = new MaxDistance();
//Add nodes to the binary tree
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.right.right.right = new Node(8);
bt.root.right.right.right.left = new Node(9);
//Finds out all the pair of nodes which are at maximum distance
bt.nodesAtMaxDistance(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!!!
