C# 비선형 자료구조 - 트리(Tree)

• 트리(Tree)란?

자료 간의 관계가 계층 구조일 때 사용하는 비선형 자료구조이다.

- 트리는 노드(node)로 이루어진 자료구조

- 트리는 하나의 루트 노드를 갖는다.

- 루트 노드는 -개 이사의 자식 노드를 갖고 있다.

- 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다.

 

• 트리(Tree)와 관련된 용어

부모 노드 & 자식 노드 = 서브 트리

같은 레벨 간 노드들 = 형제 노드

 

• 트리(Tree)의 특징

- 그래프의 한 종류이다. '최소 연결 트리'라고도 불린다.

- 트리는 계층 모델이다.

- 트리는 DAG(Directed Acycle Graphs, 방향성이 있는 비순환 그래프)의 한 종류이다.

- 노드가 N개인 트리는 항상 N-1개의 간선(edge)을 가진다.

- 루트에서 어떤 노드로 가는 경로는 유일하다.

- 한 개의 루트 노드만이 존재하며 모든 자식 노드는 한 개의 부모 노드만을 가진다.

- 순회는 Pre-order, In-order 아니면 Post-order로 이루어진다.

- 트리는 이진 트리, 이진 탐색 트리, 균형 트리, 이진 힙 등이 있다.

 

• 이진 트리(Binary tree)

컴퓨터에서 사용되는 데이터 구조의 하나로, 루트가 있는 트리 구조에서 어떤 노드의 자식의 수가 최대 2개를 넘지 않는 트리를 말한다.

 

- 이진 트리(Binary tree)의 순회

이진 트리의 순회(traversal)란 이진 트리의 모든 노드를 특정한 순서대로 한 번씩 방문하는 것이다.

 

1) 전위순회

루트 노드 1이 왼쪽 서브 트리 2 방문 후 왼쪽 서브 트리인 4 방문, 그 다음으로 5 방문 후 왼쪽 6 방문, 마지막 3 방문

 

2) 중위순회

 

3) 후위 순회

1 - 2 - 4 - 2 - 5 - 6 - 5 - 2 - 3 - 1

 

- 이진 트리(Binary tree) DFS, BFS

이진 트리의 순회는 전위, 중위 아니며 후위 순회로 이루어지고 3가지 모두 DFS(깊이우선탐색)과 BFS(너비우선탐색) 안에 있다. 너비 우선 트리는 무한한 경로가 존재, 모든 경로를 동시에 탐색한다.

 

1) 깊이 우선 탐색 : 막다른 길이 나올 때 까지 탐색

2) 너비 우선 탐색 : 갈림길에 연결되어 있는 모든 길 탐색 후 연결된 길 탐색

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace BinaryTree
{
    public class BinaryTreeNode<Tdata>
    {
        public Tdata tData { get; set; }
        public BinaryTreeNode<Tdata> btnLeft { get; set; }
        public BinaryTreeNode<Tdata> btnRight { get; set; }
        public BinaryTreeNode(Tdata tdata)
        {
            this.tData = tdata;
        }
    }
    public class BinaryTree<T>
    {
        private BinaryTreeNode<T> root = null;
        private Comparer<T> comparer = Comparer<T>.Default;
        public void Insert(T val)
        {
            BinaryTreeNode<T> node = root;
            if(node == null)
            {
                root = new BinaryTreeNode<T>(val);
                return;
            }
            while(node != null)
            {
                int result = comparer.Compare(node.tData, val);
                if(result == 0)
                {
                    //throw new InvalidDataException("Duplicate value");
                    return;
                }
                else if(result > 0)
                {
                    if(node.btnLeft == null)
                    {
                        node.btnLeft = new BinaryTreeNode<T>(val);
                        return;
                    }
                    node = node.btnLeft;
                }
                else
                {
                    if(node.btnRight == null)
                    {
                        node.btnRight = new BinaryTreeNode<T>(val);
                        return;
                    }
                    node = node.btnRight;
                }
            }
        }
        public void PreOrderTraversal()
        {
            PreOrderRecursive(root);
        }
        private void PreOrderRecursive(BinaryTreeNode<T> node)
        {
            if (node == null) return;
            Console.Write(node.tData + "->");
            PreOrderRecursive(node.btnLeft);
            PreOrderRecursive(node.btnRight);
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            BinaryTree<int> bt = new BinaryTree<int>();

            bt.Insert(4);
            bt.Insert(2);
            bt.Insert(3);
            bt.Insert(6);
            bt.Insert(1);
            bt.Insert(7);
            bt.Insert(5);

            bt.PreOrderTraversal();
        }
    }
}