Microsoft MVP성태의 닷넷 이야기
글쓴 사람
정성태 (techsharer at outlook.com)
홈페이지
첨부 파일
(연관된 글이 1개 있습니다.)

디버깅 용도로 이진 트리의 내용을 출력하는 방법

Binary Tree같은 자료 구조 테스트하다보면 가끔 내용이 어떤 식으로 구성되어 있는지 궁금할 때가 있습니다. 검색해 보니 다음의 코드가 있군요. ^^

How to Pretty Print a Binary Tree
; http://articles.leetcode.com/how-to-pretty-print-binary-tree/

소스 코드가 C/C++ 언어로 되어 있는데 ^^ C#으로 변환해 봤습니다. (덧글에 보면 Python, JavaScript 버전도 있습니다.)

char _fillCh = ' ';

void printBranches(int branchLen, int nodeSpaceLen, int startLen, int nodesInThisLevel, Deque<Node> nodesQueue, StringBuilder _out)
{
    IEnumerator<Node> iter = nodesQueue.GetEnumerator();
    iter.MoveNext();
    for (int i = 0; i < nodesInThisLevel / 2; i++)
    {
        string format = string.Format("{{0:{0}:{1}}}", (i == 0) ? startLen - 1 : nodeSpaceLen - 2, _fillCh);
        string txt = string.Format(new PaddedStringFormatInfo(), format, "");
        _out.Append(txt);
        _out.Append(iter.Current != null ? "/" : " ");
        iter.MoveNext();

        format = string.Format("{{0:{0}:{1}}}", 2 * branchLen + 2, _fillCh);
        txt = string.Format(new PaddedStringFormatInfo(), format, "");
        _out.Append(txt);
        _out.Append(iter.Current != null ? "\\" : " ");
        iter.MoveNext();
    }

    _out.AppendLine();
}

void printNodes(int branchLen, int nodeSpaceLen, int startLen, int nodesInThisLevel, Deque<Node> nodesQueue, StringBuilder _out)
{
    IEnumerator<Node> iter = nodesQueue.GetEnumerator();
    iter.MoveNext();
    for (int i = 0; i < nodesInThisLevel; i++, iter.MoveNext())
    {
        string format = string.Format("{{0:{0}:{1}}}", (i == 0) ? startLen : nodeSpaceLen, _fillCh);
        string txt = string.Format(new PaddedStringFormatInfo(), format, "");
        _out.Append(txt);
        _fillCh = (iter.Current != null && iter.Current.Left != null) ? '_' : ' ';

        format = string.Format("{{0:{0}:{1}}}", branchLen + 2, _fillCh);
        txt = string.Format(new PaddedStringFormatInfo(), format, (iter.Current != null) ? iter.Current.Data.ToString() : "");
        _out.Append(txt);

        _fillCh = (iter.Current != null && iter.Current.Right != null) ? '_' : ' ';
        format = string.Format("{{0:{0}:{1}}}", branchLen, _fillCh);
        txt = string.Format(new PaddedStringFormatInfo(), format, "");
        _out.Append(txt);

        _fillCh = ' ';
    }

    _out.AppendLine();
}

void printLeaves(int indentSpace, int level, int nodesInThisLevel, Deque<Node> nodesQueue, StringBuilder _out)
{
    IEnumerator<Node> iter = nodesQueue.GetEnumerator();
    iter.MoveNext();
    for (int i = 0; i < nodesInThisLevel; i++, iter.MoveNext())
    {
        string format = string.Format("{{0:{0}:{1}}}", (i == 0) ? indentSpace + 2 : 2 * level + 2, _fillCh);
        string txt = string.Format(new PaddedStringFormatInfo(), format, (iter.Current != null) ? iter.Current.Data.ToString() : "");
        _out.Append(txt);
    }

    _out.AppendLine();
}

