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 Xác định các lá của binary tree sử dụng preoder trong Java
Cách xác định lá của binary tree sử dụng pre-oder bằng ngôn ngữ 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 lá của binary tree sử dụng pre-oder.
Cách xác định lá của binary tree sử dụng pre-oder bằng ngôn ngữ 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: Binary tree, pre-oder.
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
Pre-oder: là một cách duyệt binary tree trong Java. Hiểu đơn giản thì với cách duyệt này ta sẽ đi qua node cha trước sau đến node con trái rồi mới đến node con phải.
Ví dụ:
Sau khi dùng pre-oder ta được: 6, 3, 1, 10, 9, 12
Ý tưởng để giải quyết bài toán này là sử dụng hai biến min và max và lấy i (chỉ mục trong mảng đầu vào), chỉ mục cho mảng sắp xếp trước đã cho và tạo đệ quy nút gốc và kiểm tra tương ứng xem bên trái và bên phải có tồn tại hay không. Phương thức này trả về biến boolean và nếu cả trái và phải đều sai thì điều đó đơn giản có nghĩa là trái và phải không có giá trị do đó nó phải là một nút lá, vì vậy hãy in nó ngay tại đó và trả về giá trị đúng như gốc tại chỉ mục đó đã tồn tại.
Chương trình xác định lá của binary tree sử dụng pre-oder bằng ngôn ngữ 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 LeavesFoundByPreoder
{
static int i = 0;
static boolean isLeaf(int pre[], int n,
int min, int max)
{
if (i >= n)
{
return false;
}
if (pre[i] > min && pre[i] < max)
{
i++;
boolean left = isLeaf(pre, n, min, pre[i - 1]);
boolean right = isLeaf(pre, n, pre[i - 1], max);
if (!left && !right)
{
System.out.print(pre[i - 1] + " ");
}
return true;
}
return false;
}
static void printLeaves(int preorder[], int n)
{
isLeaf(preorder, n, Integer.MIN_VALUE,
Integer.MAX_VALUE);
}
// Driver code
public static void main(String[] args)
{
int preorder[] = {6, 3, 1, 10, 9, 12};
int n = preorder.length;
System.out.println("Chương trình này được đăng tại freetuts.net");
printLeaves(preorder, n);
}
}
Kết quả:
Như vậy chúng ta đã thực hiện xong chương trình xác định lá của binary tree sử dụng pre-oder bằng ngôn ngữ Java. Chúc các bạn thực hiện thành công!!!
