C# Tree 구현

Description

이번 자료구조는 Tree 이다.
그중 이진 탐색 트리, Binary Search Tree를 구현하고자 한다.

• Tree구조는 Root.Node로 부터 0개 이상의 Node를 가진다.
• Node가 0 ~ 2개면 이진트리 , 0 ~ 3개면 삼진트리 등으로 불리어진다.
• 노드의 왼쪽 자식은 부모의 값보다 작은 값을 가져야 하며 노드의 오른쪽 자식은 부모의 값보다 큰 값을 가져야 함

예를 들면 이런식으로 이루어 진다.

---

Cord

Class

public class TreeNode<T>
{
    public int Data { get; set; }
    
    // 왼쪽 자식 노드
    public TreeNode<T> Left { get; set; }

    // 오른쪽 자식 노드
    public TreeNode<T> Right { get; set; }

    // 생성자로 data 초기화
    public TreeNode(int _data)
    {
        Data = _data;
    }
}

public class Tree <T>
{
    // 최상위 Node
    public TreeNode<T> Root { get; set; }
}

Tree 특성상 Root가 되는 최상위 Node를 가진다 그리고 Root로 부터
이진트리로써 Left와 Right 두개의 자식 Node를 가진다.

---

Add()

public void Add(int _data)
{
    TreeNode<T> root = Root;

    while (true)
    {
        // 같은 숫자가 있을경우 예외처리
        if (root.Data == _data)
        {
            Debug.LogError("Error");
            return;
        }

        // _root.Data와 _Data 비교
        if (root.Data > _data)  // _root 보다 작으면 left에 대입
        {
            if (root.Left == null)
            {
                root.Left = new TreeNode<T>(_data);
                break;
            }
            else
            {
                root = root.Left;
            }
        }
        else   // 크면 right에 대입
        {
            if (root.Right == null)
            {
                root.Right = new TreeNode<T>(_data);
                break;
            }
            else
            {
                root = root.Right;
            }
        }
    }
}

우선 Root의 Left 부터 보겠다.
그러면 ‘10’ - ‘left : 7’ - ‘left : 3’, ‘right : 5’ 가 되고

Root의 Right 쪽이다
‘10’ - ‘right : 15’ - ‘right : 40’ - ‘left : 35’ 가 되었다.

Tree 구조는 이것으로 끝이다.
굉장히 간단하고 종류도 많긴하다.