C# 자료구조 (트리2)

이번엔 트리의 표현법중의 하나인 왼쪽 자식 오른쪽 형제 표현법을 설명하겠다.

 

왼쪽 자식 오른쪽 형제 표현법 

 

왼쪽 자식 오른쪽 형제 표현법은 크기가 고정된 2인 트리에서 왼쪽은 자식 노드를 가리키고 오른쪽엔 형제 노드를 가리키도록 표현한 방식이다.

 

그림으로 어떻게 표현하는지 보겠다.

왼쪽 자식 오른쪽 형제 표현법 출처 C#으로 이해하는 자료구조

 

 

그림에서도 보았듯이 크기가 고정된 2의 크기로 왼쪽은 자식 오른쪽은 형제를 가리키고 있으며 추가될때마다

크기는 2로 고정 되있어서 메모리 공간 낭비를 줄일수 있는 장점이 있다.

 

부모 노드가 자식 노드들을 다 찾기 위해서는 자식 노드의 형제 노드들을 다 찾고 접근해야 알수있다.

 

이제 왼쪽은 자식 오른쪽은 형제 표현법을 구현한 코드를 보여주고 기능들을 설명하겠다.

 

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

namespace LCRS_Tree
{
    class LCRSNode<T>
    {
        public T Data { get; set; }
        public LCRSNode<T> LeftChild { get; set; }
        public LCRSNode<T> RightSibling { get; set; }

        public LCRSNode(T data)
        {
            Data = data;
        }
    }

    class LCRSTree<T>
    {
        public LCRSNode<T> Root { get; set; }

        public LCRSTree(T rootData)
        {
            Root = new LCRSNode<T>(rootData);
        }

        // 자식 노드 추가

        public LCRSNode<T> AddChild(LCRSNode<T> parent, T data)
        {
            // 만약 부모 노드가 없다면 null 반환
            if (parent == null)
                return null;

            //자식 노드의 데이터 추가
            LCRSNode<T> child = new LCRSNode<T>(data);

            //부모의 자식노드가 없다면 child노드 추가
            if (parent.LeftChild == null)
            {
                parent.LeftChild = child;
            }
            //만약 자식노드가 있다면
            else
            {
                //다른 데이터 node에 원래 있던 자식 노드 할당
                var node = parent.LeftChild;

                //형제 노드가 없을때까지 형제노드로 이동
                while (node.RightSibling != null)
                {
                    node = node.RightSibling;
                }

                //형제 노드 마지막 까지 가서 추가
                node.RightSibling = child;
            }

            //마지막 리턴
            return child;
        }

        // 형제노드 추가

        public LCRSNode<T> AddSibling(LCRSNode<T> node, T data)
        {
            // 형제 노드가 null이면 리턴
            if (node == null)
                return null;

            // 똑같이 형제노드 오른쪽 끝까지 진입
            while (node.RightSibling != null)
            {
                node = node.RightSibling;
            }

            // 새로 형제 노드에 할당한 데이터 객체 생성
            var sibling = new LCRSNode<T>(data);

            // 오른쪽 끝에 있던 형제노드 오른쪽에 data 추가
            node.RightSibling = sibling;

            //sibling 데이터 반환
            return sibling;
        }

        // 레벨 순으로 트리노드 출력
        public void PrintLevelOrder()
        {
            //데이터를 아래쪽부터 빼내기 위해 큐 생성
            var q = new Queue<LCRSNode<T>>();

            //맨 처음 Root부터 데이터를 넣어준다.
            q.Enqueue(Root);

            //큐 카운트 없어질떄까지 노드 출력
            while (q.Count > 0)
            {
                //첫번째 Root 부모 자식 데이터를 가져옴
                var node = q.Dequeue();

                //Root 데이터가 null이 아닐떄
                while (node != null)
                {
                    //데이터 출력
                    Console.WriteLine($"{node.Data}");

                    //현재 노드에 있는 자식노드가 null이 아닐떄
                    if (node.LeftChild != null)
                    {
                        //다시 큐에 자식노드를 넣는다.
                        q.Enqueue(node.LeftChild);
                    }

                    // 현재노드에 있던 형제노드로 할당
                    node = node.RightSibling;
                }
            }
        }

