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) 
ComboBox - ListBox trong lập trình C# winforms 
Random trong Python: Tạo số random ngẫu nhiên 
Lệnh cin và cout trong C++ 
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ạo double linked list từ cây bậc ba (ternary tree) trong Java
Cách để chuyển đổi ternary tree thành double linked list 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ề double linked list.
Dưới đây chúng ta sẽ thực hiện chương trình chuyển đổi ternary tree thành double linked list trong Java.
Cách chuyển đổi ternary tree thành double linked list trong Java
Ternary tree là một cấu trúc dữ liệu phân cấp trong đó mỗi nút có thể có tối đa ba nút con.
Điều này có thể được thực hiện bằng cách duyệt qua cây bậc ba theo kiểu pre-order, nghĩa là: root -> left child -> mid child -> right child. Đầu tiên, đi qua root và thêm nó vào danh sách. Sau đó, lần lượt thêm các cây con bên trái, giữa và bên phải của nó.
Bài viết này được đăng tại [free tuts .net]
Ví dụ:
Ternary Tree:
Double Linked List converted:
Thuật toán chuyển đổi ternary tree thành double linked list 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 ternary tree có 4 thuộc tính: data, left, middle, right.
Bước 2: Root là gốc của ternary tree. Head và tail thuộc tính của double linked list.
Bước 3: Class TernaryTreeToDLL() sẽ chuyển đổi ternary tree thành double linked list
Bước 4: Hiển thị các node trong list
Để 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 ternary tree thành double linked list trong Java
/**
* Học lập trình free tại freetuts.net
* @author Dell
*/
public class TernaryTreeToDLL {
public static class Node {
int data;
Node left;
Node middle;
Node right;
public Node(int data) {
this.data = data;
}
}
public Node root;
Node head, tail = null;
public void convertTernarytoDLL(Node node) {
if (node == null) {
return;
}
Node left = node.left;
Node middle = node.middle;
Node right = node.right;
if (head == null) {
head = tail = node;
node.middle = null;
head.left = null;
tail.right = null;
} else {
tail.right = node;
node.left = tail;
node.middle = null;
tail = node;
tail.right = null;
}
convertTernarytoDLL(left);
convertTernarytoDLL(middle);
convertTernarytoDLL(right);
}
public void display() {
Node current = head;
if (head == null) {
System.out.println("Danh sách này trống");
return;
}
System.out.println("Các phần tử trong double linked list: ");
while (current != null) {
System.out.print(current.data + " ");
current = current.right;
}
System.out.println();
}
public static void main(String[] args) {
TernaryTreeToDLL tree = new TernaryTreeToDLL();
tree.root = new Node(5);
tree.root.left = new Node(10);
tree.root.middle = new Node(12);
tree.root.right = new Node(15);
tree.root.left.left = new Node(20);
tree.root.left.middle = new Node(40);
tree.root.left.right = new Node(50);
tree.root.middle.left = new Node(24);
tree.root.middle.middle = new Node(36);
tree.root.middle.right = new Node(48);
tree.root.right.left = new Node(30);
tree.root.right.middle = new Node(45);
tree.root.right.right = new Node(60);
tree.convertTernarytoDLL(tree.root);
System.out.println("Chương trình này được đăng tại freetuts.net\n");
tree.display();
}
}
Kết quả:
Như vậy chúng ta đã hoàn thành chương trình chuyển đổi ternary tree thành double linked list trong Java. Chúc các bạn thực hiện thành công.
