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 Kiểm tra hai cây giống nhau trong Java
Cách kiểm tra xem hai cây giống nhau trong Java. Đây là bài tập giúp các bạn hiểu thêm về Tree trong Java.
Dưới đây chúng ta sẽ thực hiện chương trình kiểm tra hai cây nhị phân có giống nhau hay không bằng ngôn ngữ Java.
Kiểm tra hai cây nhị phân giống nhau trong Java
Trong chương trình này, chúng ta cần kiểm tra xem hai cây có giống nhau hay không. Để hai cây giống hệt nhau, chúng phải thỏa mãn hai điều kiện:
- Cấu trúc của cả hai cây phải giống nhau.
- Các node của cây này giống node của cây kia.
Bài viết này được đăng tại [free tuts .net]
Sơ đồ trên chứa ba cây là A, B và C. Cây A và B giống nhau vì chúng giống nhau về cấu trúc và giá trị của tất cả các node đều giống nhau. Tuy nhiên, cây A và C giống nhau về cấu trúc nhưng không giống nhau vì các node khác nhau ở cả hai cây.
Các bước của thuật toán trên như sau:
Bước 1: Tạo một lớp Node có ba thuộc tính: data, left & right.
Bước 2: Tạo một lớp khác có thuộc tính là root.
Bước 3: areIdenticalTrees() kiểm tra 2 cây có giống nhau hay không.
- Nếu các root của cả hai cây là null thì chúng giống hệt nhau.
- Nếu root của chỉ một cây là null thì các cây không giống nhau, trả về false.
- Nếu root của không có node nào trong cây là null thì kiểm tra xem dữ liệu của cả hai node có bằng nhau hay không và sau đó kiểm tra đệ quy cây con bên trái và cây con bên phải của một cây có giống với cây kia hay không.
Để các bạn dễ hình dung hơn thì chúng ta bắt đầu triển khai code nhé.
Chương trình kiểm tra hai cây nhị phân giống nhau 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 free tại freetuts.net
*
* @author Dell
*/
public class IdenticalTrees {
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 IdenticalTrees(){
root = null;
}
public static boolean areIdenticalTrees(Node root1, Node root2) {
if(root1 == null && root2 == null)
return true;
if(root1 == null && root2 == null)
return true;
if(root1 != null && root2 != null) {
return ((root1.data == root2.data) &&
(areIdenticalTrees(root1.left, root2.left)) &&
(areIdenticalTrees(root1.right, root2.right)));
}
return false;
}
public static void main(String[] args) {
IdenticalTrees bt1 = new IdenticalTrees();
bt1.root = new Node(1);
bt1.root.left = new Node(2);
bt1.root.right = new Node(3);
bt1.root.left.left = new Node(4);
bt1.root.right.left = new Node(5);
bt1.root.right.right = new Node(6);
IdenticalTrees bt2 = new IdenticalTrees();
bt2.root = new Node(1);
bt2.root.left = new Node(2);
bt2.root.right = new Node(3);
bt2.root.left.left = new Node(4);
bt2.root.right.left = new Node(5);
bt2.root.right.right = new Node(6);
System.out.println("Chương trình này được đăng tại freetuts");
if(areIdenticalTrees(bt1.root, bt2.root))
System.out.println("Hai cây nhị phân này đều giống nhau");
else
System.out.println("Hai cây nhị phân này khác nhau");
}
}
Kết quả:
Như vậy chúng ta đã thực hiện xong chương trình kiểm tra hai cây nhị phân giống nhau trong Java. Chúc các bạn thực hiện thành công!!!
