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

비밀번호

댓글 작성자
 




... 151  152  153  154  155  156  157  158  159  160  161  [162]  163  164  165  ...
NoWriterDateCnt.TitleFile(s)
1089정성태7/18/201135247.NET Framework: 234. 왜? Button 컨트롤에는 MouseDown/MouseUp 이벤트가 발생하지 않을까요?파일 다운로드1
1088정성태7/16/201128677.NET Framework: 233. Entity Framework 4.1 - 윈도우 폰 7에서의 CodeFirst 순환 참조 문제파일 다운로드1
1087정성태7/15/201130888.NET Framework: 232. Entity Framework 4.1 - CodeFirst 개체의 직렬화 시 순환 참조 해결하는 방법 - 두 번째 이야기파일 다운로드1
1086정성태7/14/201132162.NET Framework: 231. Entity Framework 4.1 - CodeFirst 개체의 직렬화 시 순환 참조 해결하는 방법 [1]파일 다운로드1
1085정성태7/14/201132811.NET Framework: 230. Entity Framework 4.1 - Code First + WCF 서비스 시 EndpointNotFoundException 오류 - 두 번째 이야기파일 다운로드1
1084정성태7/11/201138487.NET Framework: 229. SQL 서버 - DB 테이블의 데이터 변경에 대한 알림 처리 [4]파일 다운로드1
1083정성태7/11/201132562.NET Framework: 228. Entity Framework 4.1 - Code First + WCF 서비스 시 EndpointNotFoundException 오류
1082정성태7/10/201132429.NET Framework: 227. basicHttpBinding + 사용자 정의 인증 구현 [2]파일 다운로드1
1081정성태7/9/201131210VC++: 53. Windows 7에서 gcc.exe 실행 시 Access denied 오류 [2]
1080정성태7/8/201130138웹: 23. Sysnet 웹 사이트의 HTML5 변환 기록 - 두 번째 이야기파일 다운로드1
1079정성태7/6/201134442오류 유형: 129. Hyper-V + Realtek 랜카드가 설치된 시스템의 BSOD 현상 [2]
1078정성태7/5/201142181VC++: 52. Chromium 컴파일하는 방법 [2]
1077정성태6/24/201139209.NET Framework: 226. HttpWebRequest 타입의 HaveResponse 속성 이야기파일 다운로드1
1076정성태6/23/201133948오류 유형: 128. SQL Express - User Instance 옵션을 사용한 경우 발생하는 오류 메시지 유형 2가지
1075정성태6/21/201129054VS.NET IDE: 69. 윈폰 프로젝트에서 WCF 서비스 참조할 때 Reference.cs 파일이 비어있는 경우
1074정성태6/20/201129198.NET Framework: 225. 닷넷 네트워크 라이브러리의 트레이스 기능파일 다운로드1
1073정성태6/20/201131394오류 유형: 127. Visual Studio에서 WCF 서비스의 이름 변경 시 발생할 수 있는 오류
1072정성태6/19/201131015.NET Framework: 224. EF 4.1 Code First에서 Identity 칼럼 생성하는 방법파일 다운로드1
1071정성태6/19/201134526.NET Framework: 223. Entity Framework 4.1의 Code First를 이용한 SQL Azure 데이터베이스 생성 [3]파일 다운로드1
1070정성태6/19/201132180.NET Framework: 222. Windows Azure - VM Role 베타 프로그램 참여 [2]
1069정성태6/18/201132266.NET Framework: 221. Cache 영향을 받지 않는 DNS 이름 풀이 [2]파일 다운로드1
1068정성태6/16/201129485개발 환경 구성: 127. Portable Library - 닷넷 N-Screen용 공통 라이브러리 제작 [1]
1067정성태6/15/201129136오류 유형: 126. Windows failed to apply the Group Policy Folder Options settings. [1]
1066정성태6/14/201132385개발 환경 구성: 126. MSDN 구독자 - Windows Azure 무료 서비스 신청하는 방법 [4]
1065정성태6/13/201137078개발 환경 구성: 125. Firebird - 유니코드 기본 문자셋 지정
1064정성태6/11/201131558웹: 22. Visual Studio 2010에서 CSS 3 인텔리센스(intellisense) 지원하는 방법 [1]
... 151  152  153  154  155  156  157  158  159  160  161  [162]  163  164  165  ...