C# einen binären Suchbaum in Console anzeigen

Question

Ich habe einfachen binären Suchbaum

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

wo ich Werte wie

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

einfügen Ich mag meinen Baum in meiner Konsolenanwendung angezeigt werden soll. Ich habe eine btr.Print();, die meinen Baum von links nach rechts anzeigt (6 ist die Wurzel) - aber ich bin nicht glücklich damit.

Frage: Gibt es eine bessere Art und Weise in einer Konsolenanwendung diesen Baum angezeigt werden? Auch eine Verbesserung dieser Print() würde mir helfen.

Answer 1

Ich habe mit dem folgenden Verfahren beendet, die Sie beliebige Teilstruktur drucken:

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

Wie Sie sehen können, ich Es wurden einige Parameter hinzugefügt, die sich auf die Formatierung auswirken. Standardmäßig erzeugt es die kompakteste Darstellung.

Um mit ihm zu spielen, ich habe die BTree Klasse geändert haben, wie folgt:

public class BTree 
{ 
    // ... 

    public BNode Root { get { return _root; } } 

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

Ihre Beispieldaten verwenden, sind hier einige Ergebnisse:

btr.Root.Print();

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

UPDATE: IMO das Standardformat oben ist kompakt und lesbar, aber nur zum Spaß, angepasst, um den Algorithmus mehr "grafischen" -Ausgang (textFormat und spacing Parameter entfernt) zu erzeugen:

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

und das Ergebnis ist:

Answer 2

Dies ist mein nehmen auf sie:

I PrintPretty zu bnode hinzugefügt haben, und ich habe die zweite Print Funktion, die Sie in BTree musste entfernt.

(Edit: Ich habe den Baum mehr lisible durch die ursprünglichen Zeichen Ändern den Zweig des Baumes zu zeichnen)

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

    } 

Dies ist das Ergebnis (kompakten, wie bereits erwähnt):

---

Edit: der folgende Code wird modifiziert, um die Daten zu links-rechts zu zeigen:

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

    } 

Das Ergebnis: