C＃在Console中显示二进制搜索树

我有简单的二叉搜索树

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 _comparer = Comparer.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.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()也会对我有所帮助。

Answer 1

我最终得到了以下允许您打印任意子树的方法：

 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(); 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("_", top, item.Left.EndPos + 1, item.StartPos); } if (item.Right != null) { Print("_", top, item.EndPos, item.Right.StartPos - 1); Print("\\", top + 1, 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和spacing参数）：

 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, int topMargin = 2, int leftMargin = 2) { if (root == null) return; int rootTop = Console.CursorTop + topMargin; var last = new List(); var next = root; for (int level = 0; next != null; level++) { var item = new NodeInfo { Node = next, 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, top, 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, top, startPos); Print("─", top, startPos + 1, endPos); Print(end, top, endPos); } 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); } private static void SwapColors() { var color = Console.ForegroundColor; Console.ForegroundColor = Console.BackgroundColor; Console.BackgroundColor = color; } } 

结果是：

Answer 2

这是我的看法：

我已经将PrintPretty添加到BNode，我已经删除了你在BTree中的第二个Printfunction。

（编辑：我通过改变原始的字符来绘制树的分支，使树变得更加可见）

  static void Main(string[] args) { 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(); } public class BNode { public int item; public BNode right; public BNode left; public BNode(int item) { this.item = item; } public void PrintPretty(string indent, bool last) { Console.Write(indent); if (last) { Console.Write("└─"); indent += " "; } else { Console.Write("├─"); indent += "| "; } Console.WriteLine(item); var children = new List(); if (this.left != null) children.Add(this.left); if (this.right != null) children.Add(this.right); for (int i = 0; i < children.Count; i++) children[i].PrintPretty(indent, i == children.Count - 1); } } public class BTree { private BNode _root; private int _count; private IComparer _comparer = Comparer.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() { _root.PrintPretty("", true); } } 

这是结果（更紧凑，正如我所提到的）：

---

编辑：以下代码已被修改，以显示有关左右的信息：

  static void Main(string[] args) { 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(); } public enum NodePosition { left, right, center } public class BNode { public int item; public BNode right; public BNode left; public BNode(int item) { this.item = item; } private void PrintValue(string value, NodePosition nodePostion) { switch (nodePostion) { case NodePosition.left: PrintLeftValue(value); break; case NodePosition.right: PrintRightValue(value); break; case NodePosition.center: Console.WriteLine(value); break; default: throw new NotImplementedException(); } } private void PrintLeftValue(string value) { Console.ForegroundColor = ConsoleColor.Magenta; Console.Write("L:"); Console.ForegroundColor = (value == "-") ? ConsoleColor.Red : ConsoleColor.Gray; Console.WriteLine(value); Console.ForegroundColor = ConsoleColor.Gray; } private void PrintRightValue(string value) { Console.ForegroundColor = ConsoleColor.Green; Console.Write("R:"); Console.ForegroundColor = (value == "-") ? ConsoleColor.Red : ConsoleColor.Gray; Console.WriteLine(value); Console.ForegroundColor = ConsoleColor.Gray; } public void PrintPretty(string indent, NodePosition nodePosition, bool last, bool empty) { Console.Write(indent); if (last) { Console.Write("└─"); indent += " "; } else { Console.Write("├─"); indent += "| "; } var stringValue = empty ? "-" : item.ToString(); PrintValue(stringValue, nodePosition); if(!empty && (this.left != null || this.right != null)) { if (this.left != null) this.left.PrintPretty(indent, NodePosition.left, false, false); else PrintPretty(indent, NodePosition.left, false, true); if (this.right != null) this.right.PrintPretty(indent, NodePosition.right, true, false); else PrintPretty(indent, NodePosition.right, true, true); } } } public class BTree { private BNode _root; private int _count; private IComparer _comparer = Comparer.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() { _root.PrintPretty("", NodePosition.center, true, false); } } 

结果：