C # Displaying binary search tree in console

Question

I have a simple binary search tree

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); } } } } 

where can i insert values ​​like

 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); 

I want to display my tree in my console application. I have btr.Print(); which displays my tree from left to right ( 6 is the root), but I'm not happy with it.

Question : Is there a better way to display this tree in a console application? Even improving this Print() will help me.

Answer 1

I ended up with the following method, which allows you to print an arbitrary subtree:

 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("_", 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); } } 

As you can see, I added some options that affect formatting. By default, it creates the most compact view.

To play with it, I changed the BTree class as follows:

 public class BTree { // ... public BNode Root { get { return _root; } } public void Print() { Root.Print(); } } 

Using your sample data, here are a few results:

btr.Root.Print();

btr.Root.Print(textFormat: "(0)", spacing: 2);

UPDATE: IMO. The default format above is compact and readable, but just for fun, the adjusted algorithm for creating more "graphical" output ( textFormat and spacing parameters removed):

 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<NodeInfo>(); 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; } } 

and the result:

Answer 2

This is my occupation:

I added PrintPretty to BNode and I removed the second Print function that you had in BTree.

(Edit: I made the tree more accessible by changing the original characters to draw tree branches)

  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<BNode>(); 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<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() { _root.PrintPretty("", true); } } 

This is the result (more compact, as I mentioned):

---

Edit: The following code has been modified to show left-right information:

  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<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() { _root.PrintPretty("", NodePosition.center, true, false); } } 

Result: