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óa node của cây nhị phân tìm kiếm trong Java
Cách xóa node vào 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óa node vào binary tree trong Java.
Cách xóa node vào 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 node có max hai node con: node con bên trái và node con bên phải. node trên cùng của cây được gọi là root . Mỗi node 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
Để xóa một node vào binary tree chúng ta cần xét đến 3 khả năng có thể xảy ra:
- Node cần xóa là lá: đơn giản là việc loại bỏ nó khỏi binary tree.
- Node cần xóa chỉ có một node con: Sao chép node con vào node và xóa node.
- node cần xóa có 2 con: Tìm node kế tiếp theo thứ tự của node. Sao chép nội dung của người kế vị thứ tự vào node và xóa người kế vị thứ tự.
Bây giờ chúng ta sẽ tìm hiểu thêm về thuật toán của bài toán này để hiểu hơn nhé.
Thuật toán của bài toán xóa node vào binary tree trong Java
Thuật toán xử lí bài toán này có một số bước cơ bản sau:
Bước 1: Nếu root là NULL, thì trả về root (Trường hợp cơ sở)
Bước 2: Nếu key nhỏ hơn giá trị của root thì set root->left = deleteNode(root->left, key)
Bước 3: Nếu key lớn hơn giá trị của root thì set root->right = deleteNode(root->right, key)
Bước 4: Kiểm tra khác
- Nếu root là node lá thì trả về null
- khác nếu nó chỉ có con bên trái, thì trả lại con bên trái
- khác nếu nó chỉ có đúng con, sau đó trả về đúng con
- khác, đặt giá trị của root là của người kế vị theo thứ tự của nó và lặp lại để xóa node có giá trị của người kế vị theo thứ tự
Bước 5: Return
Chương trình xóa node vào 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
*/
import java.io.*;
class BinarySearchTree {
class Node {
int key;
Node left, right;
public Node(int item) {
key = item;
left = right = null;
}
}
Node root;
BinarySearchTree() {
root = null;
}
void deleteKey(int key) {
root = deleteRec(root, key);
}
Node deleteRec(Node root, int key) {
if (root == null) {
return root;
}
if (key < root.key) {
root.left = deleteRec(root.left, key);
} else if (key > root.key) {
root.right = deleteRec(root.right, key);
} else {
if (root.left == null) {
return root.right;
} else if (root.right == null) {
return root.left;
}
root.key = minValue(root.right);
root.right = deleteRec(root.right, root.key);
}
return root;
}
int minValue(Node root) {
int minv = root.key;
while (root.left != null) {
minv = root.left.key;
root = root.left;
}
return minv;
}
void insert(int key) {
root = insertRec(root, key);
}
Node insertRec(Node root, int key) {
if (root == null) {
root = new Node(key);
return root;
}
if (key < root.key) {
root.left = insertRec(root.left, key);
} else if (key > root.key) {
root.right = insertRec(root.right, key);
}
return root;
}
void inorder() {
inorderRec(root);
}
void inorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
System.out.print(root.key + " ");
inorderRec(root.right);
}
}
public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
/* Tạo ra một cây nhị phân
50
/ \
30 70
/ \ / \
20 40 60 80 */
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
System.out.println(
"Cây nhị phân được khởi tạo");
tree.inorder();
System.out.println("");
System.out.println("Xóa node 20");
tree.deleteKey(20);
System.out.println(
"Cây nhị phân sau khi được xử lí: ");
tree.inorder();
System.out.println("");
System.out.println("Xóa node 30");
tree.deleteKey(30);
System.out.println(
"Cây nhị phân sau khi được xử lí:");
tree.inorder();
System.out.println("");
System.out.println("Xóa node 50");
tree.deleteKey(50);
System.out.println(
"Cây nhị phân sau khi được xử lí:");
tree.inorder();
System.out.println("");
}
}
Kết quả:
Như vậy chúng ta đã thực hiện xong chương trình xóa node vào binary tree trong Java. Chúc các bạn thực hiện thành công!!!
