我有简单的二叉搜索树
public class BNode
{
public int item;
public BNode right;
public BNode left;
public BNode(int item)
{
this.item = item;
}
}
public class BTree
{
private BNode _root;
private int _count;
private IComparer<int> _comparer = Comparer<int>.Default;
public BTree()
{
_root = null;
_count = 0;
}
public bool Add(int Item)
{
if (_root == null)
{
_root = new BNode(Item);
_count++;
return true;
}
else
{
return Add_Sub(_root,Item);
}
}
private bool Add_Sub(BNode Node,int Item)
{
if (_comparer.Compare(Node.item,Item) < 0)
{
if (Node.right == null)
{
Node.right = new BNode(Item);
_count++;
return true;
}
else
{
return Add_Sub(Node.right,Item);
}
}
else if (_comparer.Compare(Node.item,Item) > 0)
{
if (Node.left == null)
{
Node.left = new BNode(Item);
_count++;
return true;
}
else
{
return Add_Sub(Node.left,Item);
}
}
else
{
return false;
}
}
public void Print()
{
Print(_root,4);
}
public void Print(BNode p,int padding)
{
if (p != null)
{
if (p.right != null)
{
Print(p.right,padding + 4);
}
if (padding > 0)
{
Console.Write(" ".PadLeft(padding));
}
if (p.right != null)
{
Console.Write("/\n");
Console.Write(" ".PadLeft(padding));
}
Console.Write(p.item.ToString() + "\n ");
if (p.left != null)
{
Console.Write(" ".PadLeft(padding) + "\\\n");
Print(p.left,padding + 4);
}
}
}
}
我可以在其中插入值
BTree btr = new BTree(); btr.Add(6); btr.Add(2); btr.Add(3); btr.Add(11); btr.Add(30); btr.Add(9); btr.Add(13); btr.Add(18);
我想在我的控制台应用程序中显示我的树.我有一个btr.Print();它从左到右显示我的树(6是根) – 但我不满意.
问题：在控制台应用程序中是否有更好的方式显示此树？即使改进此Print()也可以帮助我.
解决方法
我结束了以下方法,允许您打印任意子树：
public static class BTreePrinter
{
class NodeInfo
{
public BNode Node;
public string Text;
public int StartPos;
public int Size { get { return Text.Length; } }
public int EndPos { get { return StartPos + Size; } set { StartPos = value - Size; } }
public NodeInfo Parent,Left,Right;
}
public static void Print(this BNode root,string textFormat = "0",int spacing = 1,int topMargin = 2,int leftMargin = 2)
{
if (root == null) return;
int rootTop = Console.CursorTop + topMargin;
var last = new List<NodeInfo>();
var next = root;
for (int level = 0; next != null; level++)
{
var item = new NodeInfo { Node = next,Text = next.item.ToString(textFormat) };
if (level < last.Count)
{
item.StartPos = last[level].EndPos + spacing;
last[level] = item;
}
else
{
item.StartPos = leftMargin;
last.Add(item);
}
if (level > 0)
{
item.Parent = last[level - 1];
if (next == item.Parent.Node.left)
{
item.Parent.Left = item;
item.EndPos = Math.Max(item.EndPos,item.Parent.StartPos - 1);
}
else
{
item.Parent.Right = item;
item.StartPos = Math.Max(item.StartPos,item.Parent.EndPos + 1);
}
}
next = next.left ?? next.right;
for (; next == null; item = item.Parent)
{
int top = rootTop + 2 * level;
Print(item.Text,top,item.StartPos);
if (item.Left != null)
{
Print("/",top + 1,item.Left.EndPos);
Print("_",item.Left.EndPos + 1,item.StartPos);
}
if (item.Right != null)
{
Print("_",item.EndPos,item.Right.StartPos - 1);
Print("\\",item.Right.StartPos - 1);
}
if (--level < 0) break;
if (item == item.Parent.Left)
{
item.Parent.StartPos = item.EndPos + 1;
next = item.Parent.Node.right;
}
else
{
if (item.Parent.Left == null)
item.Parent.EndPos = item.StartPos - 1;
else
item.Parent.StartPos += (item.StartPos - 1 - item.Parent.EndPos) / 2;
}
}
}
Console.SetCursorPosition(0,rootTop + 2 * last.Count - 1);
}
private static void Print(string s,int top,int left,int right = -1)
{
Console.SetCursorPosition(left,top);
if (right < 0) right = left + s.Length;
while (Console.CursorLeft < right) Console.Write(s);
}
}
您可以看到,我添加了一些影响格式的参数.默认情况下,它产生最紧凑的表示.
为了玩它,我修改了BTree类,如下所示：
public class BTree
{
// ...
public BNode Root { get { return _root; } }
public void Print()
{
Root.Print();
}
}
使用您的样本数据,这里有一些结果：
btr.Root.Print();
btr.Root.Print(textFormat：“(0)”,spacing：2);
更新：IMO上面的默认格式是紧凑可读的,但只是为了乐趣,调整的算法产生更多的“图形”输出(textFormat和间距参数被删除)：
public static class BTreePrinter
{
class NodeInfo
{
public BNode Node;
public string Text;
public int StartPos;
public int Size { get { return Text.Length; } }
public int EndPos { get { return StartPos + Size; } set { StartPos = value - Size; } }
public NodeInfo Parent,Text = next.item.ToString(" 0 ") };
if (level < last.Count)
{
item.StartPos = last[level].EndPos + 1;
last[level] = item;
}
else
{
item.StartPos = leftMargin;
last.Add(item);
}
if (level > 0)
{
item.Parent = last[level - 1];
if (next == item.Parent.Node.left)
{
item.Parent.Left = item;
item.EndPos = Math.Max(item.EndPos,item.Parent.StartPos);
}
else
{
item.Parent.Right = item;
item.StartPos = Math.Max(item.StartPos,item.Parent.EndPos);
}
}
next = next.left ?? next.right;
for (; next == null; item = item.Parent)
{
Print(item,rootTop + 2 * level);
if (--level < 0) break;
if (item == item.Parent.Left)
{
item.Parent.StartPos = item.EndPos;
next = item.Parent.Node.right;
}
else
{
if (item.Parent.Left == null)
item.Parent.EndPos = item.StartPos;
else
item.Parent.StartPos += (item.StartPos - item.Parent.EndPos) / 2;
}
}
}
Console.SetCursorPosition(0,rootTop + 2 * last.Count - 1);
}
private static void Print(NodeInfo item,int top)
{
SwapColors();
Print(item.Text,item.StartPos);
SwapColors();
if (item.Left != null)
PrintLink(top + 1,"┌","┘",item.Left.StartPos + item.Left.Size / 2,item.StartPos);
if (item.Right != null)
PrintLink(top + 1,"└","┐",item.EndPos - 1,item.Right.StartPos + item.Right.Size / 2);
}
private static void PrintLink(int top,string start,string end,int startPos,int endPos)
{
Print(start,startPos);
Print("─",startPos + 1,endPos);
Print(end,endPos);
}
private static void Print(string s,top);
if (right < 0) right = left + s.Length;
while (Console.CursorLeft < right) Console.Write(s);
}
private static void SwapColors()
{
var color = Console.ForegroundColor;
Console.ForegroundColor = Console.BackgroundColor;
Console.BackgroundColor = color;
}
}
结果是：
