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 Triển khai cây nhị phân từ danh sách liên kết trong Java
Cách triển khai cây nhị phân từ danh sách liên kết 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ề Binary Tree.
Dưới đây freetuts sẽ giúp bạn tìm hiểu về cách thức để implement một Binary Tree từ một LinkedList trong Java.
Cách implement Binary Tree từ một LinkedList 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.
Để hoàn thành nhiệm vụ implement Binary Tree từ một LinkedList trong Java, chcần tạo cây nhị phân bằng cách chèn các nút và hiển thị các nút theo thứ tự. Một cây nhị phân điển hình có thể được biểu diễn như sau:
Bài viết này được đăng tại [free tuts .net]
Trong cây nhị phân, mỗi nút có thể có nhiều nhất hai nút con. Mỗi nút có thể có 0, 1 hoặc 2 nút con. Mỗi nút trong cây nhị phân chứa các thông tin sau:
- Data: giá trị được lưu trữ trong nút.
- Left: con trỏ tới con bên trái.
- Right: con trỏ tới con bên phải.
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ó 3 thuộc tính bao gồm: data, right, left.
Bước 2: insert() sẽ thêm node mới vào cây nhị phân.
- method này sẽ kiểm tra xem root có rỗng hay không, nếu rỗng thì method sẽ tự động thêm node mới làm root.
- Nếu kiểm tra mà không rỗng thì method sẽ thêm root vào queue.
- Gán node hiện tại làm current node và bắt đầu xét duyệt cây nhị phân.
- Xét duyệt current node xem có con trái và con phải không? Nếu có thì sẽ thêm cả 2 vào queue.
- Nếu không có node con bên trái thì thêm current node làm node con bên trái.
- Làm tương tự với node con bên phải.
Bước 3: ainOder() sẽ thêm một node mới vào danh sách:
- Tạo một node mới.
- Đầu tiên, nó kiểm tra xem head có bằng null hay không nếu bằng thì danh sách trống.
- Nếu danh sách trống, cả head và tail sẽ trỏ đến node mới được thêm vào.
- Nếu danh sách không trống, thì node mới được thêm vào sẽ trở thành tail mới và tail trước đó sẽ trỏ đến node mới làm node tiếp theo của nó. Tail mới sẽ trỏ vào head.
Bước 4: printOder() sẽ in ra toàn bộ cây bắt đầu từ con bên trái, đến gốc rồi đến con bên phải.
Để 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 implement Binary Tree từ một LinkedListtrong 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 {
class Node {
int data;
Node left, right;
private Node next;
public Node(int item) {
data = item;
left = right = null;
}
}
Node root;
public BinaryTree() {
root = null;
}
void insert(int key) {
Node newNode = new Node(key);
if (root == null) {
root = newNode;
return;
}
Queue<Node> queue = new LinkedList<Node>();
queue.add(root);
while (!queue.isEmpty()) {
Node currentNode = queue.remove();
if (currentNode.left == null) {
currentNode.left = newNode;
return;
} else {
queue.add(currentNode.left);
}
if (currentNode.right == null) {
currentNode.right = newNode;
return;
} else {
queue.add(currentNode.right);
}
}
}
void inOrder(Node node) {
if (node == null)
return;
inOrder(node.left);
System.out.print(node.data + " ");
inOrder(node.right);
}
void addToList(Node node) {
Node newNode = new Node(node.data);
if (head == null) {
head = newNode;
tail = newNode;
tail.next = head;
} else {
tail.next = newNode;
tail = newNode;
tail.next = head;
}
}
Node head, tail;
void printOrder(Node node) {
head = tail = null;
inOrder(node);
Node currentNode = head;
do {
System.out.print(currentNode.data + " ");
currentNode = currentNode.next;
} while (currentNode != head);
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
tree.insert(1);
tree.insert(2);
tree.insert(3);
tree.insert(4);
tree.insert(5);
System.out.println("Chương trình được đăng bởi freetuts.net");
System.out.println("Cây nhị phân được triển khai từ danh sách liên kết là:");
tree.printOrder(tree.root);
}
}
Kết quả:
Như vậy chúng ta đã thực hiện xong chương trình implement Binary Tree từ một LinkedList trong Java. Chúc các bạn thực hiện thành công!!!
