C# Wyświetla binarne drzewo poszukiwań w konsoli

Question

Mam proste wyszukiwanie binarne drzewo

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

gdzie mogę wstawić wartości jak

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

chcę wyświetlić moje drzewo wewnątrz mojej aplikacji konsoli. Mam btr.Print();, który wyświetla moje drzewo od lewej do prawej (6 to root) - ale nie jestem z niego zadowolony.

Pytanie: Czy istnieje lepszy sposób wyświetlania tego drzewa w aplikacji konsoli? Pomoże mi nawet poprawa tego Print().

Answer 1

ja skończyło się następującą metodą, która pozwala na drukowanie dowolnego poddrzewa:

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

Jak widać, I” ve dodał niektóre parametry wpływające na formatowanie. Domyślnie tworzy najbardziej zwartą reprezentację.

Aby zagrać z nim, mam zmodyfikowano klasę BTree następująco:

public class BTree 
{ 
    // ... 

    public BNode Root { get { return _root; } } 

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

Twoje dane przykładowe, oto wyniki:

btr.Root.Print();

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

UPDATE: IMO domyślnym formatem powyżej jest zwarte i czytelne, ale tylko dla zabawy, dostosowane algorytm do tworzenia bardziej "graficzny" wyjście (usunięty textFormat i spacing parametry):

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

a wynik jest:

Answer 2

To jest mój wziąć na to:

Dodałem PrintPretty do BNode, a ja usunęła drugą Print funkcję trzeba było w btree.

(Edit: zrobiłem drzewo więcej lisible zmieniając oryginalnych znaków rysować gałęzie drzewa)

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

    } 

Jest to wynik (bardziej zwartych, jak już wspomniałem):

---

Edit: następujący kod został zmodyfikowany w celu pokazania informacji o lewo-prawo:

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

    } 

Rezultat: