CĂN BẢN
CHUỖI
VÒNG LẶP
NUMBER
INPUT / OUTPUT
COLLECTIONS
Ví dụ danh sách liên kết đơn Java Đếm số node trong Singly Linked List trong Java Đảo ngược thứ tự của Singly Linked List trong Java Xóa node đầu tiên của Singly Linked List trong Java Xóa node ở giữa của Singly Linked List trong Java Xóa node cuối cùng của Singly Linked List trong Java Thêm node vào vị trí đầu tiên của Singly Linked List trong Java Thêm node vào vị trí cuối cùng của Singly Linked List trong Java Thêm node vào vị trí giữa của Singly Linked List trong Java Kiểm tra danh sách liên kết đơn palindrome trong Java Tìm giá trị lớn nhất của Singly Linked List trong Java Tìm giá trị nhỏ nhất của Singly Linked List trong Java Xóa phần tử trùng lặp khỏi Singly Linked List trong Java Tìm kiếm phần tử của Singly Linked List trong Java Tạo một Circular Linked List trong Java Tạo một Circular Linked List Java và đảo ngược nó Xóa node đầu tiên của Circular Linked List trong Java Xóa node cuối cùng của Circular Linked List trong Java Xóa node ở giữa của Circular Linked List trong Java Thêm node vào vị trí đầu tiên của Circular Linked List trong Java Thêm node vào vị trí cuối cùng của Circular Linked List trong Java Thêm node vào vị trí giữa của Circular Linked List trong Java Tìm giá trị lớn nhất trong Circular Linked List Java Tìm giá trị nhỏ nhất trong Circular Linked List Tìm kiếm phần tử của Circular Linked List trong Java Xóa phần tử trùng lặp khỏi Circular Linked List trong Java Sắp xếp các phần tử của Circular Linked List trong Java Chuyển đổi Binary Tree thành Double Linked List trong Java Tạo double linked list từ cây bậc ba (ternary tree) trong Java Cách chuyển đổi từ cây nhị phân thành cây nhị phân tìm kiếm trong Java Xác định các lá có cùng cấp trong Tree của Java Kiểm tra hai cây giống nhau trong Java Tìm chiều rộng tối đa của cây nhị phân trong Java Tìm phần tử lớn nhất của cây nhị phân trong Java Tìm khoảng cách lớn nhất giữa các node của cây nhị phân trong Java Tìm phần tử nhỏ nhất của cây nhị phân trong Java Tính tổng giá trị của các node của cây nhị phân trong Java Tính tổng số cây nhị phân tìm kiếm có thể được tạo ra bởi N nodes trong Java Triển khai cây nhị phân từ danh sách liên kết trong Java Tìm kiếm node của cây nhị phân tìm kiếm trong Java Cách tạo ra Mirror Tree từ Binary Tree bằng ngôn ngữ Java Xác định các lá của binary tree sử dụng preoder trong Java Xác định đường biên(boundary traversal) của cây nhị phân trong Java Xóa node của cây nhị phân tìm kiếm trong Java Duyệt cây nhị phân bằng phương pháp inOder trong Java
CALCULATE
SẮP XẾP - TÌM KIẾM
KHÁC
NÂNG CAO
CÁC CHỦ ĐỀ
BÀI MỚI NHẤT
MỚI CẬP NHẬT

Cách chuyển đổi từ cây nhị phân thành cây nhị phân tìm kiếm trong Java

Cách chuyển đổi cây nhị phân thành 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ề Tree trong Java.

Dưới đây chúng ta sẽ thực hiện chương trình chuyển đổi cây nhị phân thành cây nhị phân tìm kiếm trong Java.

Cách chuyển đổi cây nhị phân thành cây nhị phân tìm kiếm trong Java

Trong chương trình này, chúng ta cần chuyển đổi cây nhị phân thành cây nhị phân tìm kiếm tương ứng. Cây nhị phân được gọi là cây nhị phân mà mỗi nút có nhiều nhất hai nút con. Trong khi đó, cây nhị phân tìm kiếm là trường hợp đặc biệt của cây nhị phân trong đó tất cả các nút ở bên trái của nút gốc phải nhỏ hơn nút gốc và các nút ở bên phải phải lớn hơn nút gốc.

java program to convert binary tree to binary search tree png

test php

banquyen png
Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức.

Thuật toán chuyển đổi cây nhị phân thành cây nhị phân tìm kiếm 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: Khi một node được tạo, dữ liệu sẽ được chuyển đến thuộc tính dữ liệu của node, left và right sẽ được đặt là null.

Bước 3: Class ConvertBTtoBST() chứa 2 thuộc tính root và treeArray.

Bước 4: convertBTBST() sẽ chuyển đổi cây nhị phân thành cây tìm kiếm nhị phân tương ứng.

Để 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 cây nhị phân thành cây nhị phân tìm kiếm trong Java

/**
 * Học lập trình free tại freetuts.net
 *
 * @author Dell
 */
import java.util.Arrays;

public class ConvertBTtoBST {

    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;

    int[] treeArray;
    int index = 0;

