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)
13281정성태3/12/202314371Windows: 225. 윈도우 바탕화면의 아이콘들이 넓게 퍼지는 경우 [2]
13280정성태3/9/202317109개발 환경 구성: 670. WSL 2에서 호스팅 중인 TCP 서버를 외부에서 접근하는 방법
13279정성태3/9/202316299오류 유형: 851. 파이썬 ModuleNotFoundError: No module named '_cffi_backend'
13278정성태3/8/202316164개발 환경 구성: 669. WSL 2의 (init이 아닌) systemd 지원 [1]
13277정성태3/6/202316321개발 환경 구성: 668. 코드 사인용 인증서 신청 및 적용 방법(예: Digicert)
13276정성태3/5/202317109.NET Framework: 2102. C# 11 - ref struct/ref field를 위해 새롭게 도입된 scoped 예약어 [1]
13275정성태3/3/202317422.NET Framework: 2101. C# 11의 ref 필드 설명
13274정성태3/2/202316284.NET Framework: 2100. C# - ref 필드로 ref struct 타입을 허용하지 않는 이유
13273정성태2/28/202313712.NET Framework: 2099. C# - 관리 포인터로서의 ref 예약어 의미
13272정성태2/27/202314667오류 유형: 850. SSMS - mdf 파일을 Attach 시킬 때 Operating system error 5: "5(Access is denied.)" 에러
13271정성태2/25/202314703오류 유형: 849. Sql Server Configuration Manager가 시작 메뉴에 없는 경우
13270정성태2/24/202314290.NET Framework: 2098. dotnet build에 /p 옵션을 적용 시 유의점
13269정성태2/23/202316102스크립트: 46. 파이썬 - uvicorn의 콘솔 출력을 UDP로 전송
13268정성태2/22/202315406개발 환경 구성: 667. WSL 2 내부에서 열고 있는 UDP 서버를 호스트 측에서 접속하는 방법
13267정성태2/21/202316846.NET Framework: 2097. C# - 비동기 소켓 사용 시 메모리 해제가 finalizer 단계에서 발생하는 사례파일 다운로드1
13266정성태2/20/202314946오류 유형: 848. .NET Core/5+ - Process terminated. Couldn't find a valid ICU package installed on the system
13265정성태2/18/202316970.NET Framework: 2096. .NET Core/5+ - PublishSingleFile 유형에 대한 runtimeconfig.json 설정
13264정성태2/17/202319228스크립트: 45. 파이썬 - uvicorn 사용자 정의 Logger 작성
13263정성태2/16/202314973개발 환경 구성: 666. 최신 버전의 ilasm.exe/ildasm.exe 사용하는 방법
13262정성태2/15/202317224디버깅 기술: 191. dnSpy를 이용한 (소스 코드가 없는) 닷넷 응용 프로그램 디버깅 방법 [1]
13261정성태2/15/202316682Windows: 224. Visual Studio - 영문 폰트가 Fullwidth Latin Character로 바뀌는 문제 [1]
13260정성태2/14/202316491오류 유형: 847. ilasm.exe 컴파일 오류 - error : syntax error at token '-' in ... -inf
13259정성태2/14/202314549.NET Framework: 2095. C# - .NET5부터 도입된 CollectionsMarshal
13258정성태2/13/202317429오류 유형: 846. .NET Framework 4.8 Developer Pack 설치 실패 - 0x81f40001
13257정성태2/13/202316919.NET Framework: 2094. C# - Job에 Process 포함하는 방법 [2]파일 다운로드1
13256정성태2/10/202315047개발 환경 구성: 665. WSL 2의 네트워크 통신 방법 - 두 번째 이야기
... 16  17  18  19  20  21  22  23  24  25  26  27  28  29  [30]  ...