[C#] 이진 트리 공부

- 각 노드에는 값이 있고, 이 값은 왼쪽 자식의 값보다 크고, 오른쪽 자식의 값보다 작습니다.

- 이진 탐색 트리는 효율적인 탐색과 삽입을 제공하며, 평균적으로 O(log n)의 시간 복잡도를 가집니다.

using System;

public class Node
{
    public int Data;
    public Node Left;
    public Node Right;

    public Node(int data)
    {
        Data = data;
        Left = null;
        Right = null;
    }
}

public class BinarySearchTree
{
    public Node Root;

    public BinarySearchTree()
    {
        Root = null;
    }

    // 1. 노드 삽입 메서드
    public void Insert(int data)
    {
        Root = InsertRec(Root, data);
    }

    private Node InsertRec(Node root, int data)
    {
        // 트리가 비어 있으면 새 노드를 반환
        if (root == null)
        {
            root = new Node(data);
            return root;
        }

        // 값이 현재 노드보다 작으면 왼쪽 서브트리에 삽입
        if (data < root.Data)
            root.Left = InsertRec(root.Left, data);
        // 값이 현재 노드보다 크면 오른쪽 서브트리에 삽입
        else if (data > root.Data)
            root.Right = InsertRec(root.Right, data);

        return root;
    }

    // 2. 값 탐색 메서드
    public bool Search(int data)
    {
        return SearchRec(Root, data);
    }

    private bool SearchRec(Node root, int data)
    {
        // 트리가 비어 있거나 원하는 값을 찾은 경우
        if (root == null)
            return false;

        if (root.Data == data)
            return true;

        // 값을 왼쪽 또는 오른쪽 서브트리에서 탐색
        if (data < root.Data)
            return SearchRec(root.Left, data);
        else
            return SearchRec(root.Right, data);
    }

    // 3. 트리 출력 (중위 순회)
    public void InOrderTraversal()
    {
        InOrderRec(Root);
        Console.WriteLine();
    }

    private void InOrderRec(Node root)
    {
        if (root != null)
        {
            InOrderRec(root.Left);  // 왼쪽 서브트리
            Console.Write(root.Data + " ");  // 현재 노드
            InOrderRec(root.Right);  // 오른쪽 서브트리
        }
    }
}

class Program
{
    static void Main(string[] args)
    {
        BinarySearchTree bst = new BinarySearchTree();

        // 노드 삽입
        bst.Insert(50);
        bst.Insert(30);
        bst.Insert(20);
        bst.Insert(40);
        bst.Insert(70);
        bst.Insert(60);
        bst.Insert(80);

        // 트리 출력 (중위 순회)
        Console.WriteLine("In-order traversal of the tree:");
        bst.InOrderTraversal();  // 출력: 20 30 40 50 60 70 80

        // 값 탐색
        int searchValue = 60;
        if (bst.Search(searchValue))
            Console.WriteLine($"{searchValue} found in the tree.");
        else
            Console.WriteLine($"{searchValue} not found in the tree.");
    }
}