C# Zeigt einen Binären Suchbaum in der Konsole

Habe ich 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 kann ich das einfügen von Werten 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);

Möchte ich die Anzeige mein Baum in meiner Konsolenanwendung. Ich habe eine btr.Print(); zeigt mein Baum von Links nach rechts (6 ist die Wurzel) - aber ich bin nicht glücklich mit ihm.

C# Zeigt einen Binären Suchbaum in der Konsole

Frage: gibt es einen besseren Weg, um diese Struktur innerhalb einer Konsolenanwendung? Auch eine Verbesserung dieser Print() mir helfen würde.

Ich denke, der Ansatz, in dieser anderen link sieht schöner und kompakter: stackoverflow.com/a/1649223/831138 . "Compact" in dem Sinne, dass es passen mehr Informationen in der gleichen Platz auf dem Bildschirm... natürlich, es geht um stretch es senkrecht, aber mit dem Scrollbalken der Konsole sollte nicht das problem sein... ausgeführt, dass der horizontale Abstand ist ein problem.
Mögliche Duplikate von Baum-Visualisierung-Algorithmus
stackoverflow.com/questions/801740/...

InformationsquelleAutor fubo | 2016-03-30

binary-tree c#console

Ich habe endete mit der folgenden Methode, mit der Sie drucken beliebigen Teilbaum:

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 habe einige Parameter, die Einfluss auf die Formatierung. Standardmäßig erzeugt es die kompakteste Darstellung.

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

public class BTree
{
    //...

    public BNode Root { get { return _root; } }

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

Mithilfe von Beispieldaten, hier sind einige Ergebnisse:

btr.Root.Print();

C# Zeigt einen Binären Suchbaum in der Konsole

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

C# Zeigt einen Binären Suchbaum in der Konsole

UPDATE: IMO das Standard-format oben ist kompakt und gut lesbar, aber nur zum Spaß, der Algorithmus angepasst, um mehr zu produzieren "grafische" Ausgabe (textFormat und spacing Parameter entfernt):

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:

C# Zeigt einen Binären Suchbaum in der Konsole

Wirklich wie dieser code, gute Arbeit. Sehr sauber und gut lesbar.
danke das ist was ich gesucht habe - tolle Arbeit

InformationsquelleAutor Ivan Stoev

Dies ist mein nehmen auf Sie:

Habe ich PrintPretty zu BNode, und ich habe entfernt die zweite Print Funktion, die Sie hatten in BTree.

(Edit: ich habe den Baum mehr lisible durch die änderung der ursprünglichen chars zeichnen Sie die äste des Baumes)

    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 (mehr kompakt, wie ich schon erwähnt habe):

C# Zeigt einen Binären Suchbaum in der Konsole

Edit: der folgende code wurde geändert, um zu zeigen, die info über Links-rechts:

    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:

C# Zeigt einen Binären Suchbaum in der Konsole

ok, das ist trotzig eine verbesserte und kompaktere version mit +1 - aber es verliert eine information - wenn ein Kind-Knoten ist auf der linken Seite (Wert niedriger ist als der des übergeordneten Knotens) oder auf der rechten Seite (Wert höher ist)
Sie haben völlig Recht, ich dachte auch gestern nach dem posting, aber ich hatte keine Zeit, es zu korrigieren... Jetzt habe ich änderte den code ein wenig, um zu zeigen, die info über Links und rechts. Eine Sache, die man nutzen kann, in einer Konsole, um fügen Sie mehr visuelle info, ist das Spiel mit den Farben, und das ist auch etwas, das ich Hinzugefügt habe, auf die neue version.

InformationsquelleAutor Xavier Peña

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.