Chương trình Java thực hiện duyệt cây Inorder (In-order Tree Traversal)

Trong bài viết này, chúng ta sẽ hiểu cách thực hiện duyệt cây Inorder (In-order Tree Traversal). Trong duyệt InOrder, mỗi node được xử lý giữa hai subtree. Nói đơn giản: duyệt left subtree, rồi node, rồi right subtree.

Minh họa dưới đây:

Giả sử đầu vào là:

Run the program

Đầu ra mong muốn:

The In-Order traversal of the tree_object is: 5->12->6->1->9->

Thuật toán

Bước 1 - BẮT ĐẦU 
Bước 2 - Class với spec dữ liệu đã định nghĩa trước 
Bước 3 - Tạo instance mới của class 
Bước 4 - Khởi tạo instance với giá trị liên quan 
Bước 5 - Gọi phương thức thực hiện inorder traversal 
Bước 6 - Hiển thị kết quả 
Bước 7 - DỪNG

Ví dụ 1

Dùng phương pháp đệ quy (recursive) cho in-order traversal.

class Node { 
    int item; 
    Node left_node, right_node; 
    public Node(int key) { 
        item = key; 
        left_node = right_node = null; 
    } 
} 

public class Tree { 
    Node root; 
    Tree() { 
        root = null; 
    } 
    
    void inOrder(Node node) { 
        if (node == null) 
            return; 
        inOrder(node.left_node); 
        System.out.print(node.item + "->"); 
        inOrder(node.right_node); 
    } 
    
    public static void main(String[] args) { 
        Tree tree_object = new Tree(); 
        System.out.println("A tree_object object is defined: "); 
        tree_object.root = new Node(1); 
        tree_object.root.left_node = new Node(12); 
        tree_object.root.right_node = new Node(9); 
        tree_object.root.left_node.left_node = new Node(5); 
        tree_object.root.left_node.right_node = new Node(6); 
        System.out.println("The In-Order traversal of the tree_object is: "); 
        tree_object.inOrder(tree_object.root); 
    } 
}

Kết quả

A tree_object object is defined: 
The In-Order traversal of the tree_object is: 5->12->6->1->9->

Ví dụ 2

Dùng phương pháp không đệ quy (non-recursive) với Stack cho in-order traversal.

import java.util.Stack; 

class Node { 
    int data; 
    Node left_node, right_node; 
    public Node(int item) { 
        data = item; 
        left_node = right_node = null; 
    } 
} 

class tree { 
    Node root; 
    
    void inorder() { 
        if (root == null) 
            return; 
        Stack temp_stack = new Stack(); 
        Node current_node = root; 
        while (current_node != null || temp_stack.size() > 0) { 
            while (current_node != null) { 
                temp_stack.push(current_node); 
                current_node = current_node.left_node; 
            } 
            current_node = temp_stack.pop(); 
            System.out.print(current_node.data + " "); 
            current_node = current_node.right_node; 
        } 
    } 
    
    public static void main(String args[]) { 
        tree tree = new tree(); 
        System.out.println("A tree_object object is defined: "); 
        tree.root = new Node(1); 
        tree.root.left_node = new Node(2); 
        tree.root.right_node = new Node(3); 
        tree.root.left_node.left_node = new Node(4); 
        tree.root.left_node.right_node = new Node(5); 
        System.out.println("The In-Order traversal of the tree_object is: "); 
        tree.inorder(); 
    } 
}

Kết quả

A tree_object object is defined: 
The In-Order traversal of the tree_object is: 4 2 5 1 3