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

비밀번호

댓글 작성자
 




... 181  182  183  184  185  186  187  188  189  190  [191]  192  193  194  195  ...
NoWriterDateCnt.TitleFile(s)
287정성태6/24/200619346    답변글 Team Foundation Server: 7.1. 외부 빌드 머신 구성 - 다른 블로그 자료
275정성태6/7/200627366디버깅 기술: 4. VC++ 8.0 원격 디버깅 구성 - Side-by-Side DLL 문제.
269정성태6/6/200624253Team Foundation Server: 6. HTTPS를 통한 Team Server 접근 [1]
270정성태6/5/200621671    답변글 Team Foundation Server: 6.1. HTTPS를 통한 Team Server 접근 [1]
273정성태6/6/200624335    답변글 Team Foundation Server: 6.2. 두번째 방법 - HTTPS 를 통한 Team Server 접근 [1]
267정성태6/4/200623712Team Foundation Server: 5. 인터넷으로 Team Server 접근 [2]
266정성태6/8/200620020오류 유형: 7. [설치] mpoai9.dll 관련 오류
265정성태6/1/200627766디버깅 기술: 3. 원격 컴퓨터 디버깅 - VPC 설정
314정성태8/11/200625085    답변글 디버깅 기술: 3.1. Managed 원격 디버깅과 WinDBG 원격 디버깅
264정성태6/1/200634493오류 유형: 6. [VC++ 컴파일] already defined in ntdll.lib(ntdll.dll)
263정성태6/1/200635176디버깅 기술: 2. 커널 구조체 살펴보기 [5]
262정성태6/1/200627987오류 유형: 5. [설치] WinFX Beta2 - 설치시 문제점 해결
261정성태6/1/200623915웹: 3. IIS 6.0 - AppPool을 활용하여 실 서버(운영 서버)에서 디버깅
258정성태6/1/200631861디버깅 기술: 1. 디버깅 방법 - CLR 프로파일러 [1]파일 다운로드1
274정성태6/7/200624763    답변글 디버깅 기술: 1.1. 디버깅 방법 - CLR 프로파일러 ( on Vista )
254정성태6/1/200621107개발 환경 구성: 2. VPC에 Vista 설치하는 방법 [2]
255정성태6/1/200621128    답변글 개발 환경 구성: 2.1. msconfig 설정과 Windows Activation
259정성태6/1/200619981    답변글 개발 환경 구성: 2.2. Vista VPC에 터미널 서비스 - 원격 접속
253정성태6/1/200617734기타: 14. .NET 2.0 이 지원되는 NDoc 2.0 을 배포합니다.
251정성태6/1/200621134오류 유형: 4. [OS 지원 API] SHParseDisplayName과 Windows 2000
252정성태6/1/200620462    답변글 오류 유형: 4.1. NET BCL 에서 제공되는 FolderBrowserDialog [2]
249정성태6/1/200620465.NET Framework: 71. VB.NET 이외의 언어에서 My 네임스페이스 사용
250정성태6/1/200623483    답변글 .NET Framework: 71.1. VB.NET 이외의 언어에서 My 네임스페이스 사용
248정성태6/1/200621825기타: 13. Code Center Premium에서 Win32 API 소스 찾기
245정성태6/1/200629165오류 유형: 3. [C# / VC++] error C2146: syntax error : missing ';' before identifier 'GetType'
247정성태5/3/200626535    답변글 .NET Framework: 3.1. Interface를 사용하면. [1]
... 181  182  183  184  185  186  187  188  189  190  [191]  192  193  194  195  ...