[자료구조] Binary Search Tree (BST, 이진 탐색 트리)

Binary Search Tree (BST, 이진 탐색 트리)

• 모든 node의 key는 유일한 key를 가진다.
• 왼쪽 서브 트리 key들은 root의 key보다 작다.
• 오른쪽 서브 트리의 key들은 root의 key보다 크다.
• 왼쪽, 오른쪽 서브 트리 모두 binary search tree다.

이진 탐색 트리

코드

/* binary search tree */
import java.util.*;

class Node {
    int key;
    Node right;
    Node left;

    public Node() {}

    public Node(int key) {
        this.key = key;
        left = right = null;
    }
}

public class BinaryTree implements Iterable<Integer> {
    Node root;  
    private List<Integer> iterableTree = new ArrayList<>();  // List to store nodes in inorder

    public Node getRootNode() {
        return this.root;
    }

    public void add(int key) {
        root = addNode(root, key);
    }

    private Node addNode(Node root, int key) {
        if (root == null) {
            root = new Node(key);
            return root;
        }
        
        if (key < root.key) {
            root.left = addNode(root.left, key);
        }
        else if (key > root.key) {
            root.right = addNode(root.right, key);
        }
        return root;
    }

    public void inOrder(Node node) {
        if (node != null) {
            inOrder(node.left);
            System.out.println(node.key);
            inOrder(node.right);
        }
    }

    public void preOrder(Node node) {
        if (node != null) {
            System.out.println(node.key);
            preOrder(node.left);
            preOrder(node.right);
        }
    }

    public void postOrder(Node node) {
        if (node != null) {
            postOrder(node.left);
            postOrder(node.right);
            System.out.println(node.key);
        }
    }

    // Helper method to populate the iterableTree in inorder traversal
    private void setInorderIterable(Node node) {
        if (node != null) {
            setInorderIterable(node.left);   // Traverse left
            iterableTree.add(node.key);      // Add node to list
            setInorderIterable(node.right);  // Traverse right
        }
    }

    // Iterator method that provides an inorder traversal iterator
    @Override
    public Iterator<Integer> iterator() {
        if (this.root == null) {
            throw new IllegalArgumentException("Tree is empty");
        }
        this.iterableTree.clear();              // Clear the list
        this.setInorderIterable(this.root);     // Fill the list with inorder traversal
        return this.iterableTree.iterator();    // Return an iterator over the list
    }
}

class Test {
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();

        tree.add(50);
        tree.add(30);
        tree.add(20);
        tree.add(40);
        tree.add(70);
        tree.add(60);
        tree.add(80);

        System.out.println("In-order traversal:");
        tree.inOrder(tree.getRootNode());
        System.out.println("");

        Iterator<Integer> iterator = tree.iterator();
         
        System.out.println("Using iterator:");
        for (int value : tree) {
            System.out.println(value);
        }
    }
}

 

실행 결과

In-order traversal:
20
30
40
50
60
70
80

Using iterator:
20
30
40
50
60
70
80

 

 

2024.09.02 - [Java] - [Java] 14. Collections Framework

[Java] 14. Collections Framework

 

---

 

 

출처: https://github.com/gikpreet/class-programming_with_java/tree/master

GitHub - gikpreet/class-programming_with_java