int maxHeight(Node p)
{
    if (p == null) return 0;
    int leftHeight = maxHeight(p.Left);
    int rightHeight = maxHeight(p.Right);
    return (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;
}

public void printPretty(Node root, int level, int indentSpace, StringBuilder _out)
{
    int h = maxHeight(root);
    int nodesInThisLevel = 1;

    int branchLen = 2 * ((int)Math.Pow(2.0, h) - 1) - (3 - level) * (int)Math.Pow(2.0, h - 1);  // eq of the length of branch for each node of each level
    int nodeSpaceLen = 2 + (level + 1) * (int)Math.Pow(2.0, h);  // distance between left neighbor node's right arm and right neighbor node's left arm
    int startLen = branchLen + (3 - level) + indentSpace;  // starting space to the first node to print of each level (for the left most node of each level only)

    Deque<Node> nodesQueue = new Deque<Node>();
    nodesQueue.PushBack(root);

    for (int r = 1; r < h; r++)
    {
        printBranches(branchLen, nodeSpaceLen, startLen, nodesInThisLevel, nodesQueue, _out);
        branchLen = branchLen / 2 - 1;
        nodeSpaceLen = nodeSpaceLen / 2 + 1;
        startLen = branchLen + (3 - level) + indentSpace;
        printNodes(branchLen, nodeSpaceLen, startLen, nodesInThisLevel, nodesQueue, _out);

        for (int i = 0; i < nodesInThisLevel; i++)
        {
            Node currNode = nodesQueue.PeekFront();
            nodesQueue.PopFront();
            if (currNode != null)
            {
                nodesQueue.PushBack(currNode.Left);
                nodesQueue.PushBack(currNode.Right);
            }
            else {
                nodesQueue.PushBack(null);
                nodesQueue.PushBack(null);
            }
        }
        nodesInThisLevel *= 2;
    }
    printBranches(branchLen, nodeSpaceLen, startLen, nodesInThisLevel, nodesQueue, _out);
    printLeaves(indentSpace, level, nodesInThisLevel, nodesQueue, _out);
}

실습해 보니, ^^ 아래와 같이 잘 나오는 군요.

ContainerOnTree ct = new ContainerOnTree();

ct.Add(30);
ct.Add(20);
ct.Add(40);
ct.Add(10);
ct.Add(25);
ct.Add(35);
ct.Add(50);
ct.Add(5);
ct.Add(15);
ct.Add(28);
ct.Add(41);

        ______30______
       /              \
    __20__          __40__
   /      \        /      \
  10      25      35      50
 /  \       \            /
 5  15      28          41

이 외에, 비주얼 스튜디오 사용자라면 DGML(Directed Graph Markup Language)을 이용하는 방법도 고려해 볼 수 있습니다. 다음과 같이 xml 텍스트 파일로 저장하고,

File.WriteAllText("test.dgml", ct.ToDGML());

public string ToDGML()
{
    StringBuilder sb = new StringBuilder();

    sb.AppendLine("<?xml version=\"1.0\" encoding=\"utf - 8\"?>");
    sb.AppendLine("<DirectedGraph Layout=\"TopToBottom\" Title=\"Tree\" xmlns=\"http://schemas.microsoft.com/vs/2009/dgml\">");

    StringBuilder nodes = new StringBuilder();
    StringBuilder links = new StringBuilder();

    DrawNodeDGML(nodes, links, _root);
    sb.AppendLine("<Nodes>" + nodes.ToString() + "</Nodes>");
    sb.AppendLine("<Links>" + links.ToString() + "</Links>");

    sb.AppendLine("</DirectedGraph>");
    return sb.ToString();
}

private void DrawNodeDGML(StringBuilder nodes, StringBuilder links, Node node)
{
    nodes.AppendLine(string.Format("<Node Id=\"{0}\" Label=\"{1}\" />", node.Data, node.Data));

    if (node.Left != null)
    {
        links.AppendLine(string.Format("<Link Source=\"{0}\" Label=\"Left\" Target=\"{1}\" />", node.Data, node.Left.Data));
        DrawNodeDGML(nodes, links, node.Left);
    }

    if (node.Right != null)
    {
        links.AppendLine(string.Format("<Link Source=\"{0}\" Label=\"Right\" Target=\"{1}\" />", node.Data, node.Right.Data));
        DrawNodeDGML(nodes, links, node.Right);
    }
}

해당 .dgml 파일을 비주얼 스튜디오에 끌어다 놓으면 다음과 같은 화면을 볼 수 있습니다.

print_tree_1.png

바이너리 트리 전용이 아닌 전반적인 Graph 시각화 도구라서 좌/우 뻗어나가는 처리가 왼쪽으로만 고려된 면이 좀 아쉽긴 한데 그래도 데이터 내용을 확인하는 데에는 깔끔한 맛에 쓸만 합니다. ^^ (물론, 원한다면 비주얼 스튜디오에서 마우스를 이용해 위치를 자유롭게 이동/편집할 수 있습니다.)

(첨부한 파일은 이 글의 테스트 코드를 포함합니다.)




[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]

[연관 글]






[최초 등록일: ]
[최종 수정일: 3/21/2016]

Creative Commons License
이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.
by SeongTae Jeong, mailto:techsharer at outlook.com

비밀번호

댓글 작성자
 




... 16  17  18  19  20  [21]  22  23  24  25  26  27  28  29  30  ...
NoWriterDateCnt.TitleFile(s)
13455정성태11/25/202312517닷넷: 2168. C# - Azure.AI.OpenAI 패키지로 OpenAI 사용파일 다운로드1
13454정성태11/23/202312897닷넷: 2167. C# - Qdrant Vector DB를 이용한 Embedding 벡터 값 보관/조회 (Azure OpenAI) [1]파일 다운로드1
13453정성태11/23/202310729오류 유형: 879. docker desktop 설치 시 "Invalid JSON string. (Exception from HRESULT: 0x83750007)"
13452정성태11/22/202311530닷넷: 2166. C# - Azure OpenAI API를 이용해 사용자가 제공하는 정보를 대상으로 검색하는 방법파일 다운로드1
13451정성태11/21/202311645닷넷: 2165. C# - Azure OpenAI API를 이용해 ChatGPT처럼 동작하는 콘솔 응용 프로그램 제작파일 다운로드1
13450정성태11/21/202311508닷넷: 2164. C# - Octokit을 이용한 GitHub Issue 검색파일 다운로드1
13449정성태11/21/202312057개발 환경 구성: 688. Azure OpenAI 서비스 신청 방법
13448정성태11/20/202311310닷넷: 2163. .NET 8 - Dynamic PGO를 결합한 성능 향상파일 다운로드1
13447정성태11/16/202311997닷넷: 2162. ASP.NET Core 웹 사이트의 SSL 설정을 코드로 하는 방법
13446정성태11/16/202312353닷넷: 2161. .NET Conf 2023 - Day 1 Blazor 개요 정리
13445정성태11/15/202313389Linux: 62. 리눅스/WSL에서 CA 인증서를 저장하는 방법
13444정성태11/15/202312488닷넷: 2160. C# 12 - Experimental 특성 지원
13443정성태11/14/202311804개발 환경 구성: 687. OpenSSL로 생성한 사용자 인증서를 ASP.NET Core 웹 사이트에 적용하는 방법
13442정성태11/13/202311257개발 환경 구성: 686. 비주얼 스튜디오로 실행한 ASP.NET Core 사이트를 WSL 2 인스턴스에서 https로 접속하는 방법
13441정성태11/12/202312142닷넷: 2159. C# - ASP.NET Core 프로젝트에서 서버 Socket을 직접 생성하는 방법파일 다운로드1
13440정성태11/11/202310731Windows: 253. 소켓 Listen 시 방화벽의 Public/Private 제어 기능이 비활성화된 경우
13439정성태11/10/202312519닷넷: 2158. C# - 소켓 포트를 미리 시스템에 등록/예약해 사용하는 방법(Port Exclusion Ranges)파일 다운로드1
13438정성태11/9/202312881닷넷: 2157. C# - WinRT 기능을 이용해 윈도우에서 실행 중인 Media App 제어
13437정성태11/8/202313054닷넷: 2156. .NET 7 이상의 콘솔 프로그램을 (dockerfile 없이) 로컬 docker에 배포하는 방법
13436정성태11/7/202313163닷넷: 2155. C# - .NET 8 런타임부터 (Reflection 없이) 특성을 이용해 public이 아닌 멤버 호출 가능
13435정성태11/6/202311704닷넷: 2154. C# - 네이티브 자원을 포함한 관리 개체(예: 스레드)의 GC 정리
13434정성태11/1/202312373스크립트: 62. 파이썬 - class의 정적 함수를 동적으로 교체
13433정성태11/1/202310890스크립트: 61. 파이썬 - 함수 오버로딩 미지원
13432정성태10/31/202311964오류 유형: 878. 탐색기의 WSL 디렉터리 접근 시 "Attempt to access invalid address." 오류 발생
13431정성태10/31/202312288스크립트: 60. 파이썬 - 비동기 FastAPI 앱을 gunicorn으로 호스팅
13430정성태10/30/202312829닷넷: 2153. C# - 사용자가 빌드한 ICU dll 파일을 사용하는 방법
... 16  17  18  19  20  [21]  22  23  24  25  26  27  28  29  30  ...