디버깅 용도로 이진 트리의 내용을 출력하는 방법
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 파일을 비주얼 스튜디오에 끌어다 놓으면 다음과 같은 화면을 볼 수 있습니다.
바이너리 트리 전용이 아닌 전반적인 Graph 시각화 도구라서 좌/우 뻗어나가는 처리가 왼쪽으로만 고려된 면이 좀 아쉽긴 한데 그래도 데이터 내용을 확인하는 데에는 깔끔한 맛에 쓸만 합니다. ^^ (물론, 원한다면 비주얼 스튜디오에서 마우스를 이용해 위치를 자유롭게 이동/편집할 수 있습니다.)
(
첨부한 파일은 이 글의 테스트 코드를 포함합니다.)
[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]