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ìm kiếm node của cây nhị phân tìm kiếm trong Java
Cách tìm kiếm node của cây nhị phân tìm kiếm 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 Search Tree.
Dưới đây freetuts sẽ giúp bạn tìm hiểu về cách tìm kiếm node của cây nhị phân tìm kiếm trong Java.
Cách tìm kiếm node của cây nhị phân tìm kiếm 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 hãy ôn lại lý thuyết về Tree, Binary Tree:
Bài viết này được đăng tại [free tuts .net]
Tree là cấu trúc dữ liệu phi tuyến tính lưu trữ dữ liệu theo thứ bậc. Tree là một tập hợp các phần tử được gọi là các nút. Các nút được kết nối thông qua các cạnh và chứa dữ liệu. Nút đầu tiên của cây được gọi là Root. Mỗi nút có thể có hoặc không có nút con. Nút không có nút con nào được gọi là lá.
Binary Tree là một loại cấu trúc dữ liệu cây khác, trong đó mỗi nút có thể có tối đa hai nút con. Tức là mỗi nút trong cây nhị phân sẽ có dữ liệu, con trái và con phải.
Để hoàn thành nhiệm vụ, chúng ta sẽ tìm kiếm một giá trị cụ thể trong cây nhị phân. Nếu có thì in ra thông báo "Có phần tử trong cây nhị phân", ngược lại in ra thông báo "Không có phần tử trong cây nhị phân". Tóm lại, đầu tiên chúng ta sẽ so sánh dữ liệu của root với dữ liệu của nút cần tìm. Nếu tìm thấy kết quả phù hợp, hãy đặt flag thành true. Mặt khác, tìm kiếm nút trong cây con bên trái và sau đó trong cây 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: searchNode() sẽ tìm kiếm node cụ thể trong 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ì return "Cây nhị phân tìm kiếm rỗng!"
-
Nếu cây không trống, nó sẽ so sánh dữ liệu tạm thời với giá trị. Nếu chúng bằng nhau, nó sẽ đặt flag thành true và trả về.
Duyệt qua cây con bên trái bằng cách gọi hàm
searchNode()theo cách đệ quy và kiểm tra xem giá trị có xuất hiện trong cây con bên trái hay không.Duyệt qua cây con bên phải bằng cách gọi đệ quy
searchNode()và kiểm tra xem giá trị có xuất hiện trong cây con bên phải hay không.
Chương trình tìm kiếm một node cụ thể của cây nhị phân tìm kiếm 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
*/
public class SearchBinaryTree {
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;
public static boolean flag = false;
public SearchBinaryTree() {
root = null;
}
public void searchNode(Node temp, int value) {
flag = false;
if (root == null) {
System.out.println("Tree is empty");
} else {
if (temp.data == value) {
flag = true;
return;
}
if (flag == false && temp.left != null) {
searchNode(temp.left, value);
}
if (flag == false && temp.right != null) {
searchNode(temp.right, value);
}
}
}
public static void main(String[] args) {
int key = 5, key2 = -1;
SearchBinaryTree bt = new SearchBinaryTree();
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.right.left = new Node(5);
bt.root.right.right = new Node(6);
System.out.println("Chương trình được đăng tại freetuts.net");
//search key
bt.searchNode(bt.root, key);
if (flag) {
System.out.println("Phần tử " + key + " xuất hiện ở cây nhị phân tìm kiếm");
} else {
System.out.println("Phần tử " + key + "này không xuất hiện ở cây nhị phân tìm kiếm");
}
//search key2
bt.searchNode(bt.root, key2);
if (flag) {
System.out.println("Phần tử " + key2 + " xuất hiện ở cây nhị phân tìm kiếm");
} else {
System.out.println("Phần tử " + key2+ " không xuất hiện ở cây nhị phân tìm kiếm");
}
}
}
Kết quả:
Như vậy chúng ta đã thực hiện xong chương trình tìm kiếm một node cụ thể trong cây nhị phân tìm kiếm bằng ngôn ngữ Java. Chúc các bạn thực hiện thành công!!!
