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 Chuyển đổi Binary Tree thành Double Linked List trong Java
Cách chuyển đổi Binary 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 Binary Tree thành Double Linked List trong Java.
Cách chuyển đổi Binary Tree thành Double Linked List trong Java
Binary tree là một cấu trúc dữ liệu cây trong đó mỗi node có nhiều nhất hai node con.
Điều này có thể đạt được bằng cách duyệt cây theo thứ tự, node trái -> root -> node phải. Duyệt cây con bên trái và chuyển nó thành danh sách liên kết kép bằng cách thêm các node vào cuối danh sách. Theo cách này, node ngoài cùng bên trái sẽ trở thành đầu danh sách. Sau đó, chuyển cây con bên phải thành danh sách liên kết kép.
Bài viết này được đăng tại [free tuts .net]
Ví dụ:
Thuật toán chuyển đổi Binary 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 binary tree có 3 thuộc tính: data, left & right
Bước 2: Root là gốc của binary tree. Head và tail thuộc tính của double linked list.
Bước 3: Class BinaryTreeToDLL() sẽ chuyển đổi binary 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 Binary Tree thành Double Linked List trong Java
/**
* Học lập trình free tại freetuts.net
* @author Dell
*/
public class BinaryTreeToDLL {
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;
Node head, tail = null;
public void convertbtToDLL(Node node) {
if (node == null) {
return;
}
convertbtToDLL(node.left);
if (head == null) {
head = tail = node;
} else {
tail.right = node;
node.left = tail;
tail = node;
}
convertbtToDLL(node.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) {
BinaryTreeToDLL bt = new BinaryTreeToDLL();
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);
bt.convertbtToDLL(bt.root);
System.out.println("Chương trình này được đăng tại freetuts.net\n");
bt.display();
}
}
Kết quả:
Như vậy chúng ta đã hoàn thành chương trình chuyển đổi binary tree thành double linked list trong Java. Chúc các bạn thực hiện thành công.