    public ConvertBTtoBST() {
        root = null;
    }

    public Node convertBTBST(Node node) {

        int treeSize = calculateSize(node);
        treeArray = new int[treeSize];

        convertBTtoArray(node);

        Arrays.sort(treeArray);

        Node d = createBST(0, treeArray.length - 1);
        return d;
    }

    public int calculateSize(Node node) {
        int size = 0;
        if (node == null) {
            return 0;
        } else {
            size = calculateSize(node.left) + calculateSize(node.right) + 1;
            return size;
        }
    }

    public void convertBTtoArray(Node node) {

        if (root == null) {
            System.out.println("Tree is empty");
            return;
        } else {
            if (node.left != null) {
                convertBTtoArray(node.left);
            }

            treeArray[index] = node.data;
            index++;
            if (node.right != null) {
                convertBTtoArray(node.right);
            }
        }
    }

    public Node createBST(int start, int end) {

        if (start > end) {
            return null;
        }

        int mid = (start + end) / 2;
        Node node = new Node(treeArray[mid]);

        node.left = createBST(start, mid - 1);

        node.right = createBST(mid + 1, end);

        return node;
    }

    public void inorderTraversal(Node node) {

        if (root == null) {
            System.out.println("Tree is empty");
            return;
        } else {

            if (node.left != null) {
                inorderTraversal(node.left);
            }
            System.out.print(node.data + " ");
            if (node.right != null) {
                inorderTraversal(node.right);
            }

        }
    }

    public static void main(String[] args) {

        ConvertBTtoBST bt = new ConvertBTtoBST();

        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);

        System.out.println("Cây nhị phân được nhập vào: ");
        bt.inorderTraversal(bt.root);

        Node bst = bt.convertBTBST(bt.root);

        System.out.println("\nCây nhị phân tìm kiếm đã được chuyển đổi: ");
        bt.inorderTraversal(bst);
    }
}

Kết quả:

result convert BT to BST jpg

Như vậy chúng ta đã hoàn thành chương trình chuyển đổi cây nhị phân thành cây nhị phân tìm kiếm trong Java. Chúc các bạn thực hiện thành công.

Cùng chuyên mục:

Sử dụng JUnit để tạo unit test trong Spring Boot

Sử dụng JUnit để tạo unit test trong Spring Boot

Cách triển khai Spring Boot trên Tomcat Server

Cách triển khai Spring Boot trên Tomcat Server

Cách test RESTful API trong Spring Boot

Cách test RESTful API trong Spring Boot

Cách dùng Spring Security trong Spring Boot để xác thực và phân quyền

Cách dùng Spring Security trong Spring Boot để xác thực và phân quyền

Duyệt cây nhị phân bằng phương pháp inOder trong Java

Duyệt cây nhị phân bằng phương pháp inOder trong Java

Xóa node của cây nhị phân tìm kiếm trong Java

Xóa node của cây nhị phân tìm kiếm trong Java

Bảo mật Spring Boot RESTful Service sử dụng Basic Authentication trong Java

Bảo mật Spring Boot RESTful Service sử dụng Basic Authentication trong Java

Xác định đường biên(boundary traversal) của cây nhị phân trong Java

Xác định đường biên(boundary traversal) của cây nhị phân trong Java

Xác định các lá của binary tree sử dụng preoder trong Java

Xác định các lá của binary tree sử dụng preoder trong Java

Tìm kiếm node của cây nhị phân tìm kiếm trong Java

Tìm kiếm node của cây nhị phân tìm kiếm trong Java

Cách chuyển HTTP sang HTTPS trong Spring Boot

Cách chuyển HTTP sang HTTPS trong Spring Boot

Triển khai cây nhị phân từ danh sách liên kết trong Java

Triển khai cây nhị phân từ danh sách liên kết trong Java

Cách tạo ra Mirror Tree từ Binary Tree bằng ngôn ngữ Java

Cách tạo ra Mirror Tree từ Binary Tree bằng ngôn ngữ Java

Sử dụng @bean trong ứng dụng Spring Boot

Sử dụng @bean trong ứng dụng Spring Boot

Spring Data JPA trong Spring Boot là gì? Spring Data JPA có gì hay?

Spring Data JPA trong Spring Boot là gì? Spring Data JPA có gì hay?

Giới thiệu về Spring Boot Actuator trong ứng dụng Spring Boot

Giới thiệu về Spring Boot Actuator trong ứng dụng Spring Boot

Tính tổng số cây nhị phân tìm kiếm có thể được tạo ra bởi N nodes trong Java

Tính tổng số cây nhị phân tìm kiếm có thể được tạo ra bởi N nodes trong Java

Tìm phần tử nhỏ nhất của cây nhị phân trong Java

Tìm phần tử nhỏ nhất của cây nhị phân trong Java

Sử dụng nhiều ViewResolver trong Spring Boot Java

Sử dụng nhiều ViewResolver trong Spring Boot Java

Tìm khoảng cách lớn nhất giữa các node của cây nhị phân trong Java

Tìm khoảng cách lớn nhất giữa các node của cây nhị phân trong Java

Top