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) 
Thuật toán kiếm tra số nguyên tố 
Lệnh cin và cout trong C++ 
Random trong Python: Tạo số random ngẫu nhiên 
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 chuyển đổi từ cây nhị phân thành cây nhị phân tìm kiếm trong Java
Cách chuyển đổi cây nhị phân thành cây nhị phân tìm kiếm trong 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ề Tree trong Java.
Dưới đây chúng ta sẽ thực hiện chương trình chuyển đổi cây nhị phân thành cây nhị phân tìm kiếm trong Java.
Cách chuyển đổi cây nhị phân thành cây nhị phân tìm kiếm trong Java
Trong chương trình này, chúng ta cần chuyển đổi cây nhị phân thành cây nhị phân tìm kiếm tương ứng. Cây nhị phân được gọi là cây nhị phân mà mỗi nút có nhiều nhất hai nút con. Trong khi đó, cây nhị phân tìm kiếm là trường hợp đặc biệt của cây nhị phân trong đó tất cả các nút ở bên trái của nút gốc phải nhỏ hơn nút gốc và các nút ở bên phải phải lớn hơn nút gốc.
Thuật toán chuyển đổi cây nhị phân thành cây nhị phân tìm kiếm trong Java
Dưới đây là một số bước cơ bản của thuật toán:
Bước 1: Khởi tạo Node là một node trong binary tree có 3 thuộc tính: data, left & right.
Bước 2: Khi một node được tạo, dữ liệu sẽ được chuyển đến thuộc tính dữ liệu của node, left và right sẽ được đặt là null.
Bước 3: Class ConvertBTtoBST() chứa 2 thuộc tính root và treeArray.
Bước 4: convertBTBST() sẽ chuyển đổi cây nhị phân thành cây tìm kiếm nhị phân tương ứng.
Để các bạn dễ hình dung hơn thì bây giờ chúng ta sẽ tham khảo đoạn code sau.
Chương trình chuyển đổi cây nhị phân thành cây nhị phân tìm kiếm trong Java
/**
* Học lập trình free tại freetuts.net
*
* @author Dell
*/
import java.util.Arrays;
public class ConvertBTtoBST {
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 ConvertBTtoBST() {
root = null;
}
public Node convertBTBST(Node node) {
int treeSize = calculateSize(node);
treeArray = new int[treeSize];
convertBTtoArray(node);
Arrays.sort(treeArray);
Node d = createBST(0, treeArray.length - 1);
return d;
}
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 Node createBST(int start, int end) {
if (start > end) {
return null;
}
int mid = (start + end) / 2;
Node node = new Node(treeArray[mid]);
node.left = createBST(start, mid - 1);
node.right = createBST(mid + 1, end);
return node;
}
public void inorderTraversal(Node node) {
if (root == null) {
System.out.println("Tree is empty");
return;
} else {
if (node.left != null) {
inorderTraversal(node.left);
}
System.out.print(node.data + " ");
if (node.right != null) {
inorderTraversal(node.right);
}
}
}
public static void main(String[] args) {
ConvertBTtoBST bt = new ConvertBTtoBST();
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);
System.out.println("Cây nhị phân được nhập vào: ");
bt.inorderTraversal(bt.root);
Node bst = bt.convertBTBST(bt.root);
System.out.println("\nCây nhị phân tìm kiếm đã được chuyển đổi: ");
bt.inorderTraversal(bst);
}
}
Kết quả:
Như vậy chúng ta đã hoàn thành chương trình chuyển đổi cây nhị phân thành cây nhị phân tìm kiếm trong Java. Chúc các bạn thực hiện thành công.
