C# Visualizzare un Binary Search Tree in Console

Question

ho semplice albero binario di ricerca

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

dove posso inserire i valori come

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

voglio visualizzare il mio albero all'interno della mia applicazione console. Ho un btr.Print(); che visualizza il mio albero da sinistra a destra (6 è la radice) - ma non ne sono felice.

Domanda: C'è un modo migliore per visualizzare questo albero all'interno di un'applicazione console? Anche un miglioramento di questo Print() mi aiuterebbe.

Answer 1

ho finito con il seguente metodo che consente di stampare sottostruttura arbitraria:

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

Come potete vedere, I' ho aggiunto alcuni parametri che influenzano la formattazione. Di default produce la rappresentazione più compatta.

Per poter giocare con lui, ho modificato la classe BTree come segue:

public class BTree 
{ 
    // ... 

    public BNode Root { get { return _root; } } 

    public void Print() 
    { 
     Root.Print(); 
    } 
} 

Utilizzando i dati di esempio, ecco alcuni risultati:

btr.Root.Print();

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

UPDATE: IMO il formato predefinito di cui sopra è compatto e leggibile, ma solo per divertimento, regolata l'algoritmo per produrre più uscita "grafica" (textFormat e spacing parametri rimossi):

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

e il risultato è:

Answer 2

Questo è il mio prendere a esso:

Ho aggiunto PrintPretty a bnode, e ho rimosso il secondo Print funzione che si aveva in BTree.

(Edit: ho fatto l'albero più lisible cambiando i caratteri originali per attirare i rami dell'albero)

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

    } 

Questo è il risultato (più compatte, come ho già detto):

---

Edit: il seguente codice è stato modificato al fine di mostrare le informazioni su sinistra-destra:

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

    } 

Il risultato: