Java Program Inorder Tree Traversal (การเดินทาง In-order)

Tree Traversal คืออะไร?

การเยี่ยมชม (Visit) ทุก Node ใน Tree ตามลำดับที่กำหนด มี 3 แบบหลักสำหรับ Binary Tree:

Inorder Traversal (LNR)

สำหรับ Binary Search Tree (BST) Inorder จะให้ค่าที่เรียงลำดับจากน้อยไปมาก (Sorted Ascending)

Recursive Approach

void inOrder(Node node) {
    if (node == null) return;
    
    inOrder(node.left);      // 1. Left
    System.out.print(node.data + " "); // 2. Node
    inOrder(node.right);     // 3. Right
}

Iterative Approach (ใช้ Stack)

void inOrderIterative(Node root) {
    if (root == null) return;
    
    Stack stack = new Stack<>();
    Node current = root;
    
    while (current != null || !stack.isEmpty()) {
        // ไปซ้ายสุด
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        
        // Visit
        current = stack.pop();
        System.out.print(current.data + " ");
        
        // ไปขวา
        current = current.right;
    }
}

ตัวอย่างที่ 1: Recursive Method

class Node {
    int item;
    Node left, right;
    
    public Node(int key) {
        item = key;
        left = right = null;
    }
}

public class Tree {
    Node root;
    
    Tree() { root = null; }
    
    void inOrder(Node node) {
        if (node == null) return;
        inOrder(node.left);
        System.out.print(node.item + "->");
        inOrder(node.right);
    }
    
    public static void main(String[] args) {
        Tree tree = new Tree();
        System.out.println("A tree object is defined: ");
        
        // สร้าง Tree:
        //       1
        //      / \
        //     12  9
        //    / \
        //   5   6
        
        tree.root = new Node(1);
        tree.root.left = new Node(12);
        tree.root.right = new Node(9);
        tree.root.left.left = new Node(5);
        tree.root.left.right = new Node(6);
        
        System.out.println("The In-Order traversal of the tree is: ");
        tree.inOrder(tree.root);
    }
}

ผลลัพธ์

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

ตัวอย่างที่ 2: Iterative (Non-Recursive) Method

import java.util.Stack;

class Node {
    int data;
    Node left, right;
    public Node(int item) {
        data = item;
        left = right = null;
    }
}

class Tree {
    Node root;
    
    void inorder() {
        if (root == null) return;
        
        Stack stack = new Stack<>();
        Node current = root;
        
        while (current != null || !stack.isEmpty()) {
            // ไปซ้ายสุด
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            
            // Visit Node
            current = stack.pop();
            System.out.print(current.data + " ");
            
            // ไปขวา
            current = current.right;
        }
    }
    
    public static void main(String args[]) {
        Tree tree = new Tree();
        System.out.println("A tree object is defined: ");
        
        //       1
        //      / \
        //     2   3
        //    / \
        //   4   5
        
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
        
        System.out.println("The In-Order traversal of the tree is: ");
        tree.inorder();
    }
}

ผลลัพธ์

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

Morris Traversal (O(1) Space - ไม่ใช้ Stack/Recursion)

Threaded Binary Tree Technique - แปลง Tree ชั่วคราวเพื่อ Traverse โดยไม่ใช้ Extra Space

void inorderMorris(Node root) {
    Node current = root;
    
    while (current != null) {
        if (current.left == null) {
            System.out.print(current.data + " ");
            current = current.right;
        } else {
            // หา Inorder Predecessor
            Node pre = current.left;
            while (pre.right != null && pre.right != current) {
                pre = pre.right;
            }
            
            if (pre.right == null) {
                // สร้าง Thread
                pre.right = current;
                current = current.left;
            } else {
                // ลบ Thread
                pre.right = null;
                System.out.print(current.data + " ");
                current = current.right;
            }
        }
    }
}

การสร้าง BST และ Inorder ให้ Sorted Output

public class BST {
    Node root;
    
    // Insert into BST
    public void insert(int value) {
        root = insertRec(root, value);
    }
    
    private Node insertRec(Node root, int value) {
        if (root == null) return new Node(value);
        if (value < root.data) root.left = insertRec(root.left, value);
        else if (value > root.data) root.right = insertRec(root.right, value);
        return root;
    }
    
    // Inorder = Sorted Output
    public void inorder() { inOrderRec(root); }
    
    private void inOrderRec(Node root) {
        if (root != null) {
            inOrderRec(root.left);
            System.out.print(root.data + " ");
            inOrderRec(root.right);
        }
    }
    
    public static void main(String[] args) {
        BST bst = new BST();
        int[] values = {50, 30, 70, 20, 40, 60, 80};
        for (int v : values) bst.insert(v);
        
        System.out.print("Inorder (Sorted): ");
        bst.inorder(); // 20 30 40 50 60 70 80
    }
}

Complexity Analysis

สรุป

• Inorder = Left → Node → Right (LNR)
• BST Inorder = Sorted Ascending Order
• Recursive: เรียบง่าย แต่อาจ Stack Overflow (Deep Tree)
• Iterative: ใช้ Stack ควบคุม Memory ได้
• Morris: O(1) Space แต่ซับซ้อน แปลง Tree ชั่วคราว
• 應用: BST Sorting, Expression Evaluation, File System Traversal