TreeDrawer.cs

usingSystem;
usingSystem.Collections.Generic;
usingSystem.Linq;
usingDataStructures.Common;

namespaceDataStructures.Trees
{
publicstaticclassTreeDrawer
{
/// <summary>
/// Public API.
/// Extension method for BinarySearchTree<T>.
/// Returns a visualized binary search tree text.
/// </summary>
publicstaticstringDrawTree<T>(thisIBinarySearchTree<T>tree)whereT:IComparable<T>
{
intposition,width;
returnString.Join("\n",_recursivelyDrawTree(tree.Root,outposition,outwidth));
}

publicstaticstringDrawTree<TKey,TValue>(thisIBinarySearchTree<TKey,TValue>tree,boolincludeValues=false)whereTKey:IComparable<TKey>
{
intposition,width;
returnString.Join("\n",_recursivelyDrawTree(tree.Root,outposition,outwidth,includeValues));
}


/// <summary>
/// /// Recusively draws the tree starting from node.
/// To construct a full tree representation concatenate the returned list of strings by '\n'.
///
/// Example:
/// int position, width;
/// var fullTree = String.Join("\n", _recursivelyDrawTree(this.Root, out position, out width));
///
/// Algorithm developed by MIT OCW.
/// http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/readings/binary-search-trees/bstsize_r.py
/// </summary>
/// <param name="node"></param>
/// <param name="positionOutput"></param>
/// <param name="widthOutput"></param>
/// <returns>List of tree levels as strings.</returns>
privatestaticList<string>_recursivelyDrawTree<T>
(BSTNode<T>node,outintpositionOutput,outintwidthOutput)
whereT:IComparable<T>
{
widthOutput=0;
positionOutput=0;

if(node==null)
{
returnnewList<string>();
}

//
// Variables
intleftPosition,rightPosition,leftWidth,rightWidth;

//
// Start drawing
varnodeLabel=Convert.ToString(node.Value);

// Visit the left child
List<string>leftLines=_recursivelyDrawTree(node.LeftChild,outleftPosition,outleftWidth);

// Visit the right child
List<string>rightLines=_recursivelyDrawTree(node.RightChild,outrightPosition,outrightWidth);

// Calculate pads
intmiddle=Math.Max(Math.Max(2,nodeLabel.Length),(rightPosition+leftWidth-leftPosition+1));
intposition_out=leftPosition+middle/2;
intwidth_out=leftPosition+middle+rightWidth-rightPosition;

while(leftLines.Count<rightLines.Count)
leftLines.Add(newString(' ',leftWidth));

while(rightLines.Count<leftLines.Count)
rightLines.Add(newString(' ',rightWidth));

if((middle-nodeLabel.Length%2==1)&&(nodeLabel.Length<middle)&&(node.Parent!=null&&node.IsLeftChild))
nodeLabel+=".";

// Format the node's label
nodeLabel=nodeLabel.PadCenter(middle,'.');

varnodeLabelChars=nodeLabel.ToCharArray();

if(nodeLabelChars[0]=='.')
nodeLabelChars[0]=' ';

if(nodeLabelChars[nodeLabelChars.Length-1]=='.')
nodeLabelChars[nodeLabelChars.Length-1]=' ';

nodeLabel=String.Join("",nodeLabelChars);

//
// Construct the list of lines.
stringleftBranch=node.HasLeftChild?"/":" ";
stringrightBranch=node.HasRightChild?"\\":" ";

List<string>listOfLines=newList<string>()
{
// 0
(newString(' ',leftPosition))+nodeLabel+(newString(' ',(rightWidth-rightPosition))),

// 1
(newString(' ',leftPosition))+leftBranch+(newString(' ',(middle-2)))+rightBranch+(newString(' ',(rightWidth-rightPosition)))
};

//
// Add the right lines and left lines to the final list of lines.
listOfLines.AddRange(leftLines.Zip(rightLines,(leftLine,rightLine)=>
leftLine+(newString(' ',(width_out-leftWidth-rightWidth)))+rightLine));

//
// Return
widthOutput=width_out;
positionOutput=position_out;
returnlistOfLines;
}


privatestaticList<string>_recursivelyDrawTree<TKey,TValue>
(BSTMapNode<TKey,TValue>node,outintpositionOutput,outintwidthOutput,boolincludeValues=false)
whereTKey:IComparable<TKey>
{
widthOutput=0;
positionOutput=0;
List<string>listOfLines=newList<string>();

if(node==null)
{
returnlistOfLines;
}

//
// Variables
stringnodeLabel="";
intpadValue=0;

List<string>leftLines,rightLines;
leftLines=rightLines=newList<string>();

intleftPosition=0,rightPosition=0;
intleftWidth=0,rightWidth=0;
intmiddle,position_out,width_out;

//
// Start drawing
if(includeValues==true)
{
nodeLabel=String.Format("<{0}: {1}>",Convert.ToString(node.Key),Convert.ToString(node.Value));
padValue=4;
}
else
{
nodeLabel=Convert.ToString(node.Key);
padValue=2;
}

// Visit the left child
leftLines=_recursivelyDrawTree(node.LeftChild,outleftPosition,outleftWidth,includeValues);

// Visit the right child
rightLines=_recursivelyDrawTree(node.RightChild,outrightPosition,outrightWidth,includeValues);

// Calculate pads
middle=Math.Max(Math.Max(padValue,nodeLabel.Length),(rightPosition+leftWidth-leftPosition+1));
position_out=leftPosition+middle;
width_out=leftPosition+middle+rightWidth-rightPosition;

while(leftLines.Count<rightLines.Count)
leftLines.Add(newString(' ',leftWidth));

while(rightLines.Count<leftLines.Count)
rightLines.Add(newString(' ',rightWidth));

if((middle-nodeLabel.Length%padValue==1)&&(nodeLabel.Length<middle)&&(node.Parent!=null&&node.IsLeftChild))
nodeLabel+=".";

// Format the node's label
nodeLabel=nodeLabel.PadCenter(middle,'.');

varnodeLabelChars=nodeLabel.ToCharArray();

if(nodeLabelChars[0]=='.')
nodeLabelChars[0]=' ';

if(nodeLabelChars[nodeLabelChars.Length-1]=='.')
nodeLabelChars[nodeLabelChars.Length-1]=' ';

nodeLabel=String.Join("",nodeLabelChars);

//
// Construct the list of lines.
listOfLines=newList<string>()
{
// 0
(newString(' ',leftPosition))+nodeLabel+(newString(' ',(rightWidth-rightPosition))),

// 1
(newString(' ',leftPosition))+"/"+(newString(' ',(middle-padValue)))+"\\"+(newString(' ',(rightWidth-rightPosition)))
};

//
// Add the right lines and left lines to the final list of lines.
listOfLines=
listOfLines.Concat(
leftLines.Zip(
rightLines,(left_line,right_line)=>
left_line+(newString(' ',(width_out-leftWidth-rightWidth)))+right_line)
).ToList();

//
// Return
widthOutput=width_out;
positionOutput=position_out;
returnlistOfLines;
}
}
}