        // 들여쓰기 방식으로 트리 출력
        public void PrintIndentTree()
        {
            //현재 부모 노드 첫번 째 순서 1을 넣는다
            PrintIndent(Root, 1);
        }

        private void PrintIndent(LCRSNode<T> node,int indent)
        {
            //현재 노드가 널일시 리턴
            if (node == null)
                return;

            // 현재 노드 PadLeft로 여백 맞추고 출력
            string pad = " ".PadLeft(indent);
            Console.WriteLine($"{pad}{node.Data}");

            // 왼쪽 자식
            // (자식이므로 Indent 증가)
            // 재귀함수를 이용해서 자식 노드를 호출
            PrintIndent(node.LeftChild, indent + 1);

            // 오른쪽 형제
            // (형제이므로 동일 Indent 사용)
            // 재귀함수를 이용해서 형제 노드를 호출
            PrintIndent(node.RightSibling, indent);

        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            LCRSTree<string> tree = new LCRSTree<string>("A");
            var A = tree.Root;
            var B = tree.AddChild(A, "B");
            tree.AddChild(A, "C");
            var D = tree.AddSibling(B, "D");
            tree.AddChild(B, "E");
            tree.AddChild(B, "F");
            tree.AddChild(D, "G");

            //출력
            tree.PrintIndentTree();

            tree.PrintLevelOrder();
        }
    }
}

 

 

Node 클래스에선 자기의 데이터와 왼쪽 자식 노드를 가리키는 .LeftChild 오른쪽 형제 노드를 가리키는 RightSibling 프로퍼티를 만들고

 

이제 트리를 구현하는 LCRSTree 클래스의 기능들을 설명하겠다.

 

처음엔 최상위 부모 노드인 Root 노드가 있고 생성자로 Root노드의 데이터를 추가한다.

 

AddChild()

 

AddChild 메서드는 자식노드를 연결 시키는 메서드이다. 당연히 부모 노드가 없으면 null로 리턴하고 자식노드 child 노드를 인자값을 받은 데이터를 넣어서 객체를 생성 만약에 부모 노드에 자식 노드가 없다면 바로 추가를 하고 있다면 있는 자식 노드의 형제 노드가 없을때까지 가서 추가를 한다.

 

AddSibling()

 

AddSibling 메서드는 형제노드를 연결 시키는 메서드이고 AddChild 메서와 비슷한 기능과 코드를 가지고 있다고 생각할수 있다.

 

PrintLevelOrder()

 

이 기능은 최상위 부모부터 시작해서 레벨순으로 노드들을 출력하는 메서드이다.

첫번째 최상위 부모 노드의 데이터를 넣고 출력하기위해 이런 기능에 좋은 Queue를 객체생성

 

처음에 최상위 부모노드 Root를 넣고 Queue 카운트가 0이 아니면 아래쪽에있는 노드를 할당해서 그 노드의 데이터를 출력하고 자식노드가 null이아니면 일단 Queue에 넣고 형제노드가 null아니면 형제 노드들을 출력시킨다.

 

이런 비슷한 형식으로 BFS 알고리즘으로도 활용할수있다.

 

 

PrintIndentTree()

PrintIndent()

 

PrintIndentTree 기능은 PrintIndent 기능에 처음 최상위 부모노드를 접근하기 위한 메서드이고

중요한건 PrintIndent 메서드다.

 

PrintIndent 메서드는 계층적으로 나누기 위한 트리 구조를 출력하는 방식으로

일단 node가 널이면 리턴 널이 아닐땐 공백을 주는 PadLeft함수를 호출해 출력하고

 

그 노드의 자식으로 연결한 노드부터 재귀함수를 이용해 접근을해서 자식 노드들이 널일때가지 출력

그다음에 형제노드를 가서 똑같이 재귀함수를 이용해서 출력한다.

 

이런 비슷한 형식으로 DFS 알고리즘으로도 활용할수있다.

 

 

이제 위에가 PrintIndent기능으로 구현한 계층적으로 트리 구조를 호출하는 방식이고

 

아래가 PrintLevelOrder기능인 레벨적으로 순차적으로 호출한 방식이다.