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 Xác định đường biên(boundary traversal) của cây nhị phân trong Java
Cách xác định đường biên của binary tree 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.
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 đường biên của binary tree trong Java.
Cách xác định đường biên của binary tree 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.
Đầu tiên chúng ta tìm hiểu về lý thuyết liên quan đến bài toán này:
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ó max 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
Đường biên (Boundary ): là một đường của cây nhị phân, bắt đầu từ gốc đi qua node các node ở ngoài rìa bên trái, tiếp theo sẽ đi qua các node lá và cuối cùng là các node ngoài rìa bên phải.
Ví dụ:
Đường biên của cây nhị phân trên là: 20, 8, 4, 10, 14, 25, 22
Lưu ý: Nếu gốc mà không có cây con bên trái hoặc cây con bên phải thì chính nó là đường biên trái hoặc đường biên phải.
Chương trình xác định đường biên của binary tree trong 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
*/
class Node {
int data;
Node left, right;
Node(int item) {
data = item;
left = right = null;
}
}
class BinaryTree {
Node root;
void printLeaves(Node node) {
if (node == null) {
return;
}
printLeaves(node.left);
if (node.left == null && node.right == null) {
System.out.print(node.data + " ");
}
printLeaves(node.right);
}
void printBoundaryLeft(Node node) {
if (node == null) {
return;
}
if (node.left != null) {
System.out.print(node.data + " ");
printBoundaryLeft(node.left);
} else if (node.right != null) {
System.out.print(node.data + " ");
printBoundaryLeft(node.right);
}
}
void printBoundaryRight(Node node) {
if (node == null) {
return;
}
if (node.right != null) {
printBoundaryRight(node.right);
System.out.print(node.data + " ");
} else if (node.left != null) {
printBoundaryRight(node.left);
System.out.print(node.data + " ");
}
}
void printBoundary(Node node) {
if (node == null) {
return;
}
System.out.print(node.data + " ");
printBoundaryLeft(node.left);
printLeaves(node.left);
printLeaves(node.right);
printBoundaryRight(node.right);
}
public static void main(String args[]) {
BinaryTree tree = new BinaryTree();
tree.root = new Node(20);
tree.root.left = new Node(8);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(12);
tree.root.left.right.left = new Node(10);
tree.root.left.right.right = new Node(14);
tree.root.right = new Node(22);
tree.root.right.right = new Node(25);
System.out.println("Chương trình được đăng tại freetuts.net");
System.out.println("Đường biên của cây nhị phân đã cho là: ");
tree.printBoundary(tree.root);
System.out.println("");
}
}
Kết quả:
Như vậy chúng ta đã thực hiện xong chương trình xác định đường biên của binary tree trong Java. Chúc các bạn thực hiện thành công!!!
