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 Cách tạo ra Mirror Tree từ Binary Tree bằng ngôn ngữ Java
Cách xác định cây đã cho là mirror tree(cây gương) bằng ngôn ngữ Java. Đây là bài tập căn bản giúp các bạn nắm vững kiến thức về binary tree.
Binary tree là cấu trúc dữ liệu phổ biến và có nhiều ứng dụng trong các lĩnh vực khác nhau. Binary Tree cũng rất quan trọng khi phỏng vấn các công ty công nghệ hàng đầu. Việc thành thạo binary tree có thể giúp chúng ta giải quyết rất nhiều vấn đề. Trong bài viết này, chúng ta sẽ xem xét một vấn đề như vậy. Dưới đây freetuts sẽ giúp bạn tìm hiểu về cách xác định cây đã cho là mirror tree bằng ngôn ngữ Java.
Cách tạo ra mirror tree từ binary tree bằng ngôn ngữ 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.
Đầu tiên chúng ta tìm hiểu về lý thuyết liên quan đến bài toán này: Binary tree, mirror tree.
Bài viết này được đăng tại [free tuts .net]
Binary tree: là một cấu trúc dữ liệu phân cấp trong đó mỗi nút có tối đa hai nút con: nút con bên trái và nút con bên phải. Nút trên cùng của cây được gọi là root . Mỗi nút chứa ba thành phần:
- Con trỏ tới cây con bên trái
- Con trỏ tới cây con bên phải
- Data
Mirror tree : Là một binary tree, được tạo ra bằng hình ảnh phản chiếu của một binary tree khác.
Ví dụ:
Để làm được bài toán này, chúng ta có thể là xây dựng một cây mới sẽ là hình ảnh phản chiếu của cây đã cho. Chúng ta có thể viết một thuật toán đệ quy lấy gốc của binary tree và mirror tree làm đối số.
Các bước của thuật toán trên như sau:
Bước 1: Đặt gốc của mirror tree bằng gốc của cây ban đầu.
Bước 2: Gọi đệ quy hàm để tạo con trái và con phải của mirror tree.
- Đặt nút con bên trái của nút hiện tại trong mirror tree thành nút con bên phải của nút hiện tại trong cây ban đầu.
- Đặt con bên phải của nút hiện tại trong mirror tree thành con bên trái của nút hiện tại trong cây ban đầu.
- Nếu nút hiện tại trong cây ban đầu là NULL, chỉ cần trả về.
Chương trình tạo ra mirror tree từ binary tree bằng ngôn ngữ 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 MirrorTree {
public static void main(String args[]) {
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
System.out.println("Binary tree input :");
tree.inOrder();
System.out.println("");
System.out.println("Chương trình được đăng tại freetuts.net");
tree.mirror();
System.out.println("Mirror Tree : ");
tree.inOrder();
}
}
class BinaryTree {
Node root;
void mirror() {
root = mirror(root);
}
Node mirror(Node node) {
if (node == null) {
return node;
}
Node left = mirror(node.left);
Node right = mirror(node.right);
node.left = right;
node.right = left;
return node;
}
void inOrder() {
inOrder(root);
}
void inOrder(Node node) {
if (node == null) {
return;
}
inOrder(node.left);
System.out.print(node.data + " ");
inOrder(node.right);
}
}
class Node {
int data;
Node left, right;
public Node(int item) {
data = item;
left = right = null;
}
}
Kết quả:
Như vậy chúng ta đã thực hiện xong chương trình tạo ra mirror tree từ binary tree bằng ngôn ngữ Java. Chúc các bạn thực hiện thành công!!!
