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

비밀번호

댓글 작성자
 




... 61  62  63  64  65  66  67  [68]  69  70  71  72  73  74  75  ...
NoWriterDateCnt.TitleFile(s)
12342정성태9/24/202023221디버깅 기술: 171. windbg - 인스턴스가 살아 있어 메모리 누수가 발생하고 있는지 확인하는 방법
12341정성태9/23/202020339.NET Framework: 944. C# - 인스턴스가 살아 있어 메모리 누수가 발생하고 있는지 확인하는 방법파일 다운로드1
12340정성태9/23/202020007.NET Framework: 943. WPF - WindowsFormsHost를 담은 윈도우 생성 시 메모리 누수
12339정성태9/21/202019964오류 유형: 655. 코어 모드의 윈도우는 GUI 모드의 윈도우로 교체가 안 됩니다.
12338정성태9/21/202022028오류 유형: 654. 우분투 설치 시 "CHS: Error 2001 reading sector ..." 오류 발생
12337정성태9/21/202021710오류 유형: 653. Windows - Time zone 설정을 바꿔도 반영이 안 되는 경우
12336정성태9/21/202026068.NET Framework: 942. C# - WOL(Wake On Lan) 구현
12335정성태9/21/202036651Linux: 31. 우분투 20.04 초기 설정 - 고정 IP 및 SSH 설치
12334정성태9/21/202021087오류 유형: 652. windbg - !py 확장 명령어 실행 시 "failed to find python interpreter"
12333정성태9/20/202021645.NET Framework: 941. C# - 전위/후위 증감 연산자에 대한 오버로딩 구현 (2)
12332정성태9/18/202023807.NET Framework: 940. C# - Windows Forms ListView와 DataGridView의 예제 코드파일 다운로드1
12331정성태9/18/202023340오류 유형: 651. repadmin /syncall - 0x80090322 The target principal name is incorrect.
12330정성태9/18/202023923.NET Framework: 939. C# - 전위/후위 증감 연산자에 대한 오버로딩 구현 [2]파일 다운로드1
12329정성태9/16/202026690오류 유형: 650. ASUS 메인보드 관련 소프트웨어 설치 후 ArmouryCrate.UserSessionHelper.exe 프로세스 무한 종료 현상
12328정성태9/16/202023206VS.NET IDE: 150. TFS의 이력에서 "Get This Version"과 같은 기능을 Git으로 처리한다면?
12327정성태9/12/202022580.NET Framework: 938. C# - ICS(Internet Connection Sharing) 제어파일 다운로드1
12326정성태9/12/202022256개발 환경 구성: 516. Azure VM의 Network Adapter를 실수로 비활성화한 경우
12325정성태9/12/202020871개발 환경 구성: 515. OpenVPN - 재부팅 후 ICS(Internet Connection Sharing) 기능이 동작 안하는 문제
12324정성태9/11/202021287개발 환경 구성: 514. smigdeploy.exe를 이용한 Windows Server 2016에서 2019로 마이그레이션 방법
12323정성태9/11/202021669오류 유형: 649. Copy Database Wizard - The job failed. Check the event log on the destination server for details.
12322정성태9/11/202026330개발 환경 구성: 513. Azure VM의 RDP 접속 위치 제한 [1]
12321정성태9/11/202019872오류 유형: 648. netsh http add urlacl - Error: 183 Cannot create a file when that file already exists.
12320정성태9/11/202023893개발 환경 구성: 512. RDP(원격 데스크톱) 접속 시 비밀 번호를 한 번 더 입력해야 하는 경우
12319정성태9/10/202021309오류 유형: 647. smigdeploy.exe를 Windows Server 2016에서 실행할 때 .NET Framework 미설치 오류 발생
12318정성태9/9/202020224오류 유형: 646. OpenVPN - "TAP-Windows Adapter V9" 어댑터의 "Network cable unplugged" 현상
12317정성태9/9/202024635개발 환경 구성: 511. Beats용 Kibana 기본 대시 보드 구성 방법
... 61  62  63  64  65  66  67  [68]  69  70  71  72  73  74  75  ...